Start learning free

LESSON 413 OF 573 · STACK

Implement Queue Using Stacks in TypeScript: Amortized O(1)

Practice O(1) amortized Read the full explanation

A queue hands its values back in the order they arrived, like a line at a shop: the first value pushed is the first one to leave. A stack does the opposite: the last value pushed leaves first. Build a queue out of two stacks, using only what a stack can do: add a value on top, look at or remove the top value, and check whether it is empty.

Implement the class MyQueue:

  • MyQueue() creates an empty queue.
  • push(x) adds the integer x at the back of the queue.
  • peek() returns the value at the front of the queue, without removing it.
  • pop() removes the value at the front of the queue and returns it.
  • empty() returns true if the queue holds no values, and false otherwise.

The input is a list of operations, applied in order to one new MyQueue. The output lists what the peek, pop and empty calls return, in order. The starter code spells these names the way your language does.

 

Example 1:

Input:
    push(1)
    push(2)
    peek()
    pop()
    empty()
Output: 1 1 false
Explanation:
1 arrived first, so it is at the front: peek() returns 1, and pop() removes it and returns it.
2 is still in the queue, so empty() is false.

Example 2:

Input:
    push(1)
    push(2)
    pop()
    push(3)
    peek()
    pop()
    pop()
    empty()
Output: 1 2 2 3 true
Explanation:
pop() returns 1, the first value pushed. 3 arrives next, but 2 has been waiting longer,
so peek() and the next pop() return 2, and only then does pop() return 3. The queue is empty again.

Example 3:

Input:
    empty()
    push(7)
    empty()
    pop()
    empty()
Output: true false 7 true
Explanation: A new queue is empty. After push(7) it isn't, and after pop() returns 7 it is empty again.

 

Constraints:

  • 1 <= x <= 109
  • pop and peek are only called when the queue is not empty.
  • At most 2 * 105 calls in total are made to push, pop, peek and empty.

Note:

Each operation should take O(1) time amortized: one pop or peek may have to move many values from one stack to the other, but each value is moved at most once, so n operations take O(n) time in total. Moving all the values over and back again on every pop would take O(n) time per call, where n is the number of values in the queue.

STEP 1 OF 11
    Ctrl + Enter to check

    TYPESCRIPT · STACK

    Implement Queue Using Stacks in TypeScript, explained

    Problem overview

    A queue gives values back in the order they arrived, like a line at a shop. A stack does the opposite: the last value pushed leaves first. The task is to build a queue from two stacks, using only what a stack can do: add on top, look at or remove the top, and check whether it is empty. The class is MyQueue:

    • push(x) adds x at the back of the queue.
    • peek() returns the front value without removing it.
    • pop() removes the front value and returns it.
    • empty() returns whether the queue holds no values.

    After push(1) and push(2), the calls peek(), pop() and empty() return 1, 1 and false: 1 arrived first, so it is at the front, and 2 is still inside. In a longer run, push(1) and push(2) are followed by pop(), which returns 1, then push(3). The calls peek(), pop(), pop() and empty() then return 2 2 3 true: value 2 has waited longer than 3, so it leaves first.

    Approach: reverse once, and only when needed

    Pushing onto a stack puts a value on the top, but the queue needs the oldest value, which is at the bottom. Moving all values from one stack to another reverses their order: the newest goes first and lands deepest, the oldest goes last and lands on top.

    The simple way keeps everything in one stack and, on each pop, moves all values to a second stack, takes the bottom one, and moves everything back. That is O(n) per call, where n is the number of values in the queue.

    The better idea avoids moving back. Use two stacks with separate jobs:

    • inStack takes every pushed value. Its top is the newest value.
    • outStack gives values back. Its top is the oldest value, so it is the front of the queue.

    Only when outStack is empty and the front is needed, move everything from inStack to outStack. While outStack still has values, they all arrived before anything in inStack, so its top is still the front. After 1, 2, 3 are pushed, inStack is [1, 2, 3] and outStack is []. After a peek() they are [] and [3, 2, 1], with 1 on top (the end of the array). Pushing 4 then puts it in inStack, giving [4] and [3, 2, 1], and four pop() calls return 1, 2, 3, 4 in that order.

    Why it is O(1) amortized

    A single pop or peek can move many values, so one call can take O(n). But count the moves per value instead of per call. A value is pushed onto inStack once, moved to outStack at most once, and popped from outStack once. It never goes back. So a value costs at most three stack operations in its life, and n operations cost O(n) in total: O(1) per operation on average, which is what "amortized" means. A run that pushes 1 to 1000 and pops all 1000 values makes exactly 1000 moves onto outStack, one per value, and pops them in the order 1 to 1000 (their sum is 500500).

    Step by step

    1. Declare inStack as a number[], set to an empty array. An array's push and pop work at its end, so the end is the top of the stack.
    2. Declare outStack the same way.
    3. push(x): push x onto this.inStack.
    4. peek, the condition: start an if for when this.outStack.length === 0. Moving happens only then.
    5. The loop: inside it, while (this.inStack.length > 0), since every value of inStack has to move for the oldest to reach the top.
    6. The move: this.outStack.push(this.inStack.pop()) in one line. This reverses the order.
    7. Read the front: after the if, return this.outStack[this.outStack.length - 1], the top of outStack. Reading removes nothing.
    8. pop: call this.peek() and keep the result in front, because peek already does the moving and finds the front.
    9. Remove it: this.outStack.pop().
    10. Return front.
    11. empty: return this.inStack.length === 0 && this.outStack.length === 0. The values are split between the two stacks, so the queue is empty only when both are.

    The solution in TypeScript

    class MyQueue {
    inStack: number[] = [];
    outStack: number[] = [];

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

    peek(): number {
        if (this.outStack.length === 0) {
            while (this.inStack.length > 0) {
                this.outStack.push(this.inStack.pop());
            }
        }
        return this.outStack[this.outStack.length - 1];
    }

    pop(): number {
        let front: number = this.peek();
        this.outStack.pop();
        return front;
    }

    empty(): boolean {
        return this.inStack.length === 0 && this.outStack.length === 0;
    }
}

    Details:

    • A TypeScript array works as a stack with push and pop at the end, and reading the top is arr[arr.length - 1]. Array shift() and unshift() work at the front and aren't part of what the problem allows.
    • Array.prototype.pop() is typed as returning number | undefined in strict mode; the lesson compiles with strict checks off, so this.outStack.push(this.inStack.pop()) is accepted.
    • A method calls another method of the same object through this, as pop does with this.peek().
    • The lesson's tests print booleans as True/False; in the class, empty() returns the real true or false.

    Complexity

    Each operation is O(1) amortized, by the counting argument above; the worst single call, a peek or pop that moves all n values, is O(n). Space is O(n) for the n values in the two stacks.

    Edge cases and common mistakes

    • Moving when outStack isn't empty. The older values in outStack would end up under the newer ones, and the order would break. In the second example, after pop() returns 1, value 2 is in outStack; pushing 3 must not touch it, so peek() still returns 2.
    • Moving back after each pop. That works but makes every call O(n).
    • empty() checking one stack. After push(7) alone, outStack is empty but the queue is not.
    • A new queue. empty() is true; after push(7) it is false, and after pop() returns 7 it is true again.
    • Peeking an empty queue. The lesson never does this; the class would return undefined.
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free