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`

, 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).

Update (2015-06-11):

The class name of the Java function had been updated to MyStack instead of Stack.

The class name of the Java function had been updated to MyStack instead of Stack.

**Understand the problem:**

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