什么是栈

栈是算法竞赛中常用的一种线性数据结构，请注意，本文主要讲的是栈这种数据结构，而非程序运行时的系统栈/栈空间。
栈 - 图1
如上图，栈的修改是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。

栈的数组实现

  1. // C++ Version
  2. int st[N];
  3. // 这里使用 st[0] (即 *st) 代表栈中元素数量，同时也是栈顶下标
  5. // 压栈 ：
  6. st[++*st] = var1;
  8. // 取栈顶 ：
  9. int u = st[*st];
  11. // 弹栈 ：注意越界问题, *st == 0 时不能继续弹出
  12. if (*st) --*st;
  14. // 清空栈
  15. *st = 0;

栈的STL

C++ 中的 STL 也提供了一个容器 std::stack，使用前需要引入 stack 头文件。

  1. // clang-format off
  2. template<
  3.     class T,
  4.     class Container = std::deque<T>
  5. > class stack;

T 为 stack 中要存储的数据类型。
Container 为用于存储元素的底层容器类型。这个容器必须提供通常语义的下列函数：

  • back()
  • push_back()
  • pop_back()

STL 容器 std::vector、std::deque 和 std::list 满足这些要求。如果不指定，则默认使用 std::deque 作为底层容器。
使用详情请见 -> STL标准模板库