Question

LeetCode Link | 225. Implement Stack using Queues | Easy

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 to 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.

Notes:

  • 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?

Constrains

  • 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.

Examples

Example 1

Input
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation

1
2
3
4
5
6
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Solution Approach

Method: Manual / Simulate

Constrains

  • None

This method does not have any limitations.

Concept Explanation

If you have solve question 232. Implement Queue using Stacks, you might think of using a input stack and a output stack to simulate the functionality of queue. However, this won’t work if you spend few minutes.

To simulate stack using queue, only one queue is enough. When simulate stack popping using a queue, simply re-add all the elements from the front of the queue (except for the last element) back to the end of the queue (like rotate one number from left to right). When you then pop an element, it will follow the order of a stack.

Example

Code

  • Time complexity:

    • pop: O(n)
    • Other: O(1)

  • Space complexity: O(n)

TypeScript

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MyStack {
    private queue: number[];

    constructor() {
        this.queue = [];
    }

    push(x: number): void {
        this.queue.push(x);
    }

    pop(): number {
        // Rotate 1 number from left to right: 1,2,3 -> 3,1,2
        for (let i = 0; i < this.queue.length - 1; i++) {
            this.queue.push(this.queue.shift()!);
        }
        // return 3, queue: 1, 2
        return this.queue.shift()!;
    }

    top(): number {
        let res: number = this.pop();
        this.queue.push(res);
        return res;
    }

    empty(): boolean {
        return this.queue.length === 0;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */

Conclusion

Some people might wonder about the practical engineering significance of such problems. In fact, many algorithm problems are more about testing knowledge points and have a greater educational value than practical engineering significance. This is also true for interview questions!