Start learning free

LESSON 413 OF 573 · STACK

Implement Queue Using Stacks in Kotlin: 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

    KOTLIN · STACK

    Implement Queue Using Stacks in Kotlin, explained

    Problem overview

    You write a class MyQueue that behaves like a queue, but may only use stacks. push(x) adds x at the back, peek() returns the front value without removing it, pop() removes and returns the front value, and empty() says whether the queue holds nothing. A queue gives values back in arrival order; a stack gives back the newest first. The stacks may only add on top, look at or remove the top, and check for emptiness.

    In the second example, push 1 and 2, then pop() returns 1. Push 3, and peek() and the next pop() both return 2, because 2 has been waiting longer than 3. The following pop() returns 3, and empty() is then true. pop and peek are only called when the queue is not empty.

    Approach

    One stack is not enough: the oldest value is at the bottom, out of reach. A first idea uses two stacks and moves everything between them on every pop: empty the first stack onto the second to reach the bottom value, remove it, then move everything back. That takes O(n) per pop.

    The better idea notices that moving values from one stack onto another reverses their order. If values 1, 2, 3 were pushed onto inStack, with 3 on top, popping them one by one onto outStack leaves 1 on top there. So outStack has the values in queue order, oldest on top. The design is:

    • push always goes onto inStack.
    • When the front is needed and outStack is empty, move all of inStack over to outStack. If outStack still has values, do not move anything: they all arrived before everything in inStack, so the top of outStack is already the front.
    • The front is the top of outStack.

    Moving back is never needed. A value in outStack leaves from there, and new values wait in inStack until outStack runs dry.

    Why it is amortized O(1)

    A single pop or peek can move many values, so it can take O(n). But count the moves per value instead of per call. Each value is pushed onto inStack once, moved to outStack at most once (values never go back), and removed from outStack at most once. That is at most three stack operations per value, however long it stays in the queue. So n operations cost O(n) in total, which is O(1) per operation on average. That's what "amortized" means.

    Step by step

    1. Two stacks. Declare inStack and outStack as empty ArrayDeque<Int>(). The end of the deque is the top of the stack: addLast, last() and removeLast() all work there.
    2. push. inStack.addLast(x).
    3. peek. If outStack.isEmpty(), loop while inStack.isNotEmpty() and move each value with outStack.addLast(inStack.removeLast()). The newest lands deepest and the oldest lands on top.
    4. Return the top of outStack with last(). Reading removes nothing.
    5. pop. Call peek() and keep its answer in front: it moves values if needed and finds the front, so pop doesn't repeat that. Then outStack.removeLast() and return front.
    6. empty. The values are split between the stacks, so the queue is empty only if both are: inStack.isEmpty() && outStack.isEmpty().

    The solution in Kotlin

    class MyQueue {
    val inStack = ArrayDeque<Int>()
    val outStack = ArrayDeque<Int>()

    fun push(x: Int) {
        inStack.addLast(x)
    }

    fun peek(): Int {
        if (outStack.isEmpty()) {
            while (inStack.isNotEmpty()) {
                outStack.addLast(inStack.removeLast())
            }
        }
        return outStack.last()
    }

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

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

    Kotlin details worth knowing:

    • ArrayDeque is Kotlin's own. Without an import it is kotlin.collections.ArrayDeque, a growable array that works at both ends. Used only at its end, it behaves as a stack.
    • The deque is also a queue. Kotlin's ArrayDeque also has removeFirst(), so a real queue would be one line. This exercise forbids it: the point is to build the behaviour from stack operations alone.
    • last() and removeLast() throw on an empty deque (NoSuchElementException). The code never calls them on an empty outStack, because pop and peek are only called on a non-empty queue.
    • Calling a sibling method. Inside the class, peek() in pop is a call on the same object. No this. is needed.
    • && short-circuits. If inStack isn't empty, empty() returns false without looking at the second stack.

    Seeing it run

    This code pushes three values and prints both stacks (the last number is the top) after the operations:

    fun main() {
    val queue = MyQueue()
    queue.push(1)
    queue.push(2)
    queue.push(3)
    println("in = ${queue.inStack}, out = ${queue.outStack}")
    println(queue.peek())
    println("in = ${queue.inStack}, out = ${queue.outStack}")
    println(queue.pop())
    queue.push(4)
    println("in = ${queue.inStack}, out = ${queue.outStack}")
    println(queue.pop())
    println(queue.pop())
    println("in = ${queue.inStack}, out = ${queue.outStack}")
    println(queue.pop())
    println(queue.empty())
}

    It prints:

    in = [1, 2, 3], out = []
1
in = [], out = [3, 2, 1]
1
in = [4], out = [3, 2]
2
3
in = [4], out = []
4
true

    After three pushes everything sits in inStack. The first peek() moves all three values over, and 1 ends up on top of outStack. After pop() returns 1 and 4 is pushed, 4 waits in inStack while 2 and 3 leave from outStack. Only when outStack is empty does the next pop() move 4 across and return it. Values leave in the order 1, 2, 3, 4, the order they were pushed.

    Complexity

    • Time: push and empty are O(1). peek and pop are O(1) amortized, and O(n) in the worst single call, when outStack is empty and all n values move. Over any sequence of operations, each value is moved at most once, so the total is proportional to the number of operations.
    • Space: O(n) for n values in the queue.

    Edge cases and common mistakes

    • Moving while outStack still has values. The new values would be placed on top of older ones, and pop would return a newer value before an older one. Move only when outStack is empty.
    • Moving only part of inStack. Move all of it, or the order inside outStack breaks.
    • Moving back and forth. Putting everything back in inStack after each pop works but makes every call O(n).
    • Checking only one stack in empty. After a peek, all the values can be in outStack while inStack is empty, and the other way round after a push.
    • Removing in peek. peek only reads. Removing belongs to pop.
    • A new queue. Both stacks are empty, so empty() is true.
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free