Start learning free

LESSON 416 OF 576 · STACK

Implement Queue Using Stacks in Rust: Two Vecs, 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 12
    Ctrl + Enter to check

    RUST · STACK

    Implement Queue Using Stacks in Rust, explained

    Problem overview

    A queue returns values in the order they arrived; a stack returns the newest first. The task is to build the struct MyQueue from two stacks, using only stack operations: add on top, look at or remove the top, and check for emptiness. In Rust a Vec<i32> works as a stack, with the top at the end of the vector.

    The methods are MyQueue::new(), push(x) to add at the back, peek() for the front value without removing it, pop() to remove and return the front, and empty(). pop and peek are only called on a non-empty queue.

    After push(1) and push(2), peek() returns 1, and so does pop(). Then empty() is false, because 2 is still waiting.

    The statement asks for O(1) time per operation, amortized.

    Approach: reverse once, and only when needed

    Pushing is easy: put the value on a stack. The trouble is that the top of that stack is the newest value, while the queue's front is the oldest, at the bottom. Moving all the values onto a second stack, one by one, reverses their order and puts the oldest on top. Doing that move and then moving everything back on every pop works, but it costs O(n) per call.

    The better idea is to not move them back. Keep two stacks. New values always go on in_stack. Values leave from out_stack, which holds the older values already in the right order, oldest on top. Only when out_stack is empty and the front is needed, move everything from in_stack to out_stack.

    Why wait until out_stack is empty? Everything in it arrived before anything in in_stack, so its top is still the front. Moving earlier would put newer values on top of older ones and break the order.

    Here is the second example with the contents of both stacks after each step:

    after push(1), push(2):  in=[1, 2] out=[]
pop -> 1                 in=[] out=[2]
push(3)                  in=[3] out=[2]
peek -> 2                in=[3] out=[2]
pop -> 2                 in=[3] out=[]
pop -> 3                 in=[] out=[]
empty() -> true

    The first pop moves both values over (2 ends up under 1, then 1 is removed). The 3 waits in in_stack while 2 leaves. Only when out_stack is empty does the next pop move 3 across.

    Why it is amortized O(1)

    A single pop can move many values, so it can be O(n). But count the work per value instead of per call. Each value is pushed onto in_stack once, moved to out_stack at most once, and popped from out_stack once. Values are never moved back. So a value costs at most three stack operations in its whole life, and n operations cost O(n) in total: O(1) per operation on average.

    That matches what a test copy of the code counts: 100,000 pushes followed by 100,000 pops move values between the stacks exactly 100,000 times, once per value.

    Step by step

    1. Declare in_stack, a Vec<i32> that takes every pushed value on top. The end of the vector is the top.
    2. Declare out_stack, also a Vec<i32>, from which values leave in order, oldest on top.
    3. In new, return the struct with two empty vectors.
    4. In push, push x onto in_stack.
    5. In peek, start an if that runs only when out_stack is empty.
    6. Inside it, loop while in_stack is not empty.
    7. Move one value per round: pop it from in_stack, unwrap the Option, and push it onto out_stack.
    8. After the if, return the top of out_stack without removing it.
    9. In pop, call self.peek() and keep the result in front. It moves the values if needed and finds the front.
    10. Remove the top of out_stack.
    11. Return front.
    12. In empty, return whether both stacks are empty.

    The solution in Rust

    struct MyQueue {
    in_stack: Vec<i32>,
    out_stack: Vec<i32>,
}

impl MyQueue {
    fn new() -> MyQueue {
        MyQueue { in_stack: Vec::new(), out_stack: Vec::new() }
    }

    fn push(&mut self, x: i32) {
        self.in_stack.push(x);
    }

    fn peek(&mut self) -> i32 {
        if self.out_stack.is_empty() {
            while !self.in_stack.is_empty() {
                self.out_stack.push(self.in_stack.pop().unwrap());
            }
        }
        *self.out_stack.last().unwrap()
    }

    fn pop(&mut self) -> i32 {
        let front = self.peek();
        self.out_stack.pop();
        front
    }

    fn empty(&self) -> bool {
        self.in_stack.is_empty() && self.out_stack.is_empty()
    }
}

    Using it, after push(1) and push(2), the calls peek(), pop() and empty() print 1, 1 and false. For a new queue, empty(), push(7), empty(), pop() and empty() give true, false, 7 and true. Pushing 1 to 3, popping once, pushing 4 and 5 and then popping until the queue is empty returns 1, 2, 3, 4, 5.

    The Rust details worth a closer look:

    • &mut self on peek. Looking at the front can move values between the stacks, so peek changes the struct even though the queue's contents stay the same. empty only reads, so it takes &self.
    • A Vec as a stack. push, pop and last all work at the end of the vector in O(1). pop returns an Option<i32>, None when empty.
    • self.out_stack.push(self.in_stack.pop().unwrap()). The two fields are borrowed separately, so this compiles. unwrap() is safe because the loop only runs while in_stack has values.
    • *self.out_stack.last().unwrap(). last() returns an Option<&i32>, a reference to the top. The * copies the number out of it. The last line has no semicolon, so it is the return value.
    • self.out_stack.pop(); as a statement. It returns the removed value in an Option, and the code throws it away because front already holds the number.
    • Calling a method on self. self.peek() inside pop needs &mut self too, which pop already has.

    Complexity

    Time. push, empty and the final removal in pop are O(1). peek and pop are O(1) amortized: one call may move every value, but each value moves once in its life, so n operations take O(n) in total.

    Space. O(n) for the n values in the queue, split across the two vectors.

    Edge cases and common mistakes

    • Moving while out_stack still has values. The newer values would land on top of the older ones, and the queue would return them in the wrong order. After push(1), push(2), pop(), push(3), the next pop() must return 2, not 3.
    • Moving everything back after each pop. It is correct but O(n) per call.
    • Peeking twice. The second peek finds out_stack non-empty and moves nothing. After pushing 1 to 4, two calls return 1 both times, and out_stack holds [4, 3, 2, 1] with the 1 on top.
    • Checking only one stack in empty. After the first pop in the second example, out_stack holds 2 and in_stack is empty; after push(3) the 3 is in in_stack. Either stack alone would give a wrong answer at some point.
    • Popping an empty queue. The constraints rule it out. In this code, last().unwrap() would panic if both stacks were empty.
    • Forgetting that pop must return the front. Read it with peek before removing it, as the code does.

    Testing

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