Implement Stack Using Queue in DSA Typescript

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

Queue: front -> [1] -> null

Why: Add first element to queue

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

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

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

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

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

Why: Rotate again to keep last pushed at front

Step 4: Pop from queue (remove front)

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

Why: Remove last pushed element, simulating stack pop

Result:

Queue after pop: front -> [2] -> [1] -> null
Popped value: 3

Annotated Code

DSA Typescript

class Queue<T> {
  private items: T[] = [];

  enqueue(item: T): void {
    this.items.push(item);
  }

  dequeue(): T | undefined {
    return this.items.shift();
  }

  size(): number {
    return this.items.length;
  }

  front(): T | undefined {
    return this.items[0];
  }
}

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

  push(item: T): void {
    this.queue.enqueue(item); // add new item to queue
    let size = this.queue.size();
    // rotate queue to move new item to front
    while (size > 1) {
      const temp = this.queue.dequeue();
      if (temp !== undefined) {
        this.queue.enqueue(temp);
      }
      size--;
    }
  }

  pop(): T | undefined {
    return this.queue.dequeue(); // remove front which is last pushed
  }

  top(): T | undefined {
    return this.queue.front(); // front is top of stack
  }

  isEmpty(): boolean {
    return this.queue.size() === 0;
  }
}

// Driver code
const stack = new StackUsingQueue<number>();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // should print 3
console.log(stack.pop()); // should print 2
console.log(stack.pop()); // should print 1
console.log(stack.pop()); // should print undefined (empty stack)

this.queue.enqueue(item); // add new item to queue

enqueue new item to queue

while (size > 1) { const temp = this.queue.dequeue(); this.queue.enqueue(temp); size--; }

rotate queue to move last pushed item to front

return this.queue.dequeue(); // remove front which is last pushed

pop removes front of queue which is stack top

return this.queue.front(); // front is top of stack

top returns front of queue

Output

3

2

1

undefined

Complexity Analysis

Time: O(n) for push because we rotate the queue to keep last pushed item at front; O(1) for pop and top

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

vs Alternative: Naive approach might use two queues and move elements back and forth, which is less efficient; this single queue rotation is simpler but push is costlier

Edge Cases

Pop from empty stack

Returns undefined safely without error

DSA Typescript

return this.queue.dequeue(); // remove front which is last pushed

Push single element and pop

Works normally, pop returns that element

DSA Typescript

while (size > 1) { ... } // rotation handles single element by skipping

When to Use This Pattern

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

Common Mistakes

Mistake: Not rotating the queue after enqueue, so pop returns oldest element instead of newest
Fix: Rotate the queue after enqueue by dequeuing and enqueuing all elements except the last one

Summary

Implements a stack using a single queue by rotating elements to keep the newest on front.

Use when only queue operations are allowed but stack behavior is needed.

The key is rotating the queue after each push to simulate stack's top at the front.

Practice

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

easy

A. Use a queue to sort elements in ascending order

B. Use two stacks to implement a queue

C. Use a stack to implement queue operations

D. Use one or two queues to simulate stack operations like push and pop

Solution

1. Step 1: Understand stack and queue operations

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

2. Step 2: Simulate stack using queue(s)

   By using one or two queues cleverly, we can reorder elements to behave like a stack.

3. Final Answer:

   Use one or two queues to simulate stack operations like push and pop -> Option D

4. Quick Check:

   Stack via queue = simulate LIFO with FIFO [OK]

Hint: Remember stack is LIFO, queue is FIFO; simulate LIFO with queue(s) [OK]

Common Mistakes:

• Confusing stack and queue order
• Thinking queue sorts elements automatically
• Using stack to implement queue instead

2. Which of the following TypeScript code snippets correctly declares a queue using an array?

easy

A. const queue: number[] = [];

B. let queue = new Stack<number>();

C. const queue = {};

D. let queue: Queue = new Array();

Solution

1. Step 1: Check correct TypeScript array declaration

   To declare a queue as an array of numbers, use const queue: number[] = [];

2. Step 2: Identify incorrect declarations

   let queue = new Stack<number>(); uses Stack, not queue; C is an empty object; A uses undefined type Queue.

3. Final Answer:

   const queue: number[] = []; -> Option A

4. Quick Check:

   Array queue declaration = const queue: number[] = [] [OK]

Hint: Use array with type annotation for queue: const queue: number[] = [] [OK]

Common Mistakes:

• Using Stack instead of array for queue
• Declaring queue as empty object {}
• Using undefined types without import

3. Given the following TypeScript code implementing a stack using one queue, what will be the output after the operations?

class StackUsingQueue {
  private queue: number[] = [];

  push(x: number) {
    this.queue.push(x);
    for (let i = 0; i < this.queue.length - 1; i++) {
      this.queue.push(this.queue.shift()!);
    }
  }

  pop(): number | undefined {
    return this.queue.shift();
  }
}

const stack = new StackUsingQueue();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());
console.log(stack.pop());

medium

A. 3
2

B. 1
2

C. 2
3

D. Error at runtime

Solution

1. Step 1: Trace push operations

   Push 1: queue=[1]
   Push 2: queue=[2,1] after rotation
   Push 3: queue=[3,2,1] after rotation

2. Step 2: Trace pop operations

   Pop returns queue.shift(): 3, then next pop returns 2.

3. Final Answer:

   3 2 -> Option A

4. Quick Check:

   Stack pop order = 3 then 2 [OK]

Hint: Push rotates queue to front; pop removes front element [OK]

Common Mistakes:

• Not rotating queue after push
• Assuming pop removes last element of array
• Confusing shift() with pop()

4. Identify the bug in this TypeScript code for stack using two queues and suggest the fix:

class StackUsingTwoQueues {
  private q1: number[] = [];
  private q2: number[] = [];

  push(x: number) {
    this.q1.push(x);
  }

  pop(): number | undefined {
    while (this.q1.length > 1) {
      this.q2.push(this.q1.shift()!);
    }
    return this.q1.shift();
  }
}

medium

A. pop() should return q2.shift() instead of q1.shift()

B. push() should push to q2 instead of q1

C. pop() does not swap q1 and q2 after popping; add swap after pop

D. No bug; code works correctly

Solution

1. Step 1: Analyze pop method behavior

   Pop moves all but last element from q1 to q2, then removes last from q1.

2. Step 2: Identify missing queue swap

   After pop, q1 is empty and q2 has elements, but q1 and q2 are not swapped, so next push/pop fail.

3. Final Answer:

   pop() does not swap q1 and q2 after popping; add swap after pop -> Option C

4. Quick Check:

   Swap queues after pop to maintain correct state [OK]

Hint: Remember to swap queues after pop in two-queue stack [OK]

Common Mistakes:

• Forgetting to swap queues after pop
• Pushing to wrong queue
• Returning wrong queue element

5. You want to implement a stack using a single queue in TypeScript. Which approach correctly ensures that the pop() operation returns the last pushed element efficiently?

class StackUsingOneQueue {
  private queue: number[] = [];

  push(x: number) {
    this.queue.push(x);
    // What should be done here?
  }

  pop(): number | undefined {
    return this.queue.shift();
  }
}

hard

A. After push, sort the queue in descending order

B. After push, rotate the queue by moving all elements except the last to the back

C. After push, reverse the queue array

D. No extra operation needed after push

Solution

1. Step 1: Understand stack behavior with one queue

   To simulate LIFO, after pushing, rotate queue so new element is at front.

2. Step 2: Rotate queue after push

   Move all elements except last pushed to back, so pop (shift) removes last pushed.

3. Final Answer:

   After push, rotate the queue by moving all elements except the last to the back -> Option B

4. Quick Check:

   Rotate queue after push to simulate stack pop [OK]

Hint: Rotate queue after push to keep last element at front [OK]

Common Mistakes:

• Sorting queue instead of rotating
• Reversing queue array (inefficient)
• Not rotating queue after push