1. 栈的实现（数组）

2.  1 template<typename T> class ArrayStack { 2 public: 3     ArrayStack(int c = 100): capacity(c), top(-1) { 4         data = http://www.mamicode.com/new T[capacity](); 5     } 6     ArrayStack(const ArrayStack &rhs):capacity(rhs.capacity), top(rhs.top) { 7         data = http://www.mamicode.com/new T[capacity](); 8  9         std::copy(rhs.data, rhs.data + capacity, data);10     }11 12     ArrayStack& operator=(ArrayStack rhs) {13         Swap(rhs);14 15         return *this;16     }17 18     ~ArrayStack() {19         delete []data;20     }21 22     void Push(const T& val) {23         data[++top] = val;24     }25 26     void Pop()27     {28         if (top > -1)29             --top;30     }31 32     T& Top()33     {34         return data[top];35     }36 37     const T& Top() const 38     {39         return data[top];40     }41 42     bool Empty()43     {44         return top == -1;45     }46 47     std::size_t Size()48     {49         return top + 1;50     }51 52 private:53     void Swap(ArrayStack &rhs) {54         std::swap(capacity, rhs.capacity);55         std::swap(top, rhs.top);56         std::swap(data, rhs.data);57     }58 59     int capacity;60     int top;61     T *data;62 };

    

3. 两个栈实现一个队列
   

    1 template <class T> class StackQueue { 2  public: 3     StackQueue(){} 4     size_t size() { 5         return s1.size() + s2.size(); 6     } 7  8     bool empty() { 9         return size() == 0;10     }11 12     void push(const T& val) {13         s1.push(val);14     }15 16     void pop() {17         if (s2.empty()) {18             while (!s1.empty()) {19                 s2.push(s1.top());20                 s1.pop();21             }22         }23         s2.pop();24     }25 26     T& front() {27         if (!s2.empty())28             return s2.top();29         while (!s1.empty()) {30             s2.push(s1.top());31             s1.pop();32         }33         34         return s2.top();35     }36 37  private:38      std::stack<T> s1, s2;39 };

    

4. 栈的压入、弹出序列
   输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。假设压入栈的所有数字均不相等。例如，序列1,2,3,4,5是某栈的压栈序列，序列4,5,3,2,1是该栈的对应的一个弹出序列，但4,3,5,2,1就不可能是该压栈序列的弹出序列。
   

    1 #include<iostream> 2 #include<stack> 3  4 bool IsPopOrder(const int *pushorder, const int * poporder, int length) { 5     if (pushorder == NULL || poporder == NULL || length <= 0) 6         return false; 7  8     std::stack<int> s; 9 10     const int *pop_val = poporder;11     const int *push_val = pushorder;12 13     while (pop_val - poporder < length) { 14         while (s.empty() || s.top() != *pop_val) {15             if (push_val - pushorder == length) 16                 break;17 18             s.push(*push_val++);19         }20 21         if (s.top() != *pop_val)22             return false;23 24         s.pop();25         pop_val++;26     }27 28     return true;29 30 }

    

栈与队列的相关题目