受限制的线性表
先进后出
实现一个栈
数组实现叫顺序栈
public class ArrayStack {
private String[] items;//存储数据的数组
private int count;//栈中的元素
private int n;//栈的大小
public ArrayStack(int n){
this.items = new String[n];
this.n = n;
this.count = 0;
}
//入栈操作
public boolean push(String item){
//如果栈满了返回false，入栈失败
if (count == n){
return false;
}
//将item放到下标为count的位置，count +1
items[count] = item;
//栈中元素+1
count++;
return true;
}
//出栈操作
public String pop(){
//如果栈为空返回null
if (count == 0){
return null;
}
//返回下标第n-1个元素
String temp = items[count - 1];
//元素总数减1
count--;
return temp;
}
}
支持动态扩容的顺序栈
分析时间复杂度
对于出栈来说时间复杂度还是O(1)
对于入栈来说如果栈空间足够时间复杂度为O(1)，如果栈空间不够用需要扩容那么时间复杂度为O(n)
链表实现叫链式栈
性能分析
不论是顺序栈还是链栈时间复杂度和空间复杂度都是O(1)
现实应用
函数调用栈
栈帧
表达式求值
两个栈实现
