Implement Stack using Queues

The key idea

Problem

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

- void push(int x) Pushes element x onto the top of the stack.
- int pop() Removes the element on the top of the stack and returns it.
- int top() Returns the element on the top of the stack.
- boolean empty() Returns true if the stack is empty, false otherwise.

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size, and is empty operations are valid. Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Follow-up: Can you implement the stack using only one queue?

Constraints

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.
• You must use only standard queue operations: push to back, peek/pop from front, size, and is-empty.

Examples

Complexity

Time: O(n) push, O(1) pop/top (push-costly variant) Space: O(n)

More Design problems

• Binary Search Tree IteratorMEDIUM
• Design Circular QueueMEDIUM
• Design HashMapEASY
• Design HashSetEASY
• Design TwitterMEDIUM
• Detect SquaresMEDIUM
• Encode and Decode StringsMEDIUM
• Implement Queue using StacksEASY
• Insert Delete GetRandom O(1)MEDIUM
• LFU CacheHARD
• LRU CacheMEDIUM
• Maximum Frequency StackHARD