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，主要代码如下：
- template <class T, class Sequence = deque<T> >
- class stack {
- Sequence c; // 底层容器
- public:
- // 通过调用deque的方法完成 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(); }
- void push(const value_type& x) { c.push_back(x); }
- void pop() { c.pop_back(); }
- };
4. 迭代器
stack所有元素的进出都必须符合LIFO的条件，只有stack顶端的元素，才能被访问，所以，stack不提供迭代器。
5. stack使用示例
代码如下：
- #include <iostream>
- #include <stack>
- using namespace std;
- int main ()
- {
- stack<int> myints;
- cout << "0. size: " << (int) myints.size() << endl;
- for (int i=0; i<5; i++) myints.push(i);
- cout << "1. size: " << (int) myints.size() << endl;
- myints.pop();
- cout << "2. size: " << (int) myints.size() << endl;
- return 0;
- }
6. 结语
Stack是一个容器适配器，通过包装既有容器，从而为程序员提供了堆栈的全部功能。
参考文献：
STL源码剖析
