【Java--数据结构】栈：不仅仅是数据存储，它是编程的艺术
如有错误，欢迎指出~
栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。
栈是一种 先进后出 的数据结构
栈的方法介绍
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个空间
}
}
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)
Ongwu博客 版权声明：以上内容未经允许不得转载！授权事宜或对内容有异议或投诉，请联系站长，将尽快回复您，谢谢合作！