Implement Stack Using Queue in DSA C#

Mental Model

A stack works like a pile where the last item added is the first to be removed. A queue works like a line where the first item added is the first to be removed. We can use a queue to act like a stack by carefully moving items around.

Analogy: Imagine a line of people (queue). To get the last person who joined to leave first (stack behavior), you ask everyone except the last to step aside and then let the last person leave. Then the others come back in line.

Queue: front -> [1] -> 2 -> 3 -> null
Stack: top -> 3 -> 2 -> 1 -> null

Dry Run Walkthrough

Input: Push 1, Push 2, Push 3, Pop

Goal: Use a queue to behave like a stack and pop the last pushed item

Step 1: Push 1 into queue

front -> [1] -> null

Why: Add first element to queue

Step 2: Push 2 into queue, then rotate queue to move 2 to front

front -> [2] -> 1 -> null

Why: Rotate so last pushed element is at front to simulate stack top

Step 3: Push 3 into queue, then rotate queue to move 3 to front

front -> [3] -> 2 -> 1 -> null

Why: Rotate so last pushed element is at front to simulate stack top

Step 4: Pop from queue (remove front)

front -> [2] -> 1 -> null

Why: Remove last pushed element which is at front

Result:

front -> [2] -> 1 -> null
Pop returned 3

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class StackUsingQueue
{
    private Queue<int> queue = new Queue<int>();

    public void Push(int x)
    {
        queue.Enqueue(x); // Add new element at end
        int size = queue.Count;
        // Rotate queue to move new element to front
        for (int i = 0; i < size - 1; i++)
        {
            int val = queue.Dequeue();
            queue.Enqueue(val);
        }
    }

    public int Pop()
    {
        if (queue.Count == 0) throw new InvalidOperationException("Stack is empty");
        return queue.Dequeue(); // Remove front element which is top of stack
    }

    public int Top()
    {
        if (queue.Count == 0) throw new InvalidOperationException("Stack is empty");
        return queue.Peek(); // Front element is top of stack
    }

    public bool IsEmpty()
    {
        return queue.Count == 0;
    }

    public void PrintStack()
    {
        // Print elements from front to end as stack top to bottom
        Console.WriteLine(string.Join(" -> ", queue) + " -> null");
    }
}

public class Program
{
    public static void Main()
    {
        StackUsingQueue stack = new StackUsingQueue();
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);
        stack.PrintStack();
        int popped = stack.Pop();
        Console.WriteLine(popped);
        stack.PrintStack();
    }
}

queue.Enqueue(x); // Add new element at end

Add new element to the queue's end

for (int i = 0; i < size - 1; i++)

Rotate queue to move last added element to front

int val = queue.Dequeue(); queue.Enqueue(val);

Remove front and add it to back to rotate

return queue.Dequeue(); // Remove front element which is top of stack

Pop removes the front element which acts as stack top

return queue.Peek(); // Front element is top of stack

Top returns the front element without removing

Output

3 -> 2 -> 1 -> null

3

2 -> 1 -> null

Complexity Analysis

Time: O(n) for push because we rotate all elements to keep last pushed at front; O(1) for pop and top because they operate on front element

Space: O(n) because we store all elements in the queue

vs Alternative: Naive approach using two queues can have O(1) push but O(n) pop; this approach optimizes pop to O(1) by paying cost on push

Edge Cases

Pop or Top on empty stack

Throws InvalidOperationException to signal empty stack

DSA C#

if (queue.Count == 0) throw new InvalidOperationException("Stack is empty");

Push single element

Element is added and becomes top immediately

DSA C#

queue.Enqueue(x);

When to Use This Pattern

When you need last-in-first-out behavior but only have a first-in-first-out structure, use queue rotation to simulate stack operations.

Common Mistakes

Mistake: Not rotating the queue after push, so the last pushed element is not at the front
Fix: Rotate the queue by dequeuing and enqueuing all elements except the last after each push

Mistake: Trying to pop from empty queue without checking
Fix: Add a check to throw exception if queue is empty before popping

Summary

Implements a stack using a single queue by rotating elements to keep the last pushed item at the front.

Use when you want stack behavior but only have queue operations available.

The key is to rotate the queue after each push so the newest element is always at the front.

Practice

1. What is the main idea behind implementing a stack using a queue?

easy

A. Use a linked list directly to implement stack

B. Use one queue and reorder elements to simulate stack behavior

C. Use two stacks to simulate queue behavior

D. Use an array to simulate queue behavior

Solution

1. Step 1: Understand stack and queue behavior

   A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).

2. Step 2: Simulate stack using queue

   By reordering elements in a single queue after each push, the newest element is always at the front, simulating stack pop behavior.

3. Final Answer:

   Use one queue and reorder elements to simulate stack behavior -> Option B

4. Quick Check:

   Stack via queue = reorder elements [OK]

Hint: Remember stack is LIFO, queue is FIFO; reorder queue to mimic stack [OK]

Common Mistakes:

• Confusing stack and queue order
• Using two stacks instead of queues
• Ignoring element reordering after push

2. Which of the following is the correct C# syntax to declare a queue of integers?

easy

A. Queue<int> queue = new Queue<int>();

B. Queue queue = new Queue<int>();

C. Queue<int> queue = Queue<int>();

D. Queue<int> queue = new Queue();

Solution

1. Step 1: Review C# generic queue declaration

   In C#, a generic queue is declared as Queue<T> with new keyword and parentheses.

2. Step 2: Check each option

   Queue<int> queue = new Queue<int>(); correctly uses Queue<int> queue = new Queue<int>(); which is valid syntax.

3. Final Answer:

   Queue<int> queue = new Queue<int>(); -> Option A

4. Quick Check:

   Generic queue syntax = Queue<int> queue = new Queue<int>(); [OK]

Hint: Use new Queue<int>() to declare generic queue in C# [OK]

Common Mistakes:

• Omitting new keyword
• Missing generic type in constructor
• Using non-generic Queue without type

3. What will be the output of the following C# code implementing stack using one queue?

var stack = new StackUsingQueue();
stack.Push(10);
stack.Push(20);
stack.Push(30);
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Pop());

medium

A. 10\n30

B. 10\n20

C. 20\n30

D. 30\n20

Solution

1. Step 1: Understand push operation in stack using queue

   Each push adds element and reorders queue so last pushed is at front.

2. Step 2: Trace pop operations

   First pop returns 30 (last pushed), second pop returns 20 (second last pushed).

3. Final Answer:

   30\n20 -> Option D

4. Quick Check:

   Stack pop order = last in first out = 30, then 20 [OK]

Hint: Pop returns last pushed element due to queue reorder [OK]

Common Mistakes:

• Assuming queue FIFO order for pop
• Mixing push and pop order
• Ignoring reorder after push

4. Identify the potential issue in this C# method for stack push using one queue:

public void Push(int x) {
    queue.Enqueue(x);
    for (int i = 0; i < queue.Count - 1; i++) {
        queue.Enqueue(queue.Dequeue());
    }
}

medium

A. Enqueue should be Dequeue

B. Missing return statement

C. Using queue.Count in loop condition changes during iteration

D. Loop should run queue.Count times

Solution

1. Step 1: Analyze loop condition with queue.Count

   queue.Count changes momentarily during iteration (decreases after Dequeue, restores after Enqueue).

2. Step 2: Explain why this is a concern

   Although the size restores before the next condition check and works correctly, using a changing value in the loop condition can be confusing and is bad practice. Store count beforehand: int n = queue.Count; for(int i=0; i < n-1; i++)...

3. Final Answer:

   Using queue.Count in loop condition changes during iteration -> Option C

4. Quick Check:

   Loop count must be stored before loop [OK]

Hint: Store queue.Count before loop to avoid changing condition [OK]

Common Mistakes:

• Using dynamic queue.Count in loop condition
• Not rotating queue elements correctly
• Confusing enqueue and dequeue operations

5. You want to implement a stack using two queues. Which approach correctly simulates the stack's pop operation?

hard

A. Push elements into queue1; for pop, move all but last from queue1 to queue2, dequeue last from queue1, then swap queues

B. Push elements into queue2; for pop, dequeue directly from queue2

C. Push elements into queue1; pop by dequeuing from queue1 without moving elements

D. Push elements into queue2; for pop, move all elements to queue1 and dequeue first

Solution

1. Step 1: Understand two-queue stack implementation

   One queue holds elements; pop requires removing last pushed element, which is at the end.

2. Step 2: Describe correct pop operation

   Move all but last element from queue1 to queue2, dequeue last from queue1 (stack pop), then swap queues for next operations.

3. Final Answer:

   Push elements into queue1; for pop, move all but last from queue1 to queue2, dequeue last from queue1, then swap queues -> Option A

4. Quick Check:

   Pop = move all but last, dequeue last, swap queues [OK]

Hint: Pop by moving all but last element, then dequeue last [OK]

Common Mistakes:

• Dequeuing directly without moving elements
• Not swapping queues after pop
• Confusing which queue holds elements