225.用队列实现栈

发表于 更新于 分类于 ，

题目

使用队列实现栈的下列操作：

  • push(x) -- 元素 x 入栈
  • pop() -- 移除栈顶元素
  • top() -- 获取栈顶元素
  • empty() -- 返回栈是否为空

注意:

  • 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
  • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
  • 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

思路

用队列实现栈方法比较简单.栈的每一个出栈元素都是最后的元素,但是队列的出队元素是第一个元素,所以要做的就是设法将队列每一个入队的元素移到队头.

所以要做的就是每当有一个元素入队,就将队列里在它前面的元素全部出队一次再入队一次.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class MyStack
{
    Queue<int> queue = new Queue<int>();
    public MyStack() { }
    public void Push(int x)
    {
        queue.Enqueue(x);
        for (int i = 0; i < queue.Count - 1; i++)
        {
            queue.Enqueue(queue.Dequeue());
        }
    }
    public int Pop()
    {
        return queue.Dequeue();
    }
    public int Top()
    {
        return queue.Peek();
    }
    public bool Empty()
    {
        return queue.Count > 0 ? false : true;
    }
}