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;
   }

The output of the program is as follows:

					
   3  2  4  77