Start learning free

LESSON 409 OF 569 · STACK

Implement Queue Using Stacks in JavaScript: Two Stacks, 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

    JAVASCRIPT · STACK

    Implement Queue Using Stacks in JavaScript, explained

    Problem overview

    A queue returns values in the order they arrived: the first value pushed is the first to leave. A stack does the opposite, with the last value pushed leaving first. The task is to build a queue out of 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 MyQueue has four methods. push(x) adds x at the back. peek() returns the front value without removing it. pop() removes the front value and returns it. empty() returns whether the queue holds no values. The constraints promise that pop and peek are only called when the queue is not empty.

    The first example: push 1, push 2, then peek(), pop() and empty(). They return:

    1 1 false

    1 arrived first, so it is at the front: peek() shows it, pop() removes it. The 2 is still inside, so empty() is false.

    Approach: one stack to receive, one stack to give back

    In JavaScript an array works as a stack: push and pop both act on its end, the top. A single stack hands back the newest value first, which is the wrong end. The fix uses a property of stacks: moving values one by one from one stack onto another reverses their order.

    So the class keeps two arrays. inStack receives every pushed value. outStack is where values leave from. When the front is needed and outStack is empty, every value is popped from inStack and pushed onto outStack. The newest value moves first and ends deepest; the oldest moves last and ends on top. The top of outStack is now the front of the queue.

    The important rule: move values only when outStack is empty. While it still holds values, they all arrived before anything in inStack, so its top is still the front. Moving earlier would put newer values under older ones and break the order.

    A run with the numbers 1, 2, 3 pushed, then peek(), then 4 pushed, then four pops (the arrays are printed with the top at the end):

    after push 1, 2, 3:  inStack [1,2,3]  outStack []
peek() => 1:         inStack []       outStack [3,2,1]
after push 4:        inStack [4]      outStack [3,2,1]
pop() => 1:          inStack [4]      outStack [3,2]
pop() => 2:          inStack [4]      outStack [3]
pop() => 3:          inStack [4]      outStack []
pop() => 4:          empty() is true

    Notice that 4 stayed in inStack until the 3 had left, which is exactly the queue order. The last pop found outStack empty, so it moved the 4 over first.

    Why it is O(1) amortized

    A single peek or pop can be slow, because it may move every value in inStack. But each value is moved from inStack to outStack at most once: after that it only leaves. So a value costs at most three steps in its whole life: one push, one move, one pop. Over n operations the total work is O(n), which makes the average cost per operation constant. That is what "amortized O(1)" means. In a run with 200,000 pushes and 200,000 pops, mixed so that the queue was refilled and emptied many times, the number of values moved was exactly 200,000, one per pushed value.

    Moving everything over and back again on every pop would instead cost O(n) per call.

    Step by step

    1. Constructor: set this.inStack to an empty array. Values go on top of it, with the top at the end of the array.
    2. Set this.outStack to an empty array, the stack values leave from. Values in it are already in leaving order, the oldest on top.
    3. push: push x onto this.inStack. A new value joins the back of the queue.
    4. peek: write an if for when this.outStack is empty (its length is 0).
    5. Inside it, write a while loop that runs while this.inStack has values (its length is above 0).
    6. In the loop, pop the top of this.inStack and push it onto this.outStack, in one line. Each value is moved at most once.
    7. After the if, return the top of this.outStack: its last element, at index this.outStack.length - 1. Reading it removes nothing.
    8. pop: call this.peek() and store the result in front. peek already moves values when needed and finds the front, so pop does not repeat that.
    9. Pop the top of this.outStack, which removes the front value of the queue.
    10. Return front, read before the removal.
    11. empty: return whether both this.inStack.length and this.outStack.length are 0, joined with &&. The queue's values are split across the two stacks, so it is empty only when both are.

    The solution in JavaScript

    class MyQueue {
    constructor() {
        this.inStack = [];
        this.outStack = [];
    }

    push(x) {
        this.inStack.push(x);
    }

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

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

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

    JavaScript details:

    • An array as a stack. push adds at the end and pop removes from the end and returns it. Using shift or unshift would work at the front, which is a different thing and not what a stack does.
    • Reading the top. The top is arr[arr.length - 1]. JavaScript does not throw for a missing index but returns undefined, which is why the lesson's guarantee that peek and pop are called on a non-empty queue matters.
    • Methods calling methods. pop calls this.peek(). Without the this. the call would look for a function called peek outside the class and fail.
    • === in empty. It compares numbers without converting types, and && returns a real boolean here because both sides are comparisons.

    Complexity

    Time: push and empty are O(1). peek and pop are O(1) amortized: a call that moves k values costs O(k), but each value is moved once, so n operations cost O(n) in total.

    Space: O(n) for the n values held, split between the two arrays. No value is stored twice at the same time.

    Edge cases and common mistakes

    • Moving when outStack is not empty. In the second example, after push(1), push(2) and pop(), the 2 sits in outStack. Then push(3) goes to inStack. Moving the 3 over the 2 would make the next peek() return 3 instead of 2. The expected output is 1 2 2 3 true.
    • Moving back. Never move values from outStack back to inStack. The oldest values are already in the right order, and moving them again costs time.
    • Checking only one stack in empty. After peek() has moved everything, inStack is empty but the queue is not. Both lengths must be 0.
    • A new queue. empty() on a new queue is true. After push(7) it is false, and after pop() returns 7 it is true again, which gives true false 7 true.
    • Duplicating the move logic. pop reuses peek. Copying the loop into both methods invites the two copies to drift apart.

    Testing

    Outputs of the solution above:

    • push 1, push 2, then peek(), pop(), empty() return 1 1 false.
    • push 1, push 2, pop(), push 3, peek(), pop(), pop(), empty() return 1 2 2 3 true.
    • empty(), push 7, empty(), pop(), empty() return true false 7 true.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free