【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术
欢迎关注个人主页:逸狼
创造不易,可以点点赞吗~
如有错误,欢迎指出~
目录
栈
栈的方法介绍
入栈push
出栈pop和
瞄一眼peek
判空isEmpty和判满isFull
模拟实现栈
push入栈
pop出栈和peek
测试
使用泛型实现栈
测试
使用链表实现栈(链式栈)
栈
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶,另一端称为栈底。
栈是一种 先进后出 的数据结构
栈的方法介绍
入栈push
Stack<Integer> stack=new Stack<>();//入栈stack.push(1);stack.push(2);stack.push(3);stack.push(4);
出栈pop和
pop出栈,会删除栈顶元素
//出栈Integer x=stack.pop();System.out.println(x);
瞄一眼peek
peek(瞄一眼~)获取栈顶元素,不删除
//peekInteger y1=stack.peek();System.out.println(y1);Integer y2=stack.peek();System.out.println(y2);
判空isEmpty和判满isFull
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个空间}
}
push入栈
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;}
pop出栈和peek
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)