4_5.md

4.5 stack

4.5.1 stack 概述

stack 是一种先进后出的数据结构。stack 允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其他方法可以存取 stack 的其他元素。

将元素推入 stack 的操作称为 push，将元素推出 stack 的操作称为 pop。

4.5.2 stack 定义完整列表

若以 deque 为底部机构并封闭其头端开口，便轻易地形成了一个 stack。因此，SGI STL 便以 deque 作为缺省情况下的 stack 底部结构，stack 的实现因而非常简单，因此本处完整列出源码：

由于 stack 以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种样子”的性质，称为 adapter（配接器）。因此，stack 往往不被归类为 container，而被归类为 container adapter。

template <class T, class Sequence = deque<T>>
class stack {
  // 以下的 __STL_NULL_TEMPL_ARGS 会展开为 <>
  friend bool operator==__STL_NULL_TEMPL_ARGS(const stack& x, const stack& y);
  friend bool operator< __STL_NULL_TEMPL_ARGS(const stack& x, const stack& y);

public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;

protected:
  Sequence c;  // 底层容器

public:
  // 以下完全利用 Sequence c 的操作，完成 stack 的操作
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference top() { return c.back(); }
  const_reference top() const { return c.back(); }
  // deque 是两头可进出，stack 是末端进，末端出
  void push(const value_type& x) { c.push_back(x); }
  void pop() { c.pop_back(); }
};

template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c == y.c;
}

template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c < y.c;
}

4.5.3 stack 没有迭代器

stack 所有元素的基础农户都必须符合先进后出的条件，只有 stack 顶端的元素才有机会被外界取用。stack 不提供遍历功能，也不提供迭代器。

4.5.4 以 list 作为 stack 的底层容器

若以 list 为底部结构并封闭其头端开口，一样能够轻松形成一个 stack。下面是做法示范：

// file: 4stack-test.cpp
#include <stack>
#include <list>
#include <iostream>
#include <algorithm>

int main() {
  std::stack<int, std::list<int>> istack;
  istack.push(1);
  istack.push(3);
  istack.push(5);
  istack.push(7);

  std::cout << istack.size() << std::endl;    // out: 4
  std::cout << istack.top() << std::endl;     // out: 7

  istack.pop(); std::cout << istack.top() << std::endl;     // out: 5
  istack.pop(); std::cout << istack.top() << std::endl;     // out: 3
  istack.pop(); std::cout << istack.top() << std::endl;     // out: 1
  std::cout << istack.size() << std::endl;    // out: 1
}