STL容器适配器：stack

1. 概念
stack是一种LIFO（last-in first-out）的数据结构，其只允许在容器的尾部对数据进行操作,如下：

stack定义如下：
Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from the end of the container.
stacks are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed/popped from the "back" of the specific container, which is known as the top of the stack.

2. API
stack提供的API接口比较简单，如下：
(constructor)    Construct stack (public member function)
empty    Test whether container is empty (public member function)
size    Return size (public member function)
top    Access next element (public member function)
push    Add element (public member function)
pop    Remove element (public member function)

3. stack实现
stack是容器适配器，其通过对某种既有容器进行包装，从而提供LIFO的数据访问方法。不同的库，对stack有不同的实现，可以为deque，或者list，也可以为其他实现。
例如，SGI SQL就是通过deque实现stack，主要代码如下：

1template <class T, class Sequence = deque<T> >
2class stack {
3Sequence c; // 底层容器
4public:
5// 通过调用deque的方法完成 stack 的操作。
6bool empty() const { return c.empty(); }
7size_type size() const { return c.size(); }
8reference top() { return c.back(); }
9const_reference top() const { return c.back(); }
10void push(const value_type& x) { c.push_back(x); }
11void pop() { c.pop_back(); }
12};

4. 迭代器
stack所有元素的进出都必须符合LIFO的条件，只有stack顶端的元素，才能被访问，所以，stack不提供迭代器。

**5. stack使用示例
**代码如下：

1#include <iostream>
2#include <stack>
3using namespace std;
4
5int main ()
6{
7  stack<int> myints;
8  cout << "0. size: " << (int) myints.size() << endl;
9
10  for (int i=0; i<5; i++) myints.push(i);
11  cout << "1. size: " << (int) myints.size() << endl;
12
13  myints.pop();
14  cout << "2. size: " << (int) myints.size() << endl;
15
16  return 0;
17}

输出结果： 0. size: 0 1. size: 5 2. size: 4

**6. 结语
**Stack是一个容器适配器，通过包装既有容器，从而为程序员提供了堆栈的全部功能。

参考文献：
STL源码剖析