栈结构与操作

栈是什么？

• 定义: 只在一端增删的线性表, 遵循后进先出 (LIFO);
• 栈顶: 允许增删的一端;
• 栈底: 不允许增删的另一端;
• 入栈 (push): 把元素放到栈顶;
• 出栈 (pop): 删除并返回栈顶元素;

栈提供哪些基本操作？

方法	描述	时间复杂度
push()	元素入栈	$O(1)$
pop()	栈顶元素出栈	$O(1)$
peek()	只读取栈顶元素	$O(1)$

• 语义要点: 出栈后元素不可再访问, 除非重新入栈;
• 空栈: pop、peek 必须约定返回值或抛错, 实现中常返回 null;

栈适合解决什么样的问题？

• 最近相关性: 需要和"上一个未消解的元素"配对, 如括号匹配、相邻去重;
• 逆序访问: 需要先拿到最后出现的元素, 如表达式求值、字符串解码;
• 单调性: 需要在遍历中维护一个有序候选集合, 见 单调栈原理;