栈就像枪的弹匣一样,放入子弹的时候只能从上面一个一个压入,取子弹时也只能从上面一颗颗取。
最先放进出去的子弹只能最后取出,同样的,『先进后出』就是数据结构中的栈了。

栈的应用场景有很多,最常见就是函数调用栈了,程序在执行时,操作系统给每个线程分配了一块独立空间,而这块内存就是用“栈”来组织的。
程序每调用一个函数,意味着一次入栈操作,而入栈的内容为该函数,称为栈帧。函数执行结束返回结果值,代表一次出栈操作。
实现一个栈
栈对外只暴露两个操作接口,分别为栈顶的「插入」和「删除」操作。
而栈既可以用数组实现,也可以用链表实现,前者称为顺序栈,后者称为链式栈。
数组和链表作为两大基础数据结构,成为了复杂数据结构的载体。栈、队列、树、图等结构都可以用数组或链表来表示。
使用Java实现的顺序栈如下:
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; // 栈的大小
// 初始化数组,申请一个大小为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后移
items[count++] = item;
return true;
}
// 出栈操作
public String pop() {
// 栈为空,则直接返回null
if (count == 0) return null;
// 返回下标为count-1的数组元素
String tmp = items[--count];
return tmp;
}
}
由于栈只能对栈顶进行操作,入栈和出栈的时间复杂度都为O(1)。
这个顺序栈在初始化时指定了大小,所以当栈满时,就不能继续添加数据了。解决方法有两个,一是改为链式栈,二是增加扩容机制。
链式栈虽然支持动态扩容,但每项数据都额外存储了next指针,加大了内存开销。
增加扩容机制其实就是数组的扩容机制,当空间不够时,申请一个新的空间更大的数组,将原数组迁移到新数组。
END
写到一半写不下去了:),因为栈的内容本身就很精炼,只要知道「先进后出」这个原则就好了。
对于栈,不要停留在它的定义上,我们更多关注它在算法和软件工程中的应用场景。栈的结构是单调的,但运用的思想却是巧妙的。
比如算法中的括号匹配、表达式运算、拼写检查等,还有递归的调用栈、JVM的虚拟机栈、浏览器的前进后退功能等等。
评论区