赞
踩
创造不易,可以点点赞吗~
如有错误,欢迎指出~
目录
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶,另一端称为栈底。
栈是一种 先进后出 的数据结构
- Stack<Integer> stack=new Stack<>();
- //入栈
- stack.push(1);
- stack.push(2);
- stack.push(3);
- stack.push(4);
pop出栈,会删除栈顶元素
- //出栈
- Integer x=stack.pop();
- System.out.println(x);
-
peek(瞄一眼~)获取栈顶元素,不删除
- //peek
- Integer y1=stack.peek();
- System.out.println(y1);
-
- Integer y2=stack.peek();
- System.out.println(y2);
- Stack<Integer> stack=new Stack<>();
- System.out.println(stack.isEmpty());
- System.out.println(stack.isFull());
下面是利用数组模拟实现一个栈,这种叫做顺序栈。
定义一个数组来实现栈
usedSize表示
- public class MyStack {
- public int[] elem;
- public int usedSize;
-
- public MyStack(){
- this.elem=new int[10];//初始设定为10个空间
- }
- }
- public void push(int val){
- //判断是否满了
- if(isFull()){
- //扩容
- elem= Arrays.copyOf(elem,2*elem.length);
- }
- elem[usedSize]=val;
- usedSize++;
- }
- public boolean isFull(){
- return usedSize==elem.length;
- }
- public int pop(){
- if(empty()){
- return -1;
- }
- int oldVal=elem[usedSize-1];
- // elem[usedSize-1]=null;//如果是引用类型要置空
- usedSize--;
- return oldVal;
- }
-
- public int peek(){
- if (empty()) {
- return -1;
- }
- return elem[usedSize-1];
- }
-
- public boolean empty(){
- return usedSize==0;
- }
- MyStack myStack=new MyStack();
- myStack.push(1);
- myStack.push(2);
- myStack.push(3);
-
- System.out.println(myStack.pop());
- System.out.println(myStack.peek());
- System.out.println(myStack.peek());
将int换成E类型
- import java.util.Arrays;
-
- public class MyStack2<E> {
- public Object[] elem;
- public int usedSize;
-
- public MyStack2(){
- this.elem=new Object[10];//初始设定为10个空间
- }
- public void push(E val){
- //判断是否满了
- if(isFull()){
- //扩容
- elem= Arrays.copyOf(elem,2*elem.length);
- }
- elem[usedSize]=val;
- usedSize++;
- }
- public boolean isFull(){
- return usedSize==elem.length;
- }
- public E pop(){
- if(empty()){
- return null;
- }
- E oldVal=(E)elem[usedSize-1];
- // elem[usedSize-1]=null;//如果是引用类型要置空
- usedSize--;
- return oldVal;
- }
- public E peek(){
- if (empty()) {
- return null;
- }
- return (E)elem[usedSize-1];
- }
- public boolean empty(){
- return usedSize==0;
- }
- }
- MyStack2<Integer> myStack2=new MyStack2<>();
- myStack2.push(9);
- myStack2.push(8);
- myStack2.push(7);
-
- System.out.println(myStack2.pop());
- System.out.println(myStack2.peek());
- System.out.println(myStack2.peek());
如果使用的是单链表,那么入栈和出栈最好使用链表的头部,这样的时间复杂度可以达到O(1),
若用链表的尾部,时间复杂度是O(N)
如果使用的是双向链表,那么入栈和出栈可以使用链表的头部或尾部,时间复杂度都是O(1)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。