Problem 232: Implement Queue using Stacks

Question

LeetCode Link | 232. Implement Queue using Stacks | Easy

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

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

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Constrains

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

Examples

Example 1

Input
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Solution Approach

Method: Manual / Simulate

Constrains

• None

This method does not have any limitations.

Concept Explanation

This is a simulation problem, not involving specific algorithms, but testing the understanding of stacks and queues.

To simulate the behavior of a queue using stacks, a single stack alone will not suffice. Therefore, two stacks are needed: one input stack and one output stack. It is important to understand the relationship between the input stack and the output stack.

Below is an animation simulating the execution process of the queue:

queue.push(1);
queue.push(2);
queue.pop();
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();
queue.pop();
queue.empty();

Code

• Time complexity:

  • push & empty: O(1)
  • pop & peek: O(n)

• Space complexity: O(1)

TypeScript

class MyQueue {
    private stackIn: number[];
    private stackOut: number[];

    constructor() {
        this.stackIn = [];
        this.stackOut = [];
    }

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

    pop(): number {
        if (this.stackOut.length === 0) {
            while (this.stackIn.length > 0) {
                this.stackOut.push(this.stackIn.pop());
            }
        }
        return this.stackOut.pop();
    }

    peek(): number {
        let output: number = this.pop();
        this.stackOut.push(output);
        return output;
    }

    empty(): boolean {
        return this.stackIn.length === 0 && this.stackOut.length === 0;
    }
}

Conclusion

It can be seen that the implementation of the peek() function directly reuses the pop() function. Otherwise, the logic for checking if stackOut is empty would have to be rewritten.

To expand on some habits in code development, in industrial-level coding, one of the biggest no-nos is to implement a similar function by simply copying and modifying the existing code.

This approach can lead to increasingly disorganized project code. It is crucial to understand the importance of reuse. Functions with similar functionality should be abstracted out, and extensive copying and pasting should be avoided as it can easily lead to problems!