Start learning free

LESSON 412 OF 572 · STACK

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

    C# · STACK

    Implement Queue Using Stacks in C#, explained

    Problem overview

    A queue gives values back in the order they arrived; a stack gives back the newest first. You write the class MyQueue, a queue built from two Stack<int> objects, using only what a stack offers: Push, Pop, Peek and Count. The methods are Push(x) (add at the back), Peek() (the front value, not removed), Pop() (remove and return the front value) and Empty().

    The first example: push 1, push 2, then Peek(), Pop() and Empty(). They return:

    1
1
False

    1 arrived first, so it is at the front. After it is popped, 2 is still inside, so the queue is not empty. (The lesson's tests print booleans as True and False; the method itself returns the C# values true and false.)

    In the second example the order matters. After pushing 1 and 2 and popping 1, the queue pushes 3. A Peek() returns 2, not 3, because 2 has been waiting longer. Then Pop() returns 2, Pop() returns 3, and Empty() is true.

    Approach: reverse once, and reuse the reversal

    Popping a stack returns the newest value, and a queue needs the oldest. Moving the values from one stack to another one at a time reverses their order: the newest leaves first and lands at the bottom, the oldest leaves last and lands on top.

    The naive version moves everything to the second stack for each Pop, takes the top, and moves everything back. That costs O(n) per call for n values in the queue.

    The better version keeps the values on the second stack after moving them. The class has two stacks with different jobs:

    • inStack receives every pushed value. Its top is the newest value.
    • outStack holds values already in leaving order: its top is the oldest value.

    When the front is needed and outStack has values, its top is the answer; nothing moves. Only when outStack is empty are all values of inStack moved over. Values still in outStack arrived before everything in inStack, so they must leave first.

    Here is the state after pushing 1, 2 and 3, then calling Peek(). Each stack is listed from its top:

    before Peek:  inStack 3 2 1 | outStack (empty)
Peek returns 1
after Peek:   inStack (empty) | outStack 1 2 3

    After Pop() removes the 1 and Push(4) follows, inStack holds 4 and outStack holds 2 and 3 (2 on top). The next two pops return 2 and then 3 without moving anything. The 4 only moves when outStack runs out.

    Why it is amortized O(1)

    One Peek or Pop can move many values, so a single call can cost O(n). 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 on the queue cost O(n) in total, and each costs O(1) on average. This is what amortized O(1) means: a rare expensive call is paid for by the many cheap ones.

    Step by step

    1. Declare inStack and outStack as Stack<int> fields, each set to new Stack<int>().
    2. Push puts x on inStack.
    3. Peek checks whether outStack.Count is 0. If so, a while loop pops each value of inStack and pushes it onto outStack.
    4. After the if, Peek returns outStack.Peek(). Whether or not values were just moved, the oldest value is now on top.
    5. Pop calls the class's own Peek() and stores the result in front, because Peek already does the moving. It then pops outStack and returns front.
    6. Empty is true when both stacks have a Count of 0, joined with &&: the queue's values are split between them.

    The solution in C#

    class MyQueue {
    Stack<int> inStack = new Stack<int>();
    Stack<int> outStack = new Stack<int>();

    public void Push(int x) {
        inStack.Push(x);
    }

    public int Peek() {
        if (outStack.Count == 0) {
            while (inStack.Count > 0) {
                outStack.Push(inStack.Pop());
            }
        }
        return outStack.Peek();
    }

    public int Pop() {
        int front = Peek();
        outStack.Pop();
        return front;
    }

    public bool Empty() {
        return inStack.Count == 0 && outStack.Count == 0;
    }
}

    C#'s Stack<T> has Push, Pop, Peek and Count, and all of them work at the top. Peek() and Pop() on an empty stack throw InvalidOperationException; the problem promises they are only called on a non-empty queue. Inside a class, Pop calls Peek() by its name alone.

    Complexity

    • Time: Push and Empty are O(1). Peek and Pop are amortized O(1): a single call may take O(n), but n operations take O(n) in total.
    • Space: O(n) for the n values stored in the two stacks.

    Edge cases and common mistakes

    • Moving when outStack is not empty. This puts newer values beneath older ones and breaks the order. In the second example, 3 must not move while 2 is still in outStack.
    • Moving everything back after each pop. That keeps the queue correct but makes every call O(n).
    • Checking only one stack in Empty. After a move, all the values may be in outStack; after pushes, all may be in inStack.
    • Removing before reading. Pop reads the front with Peek first, so the value is still available to return.

    Testing

    The third example starts with an empty queue: Empty() is true, then Push(7) makes it false, Pop() returns 7, and Empty() is true again. The four results are True False 7 True in the tests' output format.

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