问题
使用队列实现栈的下列操作:
push(x) — 元素 x 入栈
pop() — 移除栈顶元素
top() — 获取栈顶元素
empty() — 返回栈是否为空
注意:
你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。
Implement the following operations of a stack using queues.
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
empty() — Return whether the stack is empty.
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // returns 2
stack.pop(); // returns 2
stack.empty(); // returns false
Notes:
You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
示例
public class Program { public static void Main(string[] args) { var stack = new MyStack(); stack.Push(1); stack.Push(2); stack.Push(3); Console.WriteLine(stack.Pop()); Console.WriteLine(stack.Pop()); Console.WriteLine(stack.Pop()); Console.WriteLine(stack.Empty()); Console.ReadKey(); } public class MyStack { private Queue<int> _queue = null; public MyStack() { _queue = new Queue<int>(); } public void Push(int x) { //基本思路是反转原队列 var queue = new Queue<int>(); queue.Enqueue(x); foreach(var elemet in _queue) { queue.Enqueue(elemet); } _queue = queue; } public int Pop() { return _queue.Dequeue(); } public int Top() { return _queue.First(); } public bool Empty() { return !_queue.Any(); } } }
以上给出1种算法实现,以下是这个案例的输出结果:
3 2 1 True
分析:
显而易见,Push 的时间复杂度应当为: ,其它方法的时间复杂度应当为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4106。