mplement 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.
- You must use only standard operations of a queue -- which means only
push to back
,peek/pop from front
,size
, andis 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).
Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.
Understand the problem:The class name of the Java function had been updated to MyStack instead of Stack.
We can use two queues, queue1 and queue2.
-- push(x), push x into queue1. Time complexity O(1)
-- pop(), dequeue all n - 1 elements and enqueue into queue2. dequeue the last element.
Swap queue1 and queue2. Time complexity O(n).
-- top() dequeue all n - 1 elements and enqueue into queue2, dequeue the last element and save the as return, then enqueue it into queue2. Swap queue1 and queue2. Time complexity is O(n).
-- empty(), check if queue1 is empty.
Code (Java):
class MyStack { private Queue<Integer> queue1; private Queue<Integer> queue2; public MyStack() { this.queue1 = new LinkedList<Integer>(); this.queue2 = new LinkedList<Integer>(); } // Push element x onto stack. public void push(int x) { queue1.offer(x); } // Removes the element on top of the stack. public void pop() { while (queue1.size() > 1) { queue2.offer(queue1.poll()); } queue1.poll(); // Swap queue1 and queue2 Queue<Integer> temp = queue1; queue1 = queue2; queue2 = temp; } // Get the top element. public int top() { while (queue1.size() > 1) { queue2.offer(queue1.poll()); } int ret = queue1.poll(); queue2.offer(ret); // Swap queue 1 and queue2 Queue<Integer> temp = queue1; queue1 = queue2; queue2 = temp; return ret; } // Return whether the stack is empty. public boolean empty() { return queue1.isEmpty(); } }
No comments:
Post a Comment