Start learning free

LESSON 413 OF 573 · STACK

Implement Queue Using Stacks in Scala: 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 11
    Ctrl + Enter to check

    SCALA · STACK

    Implement Queue Using Stacks in Scala, explained

    Problem overview

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

    The class MyQueue has four methods:

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

    pop and peek are only called when the queue is not empty. Each operation must take O(1) time amortized.

    Example: after push(1) and push(2), peek() returns 1 and pop() returns 1, and empty() is then false, because 2 is still waiting.

    Approach

    The simple way and its cost

    Use one stack for everything. A push goes on top. The front of the queue, however, is at the bottom, so every pop would have to move all the values to a second stack, take the bottom one, and move everything back. That is O(n) work per call, where n is the number of values in the queue.

    Two stacks, with the order reversed once

    Moving values from one stack to another reverses their order. If values 1, 2, 3 were pushed in that order, 3 is on top of the first stack. Popping them one by one onto a second stack puts 3 at the bottom and 1 on top. Now the oldest value is on top and a pop gives 1, which is what a queue needs.

    So the class has:

    • inStack, where every pushed value goes. Its top is the newest value.
    • outStack, where values leave from. Its top is the oldest value that is still in the queue.

    The central rule: move values only when outStack is empty, and then move all of them. While outStack still holds values, all of them arrived before anything in inStack, so its top is still the front. Moving more values on top of them would put newer values in front of older ones and break the order.

    A picture of the stacks (the top is written first):

    after push 1, 2, 3:   in Stack(3, 2, 1)   out Stack()
after peek():         in Stack()          out Stack(1, 2, 3)
after push 4:         in Stack(4)         out Stack(1, 2, 3)

    Then four pops return 1, 2, 3, 4: the first three come from outStack, and the fourth finds it empty and moves 4 over first.

    Why it is amortized O(1)

    One peek or pop may move many values, so a single call can be slow. But count the moves per value instead of per call. A value is pushed on inStack once, moved to outStack at most once, and popped from outStack once. That is at most three stack operations per value in its whole life. So n operations cost O(n) in total, and the average per operation, the amortized cost, is O(1).

    Counting the moves in a run bears this out: pushing 100,000 values and then popping all of them makes exactly 100,000 moves, one per value, not 100,000 times 100,000.

    Step by step

    1. Declare inStack, a val holding a new, empty scala.collection.mutable.Stack[Int](). Every pushed value goes on top of it.
    2. Declare outStack the same way: the stack the values leave from.
    3. In push, call inStack.push(x).
    4. In peek, start an if for when outStack.isEmpty.
    5. Inside it, loop while inStack.nonEmpty.
    6. Move one value per pass: outStack.push(inStack.pop()). The newest value leaves inStack first and lands deepest in outStack; the oldest leaves last and ends on top.
    7. After the if, return outStack.top. Whether or not values were just moved, the oldest value is on top, and top removes nothing.
    8. In pop, call peek() and store the result in front. It moves the values if needed and finds the front, so pop does not repeat that.
    9. Remove the top of outStack with outStack.pop().
    10. Return front, which was read before it was removed.
    11. In empty, return inStack.isEmpty && outStack.isEmpty. The values are split between the stacks, so the queue is empty only when both are.

    The solution in Scala

    class MyQueue {
    val inStack = scala.collection.mutable.Stack[Int]()
    val outStack = scala.collection.mutable.Stack[Int]()

    def push(x: Int): Unit = {
        inStack.push(x)
    }

    def peek(): Int = {
        if (outStack.isEmpty) {
            while (inStack.nonEmpty) {
                outStack.push(inStack.pop())
            }
        }
        return outStack.top
    }

    def pop(): Int = {
        val front = peek()
        outStack.pop()
        return front
    }

    def empty(): Boolean = {
        return inStack.isEmpty && outStack.isEmpty
    }
}

    Using the class on the second example:

    val q = new MyQueue
q.push(1)
q.push(2)
println(q.pop())
q.push(3)
println(q.peek())
println(q.pop())
println(q.pop())
println(q.empty())

    1
2
2
3
true

    Scala details:

    • scala.collection.mutable.Stack. It has push, pop(), top, isEmpty and nonEmpty. Its string form lists the top first, as in the picture above.
    • pop() and push(...) return values. pop() returns the removed value, and in pop of the queue its result is dropped on purpose, because front already holds it. push returns the stack itself, but the queue's push is declared Unit, so the result is thrown away.
    • Methods call each other by name. Inside the class, pop calls peek() with no prefix.
    • Empty-parentheses methods. The methods are declared with (), such as def peek(): Int, and called as q.peek().
    • Using a val for a mutable stack. val fixes which stack object the name refers to; the stack's contents still change.

    Complexity

    Time. push, empty and a peek or pop that finds outStack non-empty are O(1). A peek or pop that finds it empty moves every value of inStack, which is O(n) for that single call. Each value moves at most once, so a sequence of n operations costs O(n) in total: O(1) amortized per operation.

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

    Edge cases and common mistakes

    • Moving values when outStack is not empty. Pushing 1 and 2, popping once, then pushing 3 shows the problem. If every peek moved the values of inStack on top of outStack, the pops would return 1, 3 and 2 instead of 1, 2 and 3. The if (outStack.isEmpty) test prevents it.
    • Moving only part of inStack. Moving the whole stack at once keeps the oldest value on top of outStack. A partial move leaves the order wrong.
    • Checking only one stack in empty. After push(7) the value sits in inStack and outStack is empty; after peek() it is the other way round. Both checks are needed.
    • Doing peek's work twice in pop. Calling peek() first makes sure outStack has the front on top, so outStack.pop() removes the right value.
    • Popping an empty queue. top on an empty stack throws NoSuchElementException. The statement promises that pop and peek are never called on an empty queue.
    • Using top as if it removed. top reads and leaves the value in place. Only pop() removes.

    Testing

    • Push 1, push 2, then peek(), pop(), empty() give 1, 1, false.
    • Push 1, push 2, pop(), push 3, peek(), pop(), pop(), empty() give 1, 2, 2, 3, true.
    • On a new queue: empty(), push 7, empty(), pop(), empty() give true, false, 7, true.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free