Start learning free

LESSON 413 OF 573 · STACK

Implement Queue Using Stacks in Go: Amortized O(1) with Two Stacks

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 12
    Ctrl + Enter to check

    GO · STACK

    Implement Queue Using Stacks in Go, explained

    Problem overview

    A queue hands its values back in the order they arrived: the first value pushed is the first to leave, like a line at a shop. A stack does the opposite: the last value pushed leaves first. The lesson asks for a queue built 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 MyQueue struct has Constructor, which creates an empty queue, Push(x), which adds x at the back, Peek(), which returns the front value without removing it, Pop(), which removes the front value and returns it, and Empty(), which reports whether the queue holds no values. Pop and Peek are only called on a non-empty queue.

    In the first example, after Push(1) and Push(2), Peek() returns 1 and Pop() returns 1, because 1 arrived first. Then Empty() is false, since 2 is still in the queue.

    Approach: two stacks that reverse each other's order

    Moving one stack onto another reverses the order of its values: the top of the first stack lands at the bottom of the second. Doing this twice restores the original order. That is the trick behind the design.

    New values are pushed on inStack, so the newest value is on top and the oldest is at the bottom. A queue needs the oldest value first. When the front is needed, the values are moved from inStack one by one onto outStack. The oldest value, which was at the bottom of inStack, is moved last and ends up on top of outStack, where it can be read or removed.

    The key rule is to 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 of the queue. Moving more values on top of it would put newer values in front of older ones.

    The simple alternative is to move everything from one stack to the other and back again on every operation. That costs O(n) per call, where n is the number of values in the queue. With the rule above, each operation takes O(1) time amortized: one call may move many values, but the work averages out.

    The reason is to count the moves of a single value. A value is pushed onto inStack once, moved to outStack at most once and popped at most once. A value on outStack never goes back. So n operations make at most n moves in total, plus the pushes and pops: O(n) altogether, which is O(1) per operation on average. As a check, 1,000 pushes, 500 pops, 500 more pushes and 1,000 more pops make 3,000 operations and move 1,500 values, one for each value pushed.

    Step by step

    1. Declare inStack as a []int. The top of a stack is the end of the slice, because append and reslicing both work at the end.
    2. Declare outStack as a []int too. Its values are already in leaving order, oldest on top.
    3. Return MyQueue{} from Constructor. Both slices start as nil, and append and len work on a nil slice.
    4. In Push, append x to this.inStack and store the result back.
    5. In Peek, test whether this.outStack is empty with len(this.outStack) == 0. Only then do values need to move.
    6. Loop while this.inStack has values. Every value must move, so that the oldest, at the bottom, ends up on top of this.outStack.
    7. Move the top value: append the last element of this.inStack to this.outStack, then drop it from this.inStack by reslicing to len - 1.
    8. After the if, return the last element of this.outStack. Whether or not values just moved, the oldest value in the queue is on top. Reading it removes nothing.
    9. In Pop, call this.Peek() and keep the result in front. Peek already moves values if needed and finds the front.
    10. Drop the top of this.outStack by reslicing it to len - 1.
    11. Return front, read before it was removed.
    12. In Empty, return whether both stacks are empty, joined with &&: the queue's values are split between the two stacks.

    The solution in Go

    type MyQueue struct {
    inStack []int
    outStack []int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (this *MyQueue) Push(x int) {
    this.inStack = append(this.inStack, x)
}

func (this *MyQueue) Peek() int {
    if len(this.outStack) == 0 {
        for len(this.inStack) > 0 {
            this.outStack = append(this.outStack, this.inStack[len(this.inStack)-1])
            this.inStack = this.inStack[:len(this.inStack)-1]
        }
    }
    return this.outStack[len(this.outStack)-1]
}

func (this *MyQueue) Pop() int {
    front := this.Peek()
    this.outStack = this.outStack[:len(this.outStack)-1]
    return front
}

func (this *MyQueue) Empty() bool {
    return len(this.inStack) == 0 && len(this.outStack) == 0
}

    The Go details worth a closer look:

    • A slice as a stack. Go has no stack type. append(s, x) pushes, s[len(s)-1] reads the top and s[:len(s)-1] pops. Each of these is O(1).
    • Pointer receivers. All the methods that change a slice need *MyQueue. Pop calls this.Peek() directly, since this already is the pointer.
    • Nil slices. MyQueue{} has two nil slices, which behave as empty stacks.
    • Go has no while. The inner for with only a condition repeats while the condition holds.

    Complexity

    Time: amortized O(1) per operation. Push, Empty and the final read in Peek are constant time. A single Peek or Pop can take O(n) when it moves all the values, but each value is moved at most once in its life, so a sequence of n operations takes O(n) in total.

    Space: O(n) for the n values in the two stacks.

    Edge cases and common mistakes

    • Moving while outStack still has values. After Push(1), Push(2), Pop() (which returns 1 and leaves 2 on outStack) and Push(3), moving 3 on top of 2 would make the next Pop return 3. The correct answers are 2, then 3.
    • A new queue. Empty() is true. After Push(7) it is false, and after Pop() returns 7 it is true again.
    • Checking only one stack in Empty. Values can be in either stack, so both must be empty.
    • Forgetting that Peek moves values. It changes the stacks without changing the queue, which is fine.

    Testing

    Starting with an empty queue, push 1, 2 and 3: inStack is [1 2 3] and outStack is empty. After Peek() returns 1, inStack is empty and outStack is [3 2 1], with the oldest value on top. Pop() then returns 1, and Empty() returns false. After Push(4), inStack is [4] and outStack is [3 2], and three pops return 2, 3, 4, after which Empty() returns true.

    The second example's sequence Push(1), Push(2), Pop(), Push(3), Peek(), Pop(), Pop(), Empty() gives 1, 2, 2, 3, true.

    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free