STL源码之stack深入学习

学完STL中vector, list, deque这三个较为复杂序列式容器之后，序列式容器中还剩下stack, queue以及priority-queue三部分内容。我们前面提及到，stack和queue由于是以deque为底部结构，技术上被归类为一种配接器(adapter)。

1. stack概述
   （1）stack是一种先进后出（First In Last Out）的数据结构。它只有一个出口。
   （2）stack允许新增元素、移除元素、取得最顶端元素。
   （3）stack的结构：
2. stack定义完整列表
   （1）SGI STL以deque作为缺省情况下stack的底部结构。（将deque接口改变，使其符合“先进后出”的特性）
   （2）由于stack是以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”的性质者，称为adapter。
   （3）因此，STL stack往往不被归类为container，而被归类为container adapter。
   
   C++

   template <class T, class Sequence = deque<T>> class stack { //以下的__STL_NULL_TMPL_ARGS会展开为<> friend bool operator== __STL_NULL_TMPL_ARGS(const stack&, const stack&); friend bool operator< __STL_NULL_TMPL_ARGS(const stack&, const stack&); 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() { 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<(cosnt stack<T, Sequence>& x, const stack<T, Sequence>& y) { return x.c < y.c; }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

   template <class T, class Sequence = deque<T>> class stack { //以下的__STL_NULL_TMPL_ARGS会展开为<> friend bool operator== __STL_NULL_TMPL_ARGS(const stack&, const stack&); friend bool operator< __STL_NULL_TMPL_ARGS(const stack&, const stack&); 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() { 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<(cosnt stack<T, Sequence>& x, const stack<T, Sequence>& y) { return x.c < y.c; }

3. stack没有迭代器
   （1）stack所有元素的进出都必须符合“先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。
   （2）stack不提供走访功能，也不提供迭代器。
4. 以list作为stack的底层容器
   （1）除了deque之外，list也是双向开口的数据结构。上述stack源码中使用的底层容器的函数有empty, size, back, push_back, pop_back等等，list都具备。
   （2）若以list为底部结构并封闭其头端开头，一样能够轻易形成一个stack。
5. 实例（以list为底层容器）
   
   C++

   #include <stack> #include <list> #include <iostream> #include <algorithm> using namespace std; int main() { stack<int, list<int>> istack; istack.push(1); istack.push(3); istack.push(5); istack.push(7); cout << istack.size() << endl; //4 cout << istack.top() << endl; //7 istack.pop(); cout << istack.top() << endl; //5 istack.pop(); cout << istack.top() << endl; //3 istack.pop(); cout << istack.top() << endl; //1 cout << istack.size() << endl; //1 }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   #include <stack> #include <list> #include <iostream> #include <algorithm> using namespace std;   int main() { stack<int, list<int>> istack; istack.push(1); istack.push(3); istack.push(5); istack.push(7); cout << istack.size() << endl; //4 cout << istack.top() << endl; //7 istack.pop(); cout << istack.top() << endl; //5 istack.pop(); cout << istack.top() << endl; //3 istack.pop(); cout << istack.top() << endl; //1 cout << istack.size() << endl; //1 }