Stack两栈实现队列

比较简单。

//用两个栈实现队列

#include<iostream>
using namespace std;

template<class Type> class Stack
{
private:
    int top;
    Type* elements;
    int maxSize;
public:
    Stack(int sz=50):top(-1),maxSize(sz)
    {
        elements=new Type[sz];
    }

    void push(const Type& x)
    {
        elements[++top]=x;
    }

    Type& pop()
    {
        return elements[top--];
    }

    Type& peek()
    {
        return elements[top];
    }

    bool isEmpty()
    {
        return (top==-1)?true:false;
    }
};

template<class Type> class Queue
{
private:
    Stack<Type> stack1;
    Stack<Type> stack2;
public:


    void enQueue(const Type& x)
    {
        stack1.push(x);
    }

    Type& deQueue()
    {
        if(stack2.isEmpty())
        {
     /*       if(stack1.isEmpty())
            {
                throw runtime_error("Queue 为空！");
            }
            else  */
                while(!stack1.isEmpty())
                {
                    stack2.push(stack1.pop());
                }
        }
        return stack2.pop();
    }

    Type& peek()
    {
        if(stack2.isEmpty())
        {
         /*   if(stack1.isEmpty())
            {
                throw runtime_error("Queue 为空！");
            }
            else */
                while(!stack1.isEmpty())
                {
                    stack2.push(stack1.pop());
                }
        }
        return stack2.peek();
    }
};

int main()
{
    Queue<string> queue;
    queue.enQueue("first");
    queue.enQueue("second");
    cout<<queue.peek()<<endl;
    queue.enQueue("second");
    queue.deQueue();
    queue.enQueue("third");
    cout<<queue.deQueue()<<endl;
    cout<<queue.deQueue()<<endl;
    return 0;
}