1 /*  2 用两个栈实现双端队列  3 栈s1，s2。  4 pushback()和popback(),必须在s2为空的情况，把s2的都放s1中  5 pushfront()和popfront(),必须是在s1为空，把s1的都给放到s2中  6 */  7 #include <iostream>  8 #include <stack>  9 using namespace std; 10 template <typename T> 11 class DequeBy2Stack 12 { 13 private: 14     int maxsize; 15     stack<T> s1; 16     stack<T> s2; 17 public: 18     DequeBy2Stack(int size):maxsize(size){} 19     void pushback(T n); 20     T popback(); 21     void pushfront(T n); 22     T popfront(); 23     int size(); 24     bool empty(); 25 }; 26 template <typename T> 27 bool DequeBy2Stack<T>::empty() 28 { 29     return s2.empty()&&s1.empty(); 30 } 31 template <typename T> 32 int DequeBy2Stack<T>::size() 33 { 34     return s1.size()+s2.size(); 35 } 36 template <typename T> 37 void DequeBy2Stack<T>::pushback(T n) 38 { 39     if(this->size()==maxsize) 40     { 41         throw new std::exception("Invalid push"); 42     } 43     while(!s2.empty())           //必须将s2中的数据都导入到s1中 44     { 45         int tmp=s2.top(); 46         s1.push(tmp); 47         s2.pop(); 48     } 49     s1.push(n); 50 } 51 template <typename T> 52 T DequeBy2Stack<T>::popback() 53 { 54     while(!s2.empty()) 55     { 56         int tmp=s2.top(); 57         s1.push(tmp); 58         s2.pop(); 59     } 60     if(!s1.empty()) 61     { 62         int tmp=s1.top(); 63         s1.pop(); 64         return tmp; 65     } 66     else 67     { 68         throw new exception("Invalid popback()"); 69     } 70 } 71 template <typename T> 72 void DequeBy2Stack<T>::pushfront(T n) 73 { 74     if(this->size()==maxsize) 75     { 76         throw new std::exception("Invalid push"); 77     } 78     while(!s1.empty()) 79     { 80         int tmp=s1.top(); 81         s2.push(tmp); 82         s1.pop(); 83     } 84     s2.push(n); 85 } 86 template <typename T> 87 T DequeBy2Stack<T>::popfront() 88 { 89     while(!s1.empty()) 90     { 91         int tmp=s1.top(); 92         s2.push(tmp); 93         s1.pop(); 94     } 95     if(!s2.empty()) 96     { 97         int tmp=s2.top(); 98         s2.pop(); 99         return tmp;100     }101     else102     {103         throw new exception("Invalid popfront");104     }105 }106 107 int main()108 {109     DequeBy2Stack<int> test(8);110     int n;111     for(int i=1;i<=8;i++)112     {113         test.pushback(i);114     }115     test.popback();116     test.popfront();117     test.popfront();118     test.popfront();119     test.pushfront(100);120     test.pushfront(101);121     test.pushback(30);122     test.pushfront(102);123     test.popfront();124     while(!test.empty())125         cout<<test.popback()<<endl;126     system("pause");127 }128