Implement Stack Using Queue in DSA Typescript - Execution Trace

Concept Flow - Implement Stack Using Queue

Initialize empty queue

↓

Push operation: enqueue new element

↓

Rotate queue to move new element to front

↓

Pop operation: dequeue front element

↓

Top operation: peek front element

↓

Check if queue is empty for isEmpty

Stack is simulated by using one queue where new elements are enqueued and then rotated to front to mimic LIFO order.

Execution Sample

DSA Typescript

class Stack {
  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();
  }

  top(): number | undefined {
    return this.queue[0];
  }

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

This code uses one queue to implement stack operations by rotating the queue after each push.

Execution Table

Step	Operation	Queue State Before	Action	Queue State After	Visual State
1	Initialize	[]	Create empty queue	[]	[]
2	push(1)	[]	Enqueue 1, rotate 0 times	[1]	[1]
3	push(2)	[1]	Enqueue 2, rotate 1 time: move 1 to back	[2,1]	[2 -> 1]
4	push(3)	[2,1]	Enqueue 3, rotate 2 times: move 2, then 1 to back	[3,2,1]	[3 -> 2 -> 1]
5	top()	[3,2,1]	Peek front element	[3,2,1]	Top is 3
6	pop()	[3,2,1]	Dequeue front element (3)	[2,1]	[2 -> 1]
7	top()	[2,1]	Peek front element	[2,1]	Top is 2
8	pop()	[2,1]	Dequeue front element (2)	[1]	[1]
9	pop()	[1]	Dequeue front element (1)	[]	[]
10	isEmpty()	[]	Check if queue is empty	[]	Stack is empty

💡 All operations complete; queue empty means stack empty.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 8	After Step 9
queue	[]	[1]	[2,1]	[3,2,1]	[2,1]	[1]	[]

Key Moments - 3 Insights

Why do we rotate the queue after each push?

Rotating the queue moves the newly added element to the front, so pop() removes the last pushed element first, mimicking stack's LIFO behavior (see Step 3 and 4 in execution_table).

What happens if we pop when the queue is empty?

pop() returns undefined because the queue is empty, meaning the stack is empty (see Step 9 and 10).

Why does top() always return the first element in the queue?

Because after rotation, the most recently pushed element is at the front of the queue, so queue[0] is the stack's top (see Step 5 and 7).

Visual Quiz - 3 Questions

Look at the execution_table, what is the queue state after push(3)?

A [3,2,1]

B [1,2,3]

C [2,1,3]

D [3,1,2]

💡 Hint

Check Step 4 in execution_table for queue state after push(3).

At which step does the stack become empty?

A Step 10

B Step 8

C Step 9

D Step 7

💡 Hint

Look at queue state after Step 9 in variable_tracker and execution_table.

If we skip rotating the queue after push, what happens to pop()?

A pop() removes nothing

B pop() removes the oldest element, not the last pushed

C pop() removes the last pushed element correctly

D pop() throws an error

💡 Hint

Rotation moves new element to front; without it, queue behaves FIFO (see concept_flow).

Concept Snapshot

Stack using one queue:
- push(x): enqueue x, then rotate queue to move x to front
- pop(): dequeue front element
- top(): peek front element
- isEmpty(): check if queue is empty
Rotation ensures LIFO order using FIFO queue

Full Transcript

We implement a stack using a single queue by pushing elements into the queue and then rotating the queue so the new element moves to the front. This way, when we pop, we remove the front element, which is the last pushed element, mimicking stack behavior. The top operation returns the front element of the queue. The isEmpty operation checks if the queue is empty. The execution table shows step-by-step how the queue changes after each operation, and the variable tracker records the queue state after key steps. Key moments clarify why rotation is needed and how top and pop work. The visual quiz tests understanding of queue states and behavior changes if rotation is skipped.

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