Start learning free

LESSON 414 OF 574 · STACK

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

    SWIFT · STACK

    Implement Queue Using Stacks in Swift, explained

    Problem overview

    A queue gives values back in the order they arrived, like a line at a shop. A stack gives back the newest value first. The task is to build the class MyQueue out of two stacks, using only what a stack does: add on top, look at or remove the top, and check whether it is empty. The class needs push(_:) (add at the back), peek() (the front value, kept), pop() (the front value, removed) and empty().

    In the first example, after push(1) and push(2), peek() returns 1, pop() removes and returns 1, and empty() is false because 2 is still there. The statement asks for O(1) amortized time per operation. pop and peek are only called on a non-empty queue.

    Approach: reverse the order once, and only when needed

    A stack and a queue disagree about which value is at the exit. Popping a stack gives the newest value, but the queue needs the oldest, which is at the bottom. Moving values from one stack onto another reverses their order: the one on top goes first, so it lands at the bottom. After the move, the oldest value is on top of the second stack.

    The simple version moves everything over and back on every pop. That costs O(n) per call. The better version notices that the second stack, once filled, is already in the right order, so it can serve many pops without any more moves. The class uses:

    • inStack: every pushed value goes on top of it;
    • outStack: values leave from it. Its top is the oldest value.

    Only when outStack is empty and the front is needed are all the values moved from inStack to outStack. While outStack still has values, they all arrived before anything in inStack, so its top is still the front of the queue. New pushes can keep piling up on inStack and wait for their turn.

    With push(1), push(2), push(3), inStack is [1, 2, 3] and outStack is empty. The first peek() moves the values, leaving inStack empty and outStack as [3, 2, 1] with the top (1) at the end. It returns 1. A later push(4) gives inStack = [4], and the next three pops return 1, 2, 3 without any move, because outStack still has values. The fourth pop then moves the 4.

    Step by step

    1. Declare inStack as a var of type [Int], set to an empty array. The top of a stack is the end of the array, where append, last and removeLast() work.
    2. Declare outStack the same way.
    3. In push, append x to inStack.
    4. In peek, start an if that runs when outStack.isEmpty. Values move only then.
    5. Inside it, loop while !inStack.isEmpty, because every value must move so the oldest one ends up on top.
    6. Move one value: outStack.append(inStack.removeLast()).
    7. After the if, return outStack.last!, the oldest value. Reading it removes nothing.
    8. In pop, call peek() and keep the result in front with let. peek already moves values if needed.
    9. Remove the top of outStack with removeLast().
    10. Return front.
    11. In empty, return whether both stacks are empty, joined with &&.

    The solution in Swift

    class MyQueue {
    var inStack: [Int] = []
    var outStack: [Int] = []

    func push(_ x: Int) {
        inStack.append(x)
    }

    func peek() -> Int {
        if outStack.isEmpty {
            while !inStack.isEmpty {
                outStack.append(inStack.removeLast())
            }
        }
        return outStack.last!
    }

    func pop() -> Int {
        let front = peek()
        outStack.removeLast()
        return front
    }

    func empty() -> Bool {
        return inStack.isEmpty && outStack.isEmpty
    }
}

    The Swift details worth a closer look:

    • Arrays as stacks. An array has no push or pop. append adds at the end, last reads the end and removeLast() removes it. All three are O(1) on average, so the end of the array is the top.
    • last is an optional. It is nil on an empty array, and the ! unwraps it. That is safe in peek because the lesson only calls it on a non-empty queue, and by then outStack has at least one value.
    • The unused result of removeLast(). In pop, the line outStack.removeLast() throws away the removed value, which is already in front. Swift accepts that because removeLast() is marked as allowed to have an unused result.
    • Calling another method. Inside the class, peek() is called by name alone. This keeps the moving logic in one place.
    • removeLast() on an empty array stops the program with a run-time error, so calling pop on an empty queue would crash. The lesson never does that.
    • A class. The methods change the stored arrays. In a struct they would need mutating; in a class they don't.

    Complexity

    Time: amortized O(1) per operation. A single peek or pop can be expensive: when outStack is empty and inStack holds a thousand values, it moves all of them. But look at one value's life. It is pushed once, moved from inStack to outStack at most once, and popped once. A value never goes back, so each value causes at most three stack operations in total. For n operations, the work is at most about 3n, that is O(n) overall and O(1) on average per call.

    A counted run shows it. After 1,000 pushes and one pop, there have been 1,001 operations and 1,000 moves: the first pop paid for everything. After 999 more pops, the total is 2,000 operations and still 1,000 moves: those pops moved nothing. Then 500 pairs of a push and a pop make 3,000 operations and 1,500 moves in total, which is still no more than one move per value.

    Space. O(n): each value is in exactly one of the two stacks at any time.

    Edge cases and common mistakes

    • Moving while outStack still has values. That puts newer values under older ones and breaks the order. With 1 and 2 pushed, pop() returns 1, then push(3): the next peek() and pop() must return 2, and only then 3. The queue then ends up empty.
    • Moving back and forth on every call. It works, but costs O(n) per call.
    • Checking only one stack in empty. After one peek, all the values may sit in outStack, or all in inStack. The queue is empty only when both are.
    • A new queue. empty() is true. After push(7) it is false, and after pop() returns 7 it is true again.
    • Moving only part of inStack. All of its values must move, or the oldest one stays buried at the bottom.
    • Reading the wrong end. The top of a stack made from an array is its last element, not first.

    Testing

    • push(1), push(2), then peek(), pop(), empty() give 1, 1, false.
    • push(1), push(2), pop(), push(3), then peek(), pop(), pop(), empty(): the first pop gives 1, then the last four give 2, 2, 3 and true.
    • On a new queue, empty() is true; push(7), empty(), pop(), empty() give false, 7, true.
    • push(1), push(2), push(3), push(4), then four pops, give 1, 2, 3, 4.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free