CareerCup-3.5

Implement a MyQueue class which implements a queue using two stacks

开始想到的方法是入队的时候数据进入栈0，出队的时候数据移入栈1再pop。看了答案方法更好。只需要单向挪动。问题在于思维定势，想到队列，总觉得这些数据必须按照顺序在一个栈里。

#include iostream 

using namespace std; 

typedef int Data; 

struct Node 

 Node(Data d):data(d){next = NULL;}; 

 Data data; 

 Node* next; 

class Stack 

public: 

 Stack():topNode(NULL){}; 

 void pop() 

 if(topNode != NULL) 

 Node* p = topNode; 

 topNode = topNode- next; 

 delete p; 

 } else { 

 throw "Empty Stack"; 

 Data top() 

 if(topNode != NULL) 

 return topNode- data; 

 } else { 

 throw "Empty Stack"; 

 void push(Data data) 

 Node* d = new Node(data); 

 d- next = topNode; 

 topNode = d; 

 bool isEmpty(){return topNode == NULL;}; 

private: 

 Node* topNode; 

class MyQueue 

public: 

 void enqueue(Data data) 

 stack[0].push(data); 

 Data dequeue() 

 if(stack[1].isEmpty()) 

 while(!stack[0].isEmpty()) 

 stack[1].push(stack[0].top()); 

 stack[0].pop(); 

 if(stack[1].isEmpty()) 

 throw "Empty Queue"; 

 Data data = stack[1].top(); 

 stack[1].pop(); 

 return data; 

 bool isEmpty(){return stack[0].isEmpty() stack[1].isEmpty();}; 

private: 

 Stack stack[2]; 

int main() 

 MyQueue queue; 

 for(int i=0; i i++) 

 queue.enqueue(i*2); 

 queue.enqueue(i*2+1); 

 cout queue.dequeue() endl; 

 cout queue.dequeue() endl; 

 system("pause");