C# 使用堆栈实现队列

232 使用堆栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（、、、）：pushpoppeekempty

实现类：MyQueue

void push(int x)将元素 x 推到队列的末尾
int pop()从队列的开头移除并返回元素
int peek()返回队列开头的元素
boolean empty()如果队列为空，返回；否则，返回truefalse
说明：

你只能使用标准的栈操作 —— 也就是只有 , , , 和操作是合法的。push to toppeek/pop from topsizeis empty
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用次、、和100pushpoppeekempty
假设所有操作都是有效的（例如，一个空的队列不会调用或者操作）poppeek

解决方案：

提供思路

将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop和 peek操作。

每次 pop 或 peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

上代码：

public class MyQueue
{
    Stack<int> inStack;
    Stack<int> outStack;

    public MyQueue()
    {
        inStack = new Stack<int>();
        outStack = new Stack<int>();
    }

    public void Push(int x)
    {
        inStack.Push(x);
    }

    public int Pop()
    {
        if (outStack.Count == 0)
        {
            In2Out();
        }
        return outStack.Pop();
    }

    public int Peek()
    {
        if (outStack.Count == 0)
        {
            In2Out();
        }
        return outStack.Peek();
    }

    public bool Empty()
    {
        return inStack.Count == 0 && outStack.Count == 0;
    }

    private void In2Out()
    {
        while (inStack.Count > 0)
        {
            outStack.Push(inStack.Pop());
        }
    }
}