Queue两队列实现栈

思路要清晰。
View Code
  1 //两队列实现栈
  2 #include<iostream>
  3 using namespace std;
  4 
  5 template<class Type> class Queue
  6 {
  7 private:
  8     int rear,front;
  9     Type* elements;
 10     int maxSize;
 11 public:
 12     Queue(int sz=50):rear(0),front(0),maxSize(sz)
 13     {
 14         elements=new Type[50];
 15     }
 16 
 17     void enQueue(const Type& x)
 18     {
 19         if(isFull())
 20             return ;
 21         elements[rear]=x;
 22         rear=(rear+1)%maxSize;
 23     }
 24 
 25     Type& deQueue()
 26     {
 27         Type temp=elements[front];
 28         front=(front+1)%maxSize;
 29         return temp;
 30     }
 31 
 32     Type& peek()
 33     {
 34         return elements[front];
 35     }
 36 
 37     bool isFull()  //注意为了判断空或满，必须留一个空的元素空间。。。
 38     {
 39         return ((rear+1)%maxSize==front)?true:false;
 40     }
 41 
 42     bool isEmpty()
 43     {
 44         return (front==rear)?true:false;
 45     }
 46 
 47     int size()
 48     {
 49         return (rear-front+maxSize)%maxSize;
 50     }
 51 };
 52 
 53 template<class Type> class Stack
 54 {
 55 private:
 56     Queue<Type> queue1;
 57     Queue<Type> queue2;
 58 public:
 59     void push(const Type& x)//开始考虑错了，考虑如果一个装满了，怎么办？首先思维就错了。
 60     {
 61         if(queue1.isEmpty())
 62             queue2.enQueue(x);
 63         else
 64             queue1.enQueue(x);
 65     }
 66     Type& pop()
 67     {
 68     //    if(queue1.isEmpty()&&queue2.isEmpty()) return;
 69         if(queue1.isEmpty())
 70         {
 71             while(queue2.size()>1)
 72                 queue1.enQueue(queue2.deQueue());
 73             return queue2.deQueue();
 74         }
 75         else
 76         {
 77             while(queue1.size()>1)
 78                 queue2.enQueue(queue1.deQueue());
 79             return queue1.deQueue();
 80         }
 81 
 82     }
 83 
 84     Type& peek()
 85     {
 86         //    if(queue1.isEmpty()&&queue2.isEmpty()) return;
 87         Type result;
 88         if(queue1.isEmpty())
 89         {
 90             while(queue2.size()>1)
 91                 queue1.enQueue(queue2.deQueue());
 92             result=queue2.deQueue();
 93             queue1.enQueue(result);
 94         }
 95         else
 96         {
 97             while(queue1.size()>1)
 98                 queue2.enQueue(queue1.deQueue());
 99             result=queue1.deQueue();
100             queue2.enQueue(result);
101         }
102         return result;
103     }
104 };
105 
106 int main()  
107 {
108     Stack<int> stack;
109     stack.push(1);
110     stack.push(2);
111     stack.push(3);
112     cout<<stack.pop()<<endl;//3
113     stack.push(3);
114     cout<<stack.pop()<<endl;//3
115     stack.push(4);
116     cout<<stack.peek()<<endl;//4
117     cout<<stack.pop();
118     cout<<stack.pop()<<endl;//4 2
119     cout<<stack.peek();
120     cout<<stack.pop()<<endl;//1 1
121     return 0;
122 }
123 // cout<<stack.pop()<<stack.pop();不是按自己想要的顺序。
124 //如果只有一个元素：
125 //cout<<stack.peek()<<stack.pop();貌似是从右向左执行。