359
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，主要代碼如下：
- 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源碼剖析
最後更新：2017-04-04 07:03:55