数组与线性结构
栈
栈是一种你只能碰到顶部的集合，就像一摞盘子：新盘子放在顶上，要拿也只能拿最上面那个。最后进去的最先出来——这叫做 LIFO，后进先出。两个核心动作是 push（压入顶部）和 pop（弹出顶部）；peek 则只看顶部而不取走。
因为所有操作都集中在一端，栈很便宜：push 和 pop 都是 O(1)。你可以用动态数组实现它（push 即追加、pop 即删末尾），也可以用链表（在头部 push/pop）。C++ 提供了现成的封装 std::stack。它故意没有快速触及中间的办法——这个限制正是要点，它让结构保持简单而快速。
留意之后你会发现栈无处不在。调用栈记录着谁调用了谁、以及如何返回；撤销历史会弹出最近一次操作；括号匹配、表达式求值，以及深度优先搜索中的回溯，都靠一个栈来记住该回到哪里。
#include <stack> std::stack<int> s; s.push(1); s.push(2); s.push(3); // top -> | 3 | // | 2 | // | 1 | (bottom) int t = s.top(); // 3 (peek, O(1)) s.pop(); // removes 3, O(1) // now top() == 2
LIFO 顺序；push 与 pop 都是 O(1)。
作为数据结构的栈，与运行程序的调用栈不是一回事——但调用栈本身就是一个栈，名字因此共用。
又称
另见