STL之stack棧

概述

棧（statck）這種資料結構在計算機中是相當出名的。

棧中的資料是先進後出的（First In Last Out, FILO）。棧隻有一個出口，允許新增元素（隻能在棧頂上增加）、移出元素（隻能移出棧頂元素）、取得棧頂元素等操作。

在STL中，棧是以别的容器作為底部結構，再将接口改變，使之符合棧的特性就可以了。是以實作非常的友善。

namespace std {
       template <class T,
                 class Container = deque<T> >
       class stack;
   }      

　　

　　The first template parameter is the type of the elements. The optional second template parameter defines the container that is used internally by the queue for its elements. The default container is a deque. It was chosen because, unlike vectors, deques free their memory when elements are removed and don't have to copy all elements on reallocation .

操作

The core interface of stacks is provided by the member functions push(), top(), and pop():

• push() inserts an element into the stack.
• top() returns the next element in the stack.
• pop() removes an element from the stack.
• stack<ElementType> c create a empty stack.
• stack<ElementType> c1(c2) copy a new stack from c2.
• empty() return wheather the stack is empty.
• size() return the number of element in the stack.

實作源代碼

namespace std {
      template <class T, class Container = deque<T> >
      class stack {
        public:
          typedef typename Container::value_type value_type;
          typedef typename Container::size_type  size_type;
          typedef          Container             container_type;
          protected:
            Container c;     // container
          public:
            explicit stack(const Container& = Container());

            bool        empty() const             { return c.empty(); }
            size_type   size()    const           { return c.size(); }
            void push   (const value_type& x)     { c.push_back(x); }
            void        pop()                     { c.pop_back(); }
            value_type& top()                     { return c.back(); }
            const value_type& top() const         { return c.back(); }
      };

      template <class T, class Container>
        bool operator==(const stack<T, Container>&,
                        const stack<T, Container>&);
      template <class T, class Container>
        bool operator< (const stack<T, Container>&,
                        const stack<T, Container>&);
      ...// (other comparison operators)
   }      

　　從實作源代碼中可以看出，由于棧隻是進一步封裝别的資料結構，并提供自己的接口，是以代碼非常簡潔，如果不指定容器，預設是用deque來作為其底層資料結構的（對deque不是很了解？可以參閱《STL之deque雙向隊列》）。

使用範例

// cont/stack1.cpp

   #include <iostream>
   #include <stack>
   using namespace std;

   int main()
   {

       stack<int> st;

       // push three elements into the stack
       st.push(l);
       st.push(2);
       st.push(3);

       // pop and print two elements from the stack
       cout << st.top() << ' ';
       st.pop() ;
       cout << st.top() << ' ';
       st.pop() ;

       // modify top element
       st.top() = 77;

       // push two new elements
       st.push(4);
       st.push(5);

       // pop one element without processing it
       st.pop() ;

       // pop and print remaining elements
       while (!st.empty()) {
           cout << st.top() << ' ';
           st.pop() ;
       }
       cout << endl;
   }      

3  2  4  77