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<5; i++)  
    {  
        queue.enqueue(i*2);  
        queue.enqueue(i*2+1);  
        cout<<queue.dequeue()<<endl;  
        cout<<queue.dequeue()<<endl;  
    }  
    system("pause");  
};