Stack 是一种受限的线性结构，其末尾称之为 栈顶 (top)，元素进入栈称为 入栈 (push)，从栈中移除称为 出栈 (pop)。push 只能从 top 进行，元素加入结构的末尾； pop 也只能从 top 进行，移除的元素总是 top 的元素。由于其受限的特性，导致了数据只能以 先进后出 (First-In Last-Out, FILO) 的方式操作。整个栈中仅有 top 元素可见。

Stack ADT

template <class T>
concept stack =
    requires(T a, const T& b, const typename T::value_type& value) {
    requires swappable<T>;
    requires erasable<typename T::value_type>;
    requires same<typename T::reference, typename T::value_type&>;
    requires same<typename T::const_reference, const typename T::value_type&>;
    requires unsigned<typename T::size_type>;
    { a.empty() } -> boolean;
    { a.size() } -> typename T::size_type;
    { a.top() } -> typename T::reference;
    { b.top() } -> typename T::const_reference;
    a.push(value);
    a.pop();
};

stack 的实现

无论实现的效率如何，线性结构一般都支持从尾部插入、移除元素，因此 stack 的实现可以直接使用已经实现的线性容器，并对这些容器的接口进行包装，以实现对操作的限制。

因此这样对 container 进行包装的方式，被称为 适配器 (adaptor)。adaptor 可以根据自己的需求，选择合适的 container 进行包装。比如使用顺序实现的线性表或双链表进行包装，这里的具体实现就不再展开，栈的思想比其实现更为重要。

stack 的应用

也许你会想，这限制了线性表的操作，这还有什么用呢，那么接下来我们将看到几个例子。

平衡符号

我们有时候需要检测符号是否符合要求，比如说只有方括号与圆括号组成的一个序列，如果这个序列的括号可以正确匹配则序列符合要求，否则不符合要求。如 [()[]] 是一个符合要求的需要，而 [(]) 不符合要求。

stack s;
for (auto bracket : sequence) {
  if (bracket == '[' || bracket == '(') {
    s.push(bracket);
  } else {
    if (s.empty()) {
      return ERROR;
    }
    auto top = s.top();
    s.pop();
    if ((top == '[' && bracket == ')') || (top == '(' && bracket == ']')) {
      return ERROR;
    }
  }
}

后缀表达式

当你在计算器上输入 a + b * c + d ，有没有好奇为什么计算器可以理解正确的优先级，而不是将其理解 (a + b) * c 。或许因为它遵循优先级，才显得这是很理所应当的，而后者是不可理喻的。那么我们需要探寻的是计算器如何遵循优先级。

在上述示例中，我们先计算 b * c ，之后计算 + a 和 + d ，这个顺序你觉得像什么？是不是一个序列入栈并出栈的一个可能的序列 b -> c -> a -> d 。那么问题来了，数据在入栈之后，什么时候出栈呢。数据 b、c 的出栈是因为相乘，而 a 是因为与前面的结果相加，出栈是因为遇到了符号。为了方便起见，将一次计算结果也放入栈中，那么在每次遇到符号时，我们将从栈中弹出两个数字，经过运算将结果压入栈中。那我们可以把这个表达式写为

a b c ∗ + d +

而这种写法就是 后缀 (postfix) 或者说 * 逆波兰* (revwerse Polish)，我们平常使用的被称为 中缀 (infix) 表达式。另外 postfix expression 有个好处，那就是并不需要括号的支持，在序列中的顺序决定了运算顺序，而不需要再为某个子表达式添加括号来提升运算顺序。

计算逆波兰表达式

我们写出这个计算过程，其时间复杂度为 O(N)\mathcal{O}(N)O(N)，最终栈中唯一的元素就是表达式的结果。

stack s;
for (auto symbol : sequence) {
  if (is_op(symbol)) {
    auto b = s.top(); s.pop();
    auto a = s.top(); s.pop();
    // 假设存在 eval 函数，且 eval 可以执行操作 a op b，并返回相应的结果
    s.push(eval(a, symbol, b));
  } else {
    s.push(symbol);
  }
}

中缀表达式转后缀表达式

那既然会计算 postfix 了，那如何将一个 infix expression 转换为 postfix expression。

我们需要一个用以存储运算符的栈 operation，以及一个用以存储后缀表达式的线性表 sequence。算法的基本思路是：依次读入表达式的符号，如果是操作数则入栈 sequence，否则和 operation 栈顶进行比较。如果 op 优先级高于栈顶元素则入栈，反之将 operation 中的元素依次弹出到 sequence 中，直到出现一个比 op 优先级小的运算符，弹出操作完成后将 op 压入 operation。最终表达式结束时，将栈中剩余符号全部弹出到 sequence 即可。

你会发现这个算法并没有处理括号，括号带来了复杂性，我们现在单独的说一下括号。当遇到左括号时，我们将其压入 operation，除右括号外任何运算符的优先级都低于左括号，因此只有右括号到来时，我们将栈中元素弹出，直到弹出一个左括号。我们在处理过程中并不将右括号入栈，并在左括号弹出栈后也不将其压入 sequence。这里我们给出表格来表示运算符的优先级，并根据表格实现一个优先级比较的函数，其中列符号表示 待弹出/压入 的运算符，行符号表示受比较的运算符。

// 比较运算符 o 和 p，如果 o 大于 p 则返回 true，否则返回 false
bool compare(operation o, operation p) {
  switch (o) {
    case PLUS: case MINUS: return is_plus(p) || is_minus(p); // o 是加号或减号
    case TIMES: case DIVISION: return !is_left_bracket(p); // o 是乘号或除号
    case LEFT_BRACKET: return false; // o 是左括号
    case RIGHT_BRACKET: return true; // o 是右括号
    defalut: return ERROR;
  }
}

在上述比较操作的基础上，我们可以轻松的实现一个中缀表达式转后缀表达式的过程。分析该算法的时间复杂度，该算法需要遍历整个 infix expression，并会额外遍历一遍 operation，因此复杂度为 Θ(N)。

// 接收一个中缀表达式序列，返回一个后缀表达式序列
sequence_container infix2postfix(sequence_container infix) {
  stack s;
  sequence_container postfix;
  for (auto symbol : infix) {
    // 当前元素是一个操作数
    if (!is_operation(symbol)) {
      postfix.push_back(symbol);
      continue;
    }
    // 当前元素是右括号且栈不为空，弹出运算符
    if (!s.empty() && is_right_bracket(symbol)) {
      // 将运算符弹出到 postfix 序列中，直到运算符为左括号或空栈为止
      while (!s.empty() && !is_left_bracket(s.top())) {
        postfix.push_back(s.top());
        s.pop();
      }
      // 将左括号移除
      if (!s.empty() && is_left_bracket(s.top())) {
        s.pop();
      }
      continue;
    }
    // 当前元素优先级小于栈顶元素，弹出运算符，直到元素优先级大于栈顶或空栈为止
    if (!s.empty() && !compare(symbol, s.top())) {
      while (!s.empty() && compare(s.top(), symbol)) {
        postfix.push_back(s.top());
        s.pop();
      }
    }
    s.push(symbol);
  }
  while (!s.empty()) {
    postfix.push_back(s.top());
    s.pop();
  }
  return postfix;
}

前缀表达式

既然有 infix 与 postfix，怎么会没有前缀表达式 (prefix) 呢。就如其字面意思，运算符在操作数之前。因此我们需要表示 5+25 + 25+2 时就可以写成 + 5 2 ，好像还不错，但感觉并没有什么用。

如果我们允许，在同一个运算符下的参数，都遵循该运算，那么我们就可以将 1+2+3+4+5+61 + 2 + 3 + 4 + 5 + 61+2+3+4+5+6 这一大长串写为 + 1 2 3 4 5 6 ，这样感觉还不错吧！

实际上，有编程语言采用前缀表达式作为基础的书写格式。其实你已经见过了，在 第一篇 中实现 Fibonacci 时就使用的这种语言，实际上是 Scheme (Lisp 的一种方言)，或者说这就是最基本的 Lisp 代码。

Lisp 代码其实是相当简单的！Lisp 使用括号作为分界符 (我想你已经想起 NASA 与 Lisp 的笑话了，我先笑为敬 xD 。其使用前缀表达式，因此括号中的第一个标识符就是运算符，因此引论中的 factorial (阶乘) 写为了 (* n (factorial (- n 1))) ，即 n∗(n−1)! 。

很简单吧！最后感受一下 Lisp 与前缀表达式的魅力吧，用 lisp 实现表达式

(/ (+ 5 4 (- 2 3) 6 (/ 4 5)) ;; 这里进行了去括号操作
   (* 3 (- 6 2) (- 2 7)))

运算符的结合性

大部分时刻我们都会忽略运算符的结合性问题，因为绝大多数运算符都是 左折叠 (fold left)，只有一小部分运算符采用 右折叠 (fold right)。

在 C++ 中所有的赋值运算符、自增、自减、取地址、解引用、逻辑非、按位取反等是 fold right。C++ 中可以重载运算符，但不能添加新的运算符，重载之后的运算符优先级与结合性保持不变。而 Haskell 中我们不仅可以重载运算符，还可以添加新的运算符，因此 Haskell 中我们定义运算符也可以定义它的优先级与结合性。

假设我们有运算符 ** 代表幂运算，幂运算显然是右结合的，2^{2^{3}} = 2^{8} = 256 而不是 4^{3} = 64 。但我们现在将中缀表达式转换成后缀表达式的过程，将所有运算符都当作左结合，这就会造成严重的问题。限于篇幅原因，这里只引出该问题，并不给出实现右结合的代码。

函数调用

我们在使用一个函数时，运行时会将所有局部变量存储起来，防止在调用新函数时将这些局部变量覆盖。当前指令的位置也会被存储，当新函数完成时，就可以回到原来的位置继续向下运行。当函数调用时，存储所有的重要信息 (如寄存器的值、返回地址等)，都要以抽象的方式存在与 一张纸上 并被置于堆 (pile) 的顶部。然后控制转移到心函数，该函数自由地用它的值替代寄存器。当函数返回时，需要对 pile 顶部的 纸 进行复原工作，以便返回继续执行。

所有存储的信息被称为 活动记录 (activation record) 或 栈帧 (stack frame)。在操作系统中，当前环境是栈顶描述的，因此栈从内存分区的高端向下增长，因此同时有太多函数运行会将栈空间用尽，被称作 栈溢出 (stack overflow)。当然正常情况下栈是不会被用尽的，一般 stack overflow 发生时，意味着有失控递归 (即忘记基准情况)。有时正常的程序也会用尽栈空间，比如递归过深的情况。

当然我们有一种方法可以减轻递归对栈空间的消耗，那就是将递归变为 迭代 。等等，不是说使用递归，怎么能用迭代呢！当然这里说的是迭代 (iterate) 而不是循环 (loop)，毕竟在不可变的 pure functional programming 中是无法实现 loop 的。

这里抛出一个问题：现在有方法 inc 和 dec 分别是将一个参数 加一 和 减一，如何用这两个方法实现两个正整数相加。这里依然使用 scheme 进行代码演示，请仔细阅读代码并思考其中的差别。

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))
(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

代码并不复杂，我们将这种递归实现的迭代又称之为 尾递归 (tail recursion)。如果编译器有针对递归的优化，往往会将 tail recursion 消除，或者将局部变量的值直接转移到函数的顶部，依次来消除递归带来的栈空间损耗。另外可以说明一点，tail recusion 总是可以机械地改写为 loop，而有些 recursion 需要 stack 的帮助就能改写为 loop。

在编程语言的实现中，tail recursion 比一般的递归效率更高，且不会有 stack overflow 风险，因此将递归转换为尾递归是可行的。不过 Weiss 在书中也说明了 tail recursion 相比 loop 并不是一个好的选择。但是 recursion 相比于 loop 其更加简洁、逻辑更为清晰。

最后再说一点吧。讲了很多关于 SICP 上第一章的内容。虽然 SICP 使用的是 scheme 作为讲解语言，但其并不难学，请不要有抵触心理。SICP 是一本相当好的书，虽然目前为止我只看完了第一章的内容。对了，不知道你对上面 scheme 代码实现的 a + b 有什么想法，下面就用图示给出两个代码的差别吧。图示左边部分对应前一个函数，即递归计算；右半部分对应后一个函数，即迭代计算。