栈的核心概念与基本操作

学习目标

本节学习栈的核心概念和基本操作。

学习完成后，你需要能够解释什么是栈顶、什么是入栈、什么是出栈，以及为什么栈的操作顺序一定符合后进先出。

栈可以理解为一端开放的线性结构。所有插入和删除都发生在同一端，这一端叫作栈顶。

栈顶
 ↓
 C
 B
 A

在这个栈中，A 最早进入，C 最晚进入。因为只能从栈顶操作，所以 C 会最先离开。

入栈通常叫 push，表示把元素放到栈顶。

出栈通常叫 pop，表示移除并返回栈顶元素。

stack<string> names;

names.push("A");
names.push("B");
names.push("C");

string topName = names.top();
names.pop();

Deque<String> names = new ArrayDeque<>();

names.push("A");
names.push("B");
names.push("C");

String topName = names.peek();
names.pop();

names = []

names.append("A")
names.append("B")
names.append("C")

top_name = names[-1]
names.pop()

Stack<string> names = new Stack<string>();

names.Push("A");
names.Push("B");
names.Push("C");

string topName = names.Peek();
names.Pop();

这四段代码中，A、B、C 依次进入栈。最后进入的是 C，因此栈顶元素是 C。执行一次出栈后，C 离开，B 成为新的栈顶。

查看栈顶指的是读取当前最上面的元素，但不把它移除。

在很多语言库中，这个操作常叫 top、peek 或通过下标访问最后一个元素。

查看栈顶的用途很多。例如，在括号匹配中，我们经常需要查看最近一个尚未匹配的左括号；在表达式求值中，也经常需要查看最近入栈的操作符或操作数。

出栈前通常需要判断栈是否为空。对空栈执行出栈操作通常是错误的。

if (!names.empty()) {
    string value = names.top();
    names.pop();
}

if (!names.isEmpty()) {
    String value = names.pop();
}

if names:
    value = names.pop()

if (names.Count > 0)
{
    string value = names.Pop();
}

判空是栈操作中非常常见的边界处理。后续写算法题时，很多错误都来自没有处理空栈情况。

如果底层实现合理，栈的常见操作通常很高效：

操作        常见时间复杂度
入栈 push   O(1)
出栈 pop    O(1)
查看栈顶     O(1)
判空         O(1)

如果栈底层使用动态数组，入栈在触发扩容时会有一次搬移成本，但从长期平均看，尾部追加通常仍可视为摊还 $O(1)$ 。

不同语言的栈写法不同，但核心规则完全一致：最后进入的元素最先离开。

学习栈时，不要只记某个库方法的名字。更重要的是看到一个问题时，能判断它是不是具有“最近的先处理”这种特征。

如果一个过程总是需要回到最近的状态、处理最近的元素或撤销最近的动作，就应该想到栈。

栈是一种后进先出的受限线性结构。

它的主要操作包括入栈、出栈、查看栈顶和判空。栈顶是唯一可以直接操作的位置。掌握栈的关键，是理解“最后进入的元素最先被处理”这一规则，而不是死记某种语言的具体语法。