用两个栈实现一个队列

已知下面 Stack 类及其 3 个方法 Push、Pop 和 Count，请用 2 个 Stack 实现 Queue 类的入队(Enqueue)出队(Dequeue)方法。

class Stack
{
…
public:
         void Push(int x); // Push an element in stack;
         int Pop();  // Pop an element out of stack;
         int Count() const;     // Return the number of the elements in stack;
…
};

class Queue
{
…
public:
         void Enqueue(int x);
         int Dequeue();
 
private:
         Stack s1;
         Stack s2;
…
};

入队时，将元素压入 s1。

出队时，判断 s2 是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。

这个思路，避免了反复“倒”栈，仅在需要时才“倒”一次。