【第四章】栈

文章目录

• 栈的基本概念
• • 后进先出
• 栈中的常见操作
• • 入栈
  • 出栈
  • 取栈顶元素
  • 判断栈是否为空
  • 获取栈中有效元素个数
• 栈的顺序存储与链式存储
• • 顺序存储实现栈
  • 链式存储实现栈
• 栈的优缺点
• • 优点
  • • 操作规则简单
    • 插入删除效率高
    • 应用场景广
  • 缺点
  • • 只能访问栈顶
    • 使用场景受规则约束
• 复杂度分析
• • 入栈
  • 出栈
  • 取栈顶元素
  • 判空
• C和Java中手动实现
• • C语言手动实现栈
  • Java中手动实现栈
• Java中栈的分析
• C++中对于stack的分析
• 本章小结

上一章我们对于链表进行了比较系统的介绍。到这里为止，我们已经接触了两种非常基础的线性结构，也就是顺序表和链表。而从这一章开始，我们要在前面线性表的基础上，进一步学习一种特殊的线性结构，那就是栈。

栈本质上依然属于线性表，只不过它对数据的插入和删除位置做了严格限制。也正因为这个限制，栈在很多场景中都非常有用，比如表达式求值，函数调用，括号匹配，深度优先搜索等等。所以说，栈虽然结构不复杂，但应用却非常广。

栈的基本概念

栈是一种特殊的线性表，它的特殊之处就在于：

只允许在一端进行插入和删除操作。

这一端通常被称为栈顶，另一端则称为栈底。

也就是说，栈中的元素并不是可以随意从中间插进去或者删掉的，而是必须遵守“后进先出”的规则。

后进先出

栈最核心的特点就是：

Last In First Out

也就是我们经常说的 LIFO，中文一般翻译成“后进先出”。

这个规则可以把它想象成一摞盘子：

• 新放上去的盘子总是在最上面
• 取的时候也只能先取最上面的

这就和栈的逻辑非常接近。

例如依次往栈中放入：

1 2 3 4

如果按栈的规则出栈，那么顺序就会变成：

4 3 2 1

这就是典型的后进先出。

栈中的常见操作

栈虽然结构简单，但是围绕它的操作是非常固定的。通常来说，栈最常见的几个操作如下：

入栈

入栈就是把一个元素放到栈顶。

一般英文中常写作：

push

如果把过程展开来看，那么栈的“增”其实就是在栈顶增加一个元素。以顺序栈为例，通常步骤就是：

1.先判断栈是否已满 2.如果没有满，就把新元素放到当前栈顶位置 3.然后让栈顶位置往上移动一格

例如原来栈中数据从栈底到栈顶依次是：

1 2 3

现在入栈一个 4，那么过程就是先把 4 放到原来栈顶后面的那个位置，再更新栈顶，最终就变成：

1 2 3 4

所以说，栈的“增”本质上就是在最上面压入一个新元素。

出栈

出栈就是把栈顶元素删除掉。

一般英文中常写作：

pop

如果把过程拆开来看，那么栈的“删”其实也只围绕栈顶进行。

例如当前栈中元素是：

1 2 3 4

这时候如果执行一次出栈，那么删掉的一定是最上面的 4。对应步骤一般就是：

1.先判断栈是否为空 2.如果不为空，就把栈顶位置往下移动一格 3.逻辑上原来的栈顶元素就被删除了

最后栈中就变成：

1 2 3

这里要注意，栈的删除不是去删中间任意元素，而只能删最上面的那个。

取栈顶元素

有时候我们不一定要立刻删除栈顶，而只是想看一下当前栈顶是谁。这时候一般会有一个专门的操作来获取栈顶元素。

常见写法一般为：

top / peek

这个操作其实就可以理解成栈中的“查”。只不过这里查的不是任意一个位置，而是当前最上面的那个元素。

例如当前栈中是：

1 2 3 4

那么取栈顶元素时，拿到的就是 4。并且要注意：

• 取栈顶元素只是查看
• 它不会把这个元素真的删除掉

所以执行完以后，栈本身通常还是原来的样子。

判断栈是否为空

栈在出栈或者取栈顶元素之前，通常都要先判断当前栈是否为空，否则就可能出现非法访问。

获取栈中有效元素个数

有些场景下还需要知道栈里现在到底有多少个元素，因此通常也会提供获取栈长度的操作。

如果从“改”的角度来说，栈本身其实没有像顺序表那种很自然的“修改任意位置元素”的需求。因为栈强调的是栈顶操作，所以在大多数场景里，栈更关注的是：

• 压入新元素
• 删除栈顶元素
• 查看栈顶元素

也就是说，栈的核心并不在于“改中间的值”，而在于维护后进先出的规则。

栈的顺序存储与链式存储

和前面的线性表类似，栈也可以有不同的实现方式。最常见的有两种：

1.顺序存储 2.链式存储

顺序存储实现栈

如果采用数组来实现栈，那么通常只需要：

• 一段连续空间
• 一个变量来记录当前栈顶位置

这种实现方式的优点是：

• 结构简单
• 访问栈顶方便
• 效率高

缺点是：

• 如果空间固定，容量会受限制
• 如果要动态扩容，就需要额外处理

链式存储实现栈

如果采用链表来实现栈，那么通常会把链表的某一端作为栈顶。

链式栈的优点是：

• 空间使用灵活
• 不需要考虑数组扩容问题

缺点是：

• 每个结点有额外指针开销
• 实现上比数组栈更绕一点

在实际学习和做题中，顺序栈通常更常见一些，因为它写起来更直接，也更贴近栈这种“栈顶频繁操作”的特点。

栈的优缺点

栈作为一种受限线性表，也有自己非常明显的优点和局限性。

优点

操作规则简单

栈只允许在栈顶进行插入删除，因此逻辑非常清晰。很多问题一旦识别出“后进先出”的特征，就可以很自然地想到栈。

插入删除效率高

无论是数组实现还是链表实现，只要操作都集中在栈顶，那么入栈和出栈通常都很高效。

应用场景广

栈在数据结构中虽然简单，但是应用非常广泛。比如：

• 括号匹配
• 表达式求值
• 函数调用栈
• DFS深度优先搜索
• 浏览器前进后退

这些背后都能看到栈的影子。

缺点

只能访问栈顶

栈最大的限制就在这里。它不能像顺序表那样按下标访问，也不能像普通链表那样灵活地处理中间位置的元素。

使用场景受规则约束

栈必须满足后进先出的特点，如果一个问题本身并不具备这个特征，那么使用栈往往就不合适。

复杂度分析

对于栈来说，复杂度分析一般并不算复杂，因为它的操作主要都集中在栈顶。

入栈

在不考虑扩容的前提下，入栈一般只涉及：

• 放入元素
• 更新栈顶位置

因此时间复杂度通常为：

O(1)

出栈

出栈一般只是删除栈顶元素并更新栈顶位置，因此时间复杂度通常也是：

O(1)

取栈顶元素

由于栈顶位置通常是直接可知的，所以取栈顶元素的时间复杂度一般也是：

O(1)

判空

判空通常只需要看当前有效元素个数或者栈顶位置是否满足条件，因此复杂度也通常是：

O(1)

所以从整体上看，栈是一种在局部操作上效率非常高的数据结构。

C和Java中手动实现

讲完概念以后，栈这一章同样不能只停留在定义层面。真正要把栈学明白，还是得自己动手写一遍。这里我们就按照“手动造轮子”的思路，分别用 C 和 Java 写一个最基础的顺序栈。

C语言手动实现栈

在 C 语言里，如果用顺序表思想来实现栈，那么通常需要这几个成员：

1.一段数组空间 2.当前有效元素个数 3.当前容量

结构体一般可以写成这样：

typedef int STDataType;

typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;

这里的 top 一般可以理解为当前有效元素个数，也可以理解为下一个可插入位置。

初始化通常如下：

void StackInit(ST* ps)
{
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}

入栈操作：

void StackPush(ST* ps, STDataType x)
{
if(ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
if(tmp == NULL)
{
perror("realloc fail");
exit(–1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}

ps->a[ps->top] = x;
ps->top++;
}

出栈操作：

void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top—;
}

取栈顶元素：

STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top – 1];
}

从这里也能看出来，顺序栈手写的关键其实很简单：

• 入栈：放数据并上移栈顶
• 出栈：下移栈顶
• 取栈顶：看 top – 1

Java中手动实现栈

Java 中手写栈时，思路和 C 语言其实一样，只不过不需要手动 malloc 和 free。

例如可以定义一个顺序栈类：

public class MyStack {
private int[] elem;
private int usedSize;

public MyStack() {
this.elem = new int[10];
}
}

这里：

• elem 表示底层数组
• usedSize 表示当前栈中有效元素个数

扩容逻辑可以这样写：

private void grow() {
int[] tmp = new int[this.elem.length * 2];
for (int i = 0; i < this.usedSize; i++) {
tmp[i] = this.elem[i];
}
this.elem = tmp;
}

入栈：

public void push(int val) {
if (usedSize == elem.length) {
grow();
}
elem[usedSize] = val;
usedSize++;
}

出栈：

public void pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
usedSize—;
}

获取栈顶元素：

public int peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return elem[usedSize – 1];
}

判空：

public boolean isEmpty() {
return usedSize == 0;
}

从这里也能很明显地看出来，Java 手写栈和 C 语言手写栈，在核心思想上其实没有本质区别，只不过一个更偏底层内存管理，一个更偏对象封装。

Java中栈的分析

在 Java 中，很多同学一开始会直接想到 Stack 类。这个类当然能用，但从现在的使用习惯来看，更多时候大家会更倾向于使用 Deque 接口下的实现类来模拟栈。

原因就在于：

• Stack 是比较早期的类
• 现在更多时候会用 ArrayDeque

例如：

Deque<Integer> stack = new ArrayDeque<>();

然后通过：

• push()
• pop()
• peek()

来完成栈的基本操作。

从底层思想上看，Java 中这些栈式操作，本质上依然是在维护“后进先出”的规则。

C++中对于stack的分析

在 C++ STL 中，也提供了一个专门的栈适配器，也就是 stack。

这里要注意，stack 严格来说并不是一个完全独立的数据结构容器，而更像是一种适配器。它会基于已有容器，把外部操作限制成栈的形式。

也就是说，stack 更强调的是：

只暴露栈该有的那部分行为。

常见操作包括：

• push
• pop
• top
• empty
• size

这和我们手写栈时的核心操作其实完全一致，只不过 STL 帮我们把底层细节封装好了。

本章小结

栈是一种特殊的线性表，它只允许在一端进行插入和删除操作，因此具有非常典型的后进先出特点。正因为这个规则明确，所以栈在表达式求值、括号匹配、函数调用、深度优先搜索等问题中都有广泛应用。

本章主要介绍了栈的基本概念、常见操作、优缺点、复杂度分析，同时补充了 C 和 Java 中手动实现栈的部分。对于栈这一章来说，真正重要的不是背下来 push 和 pop 这两个名字，而是要真正理解“为什么所有操作都围绕栈顶展开”。只要这一点想清楚了，栈的实现和应用都会顺很多。

好的，那么本章关于栈的内容就先介绍到这里。下一章我们会继续介绍和栈并列出现的另一个重要结构，也就是队列。栈讲的是后进先出，而队列讲的是先进先出，两者放在一起学习，效果会更好。