Implement Stack Using Queue in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after these stack operations?

Consider a stack implemented using a single queue. The stack supports push and pop operations. After performing the following operations, what is the printed stack content from top to bottom?

push(1)
push(2)
push(3)
pop()
push(4)

DSA Typescript

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

  push(x: number): void {
    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();
  }

  printStack(): string {
    return this.queue.join(' -> ') + ' -> null';
  }
}

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

A 2 -> 1 -> 4 -> null

B 1 -> 2 -> 4 -> null

C 4 -> 2 -> 1 -> null

D 3 -> 2 -> 1 -> 4 -> null

💡 Hint

Remember that after each push, the new element is rotated to the front of the queue to simulate stack behavior.

The push operation rotates the queue so the last pushed element is always at the front. After pushing 1, 2, 3, the queue is [3, 2, 1]. Popping removes 3. Then pushing 4 rotates queue to [4, 2, 1]. So the stack top is 4, then 2, then 1.

🧠 Conceptual

intermediate

Which queue operation is essential to simulate stack's LIFO behavior?

When implementing a stack using a single queue, which queue operation must be used repeatedly to ensure the last pushed element is always popped first?

A Rotate the queue by dequeuing and enqueuing elements

B Enqueue elements at the front of the queue

C Use two queues to alternate elements

D Reverse the queue using recursion

💡 Hint

Think about how to bring the last pushed element to the front of the queue.

Rotating the queue by dequeuing and enqueuing elements moves the last pushed element to the front, simulating stack's LIFO order.

🔧 Debug

advanced

Why does this stack implementation using two queues fail to pop correctly?

Given this code snippet for a stack using two queues, why does the pop method not return the correct top element?

class Stack {
  q1: number[] = [];
  q2: number[] = [];

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

  pop(): number | undefined {
    while (this.q1.length > 1) {
      this.q2.push(this.q1.shift()!);
    }
    const popped = this.q1.shift();
    [this.q1, this.q2] = [this.q2, this.q1];
    return popped;
  }
}

A The push method should add elements to q2, not q1

B The pop method empties q1 completely before swapping queues

C The pop method does not handle empty stack case

D The pop method correctly returns the last pushed element

💡 Hint

Trace the pop method step by step with multiple pushes.

The pop method moves all but the last element from q1 to q2, then removes and returns the last element from q1, which is the top of the stack. Then it swaps q1 and q2. This correctly simulates stack pop.

📝 Syntax

advanced

Which option causes a syntax error in this stack using queue code?

Identify which code snippet will cause a syntax error when implementing a stack using a queue in TypeScript.

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

  push(x: number): void {
    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();
  }
}

A push(x: number) { this.queue.push(x) for i in 0..this.queue.length-1 { this.queue.push(this.queue.shift()!) } }

B pop() { return this.queue.shift() }

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

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

💡 Hint

Look for missing punctuation or invalid loop syntax.

Option A uses invalid loop syntax 'for i in 0..this.queue.length-1' which is not valid TypeScript, causing a syntax error.

🚀 Application

expert

What is the time complexity of push and pop in stack implemented using one queue?

In a stack implemented using a single queue where push rotates the queue to maintain stack order, what are the time complexities of push and pop operations?

A push: O(1), pop: O(n)

B push: O(n), pop: O(1)

C push: O(n), pop: O(n)

D push: O(1), pop: O(1)

💡 Hint

Consider how many elements are moved during push and pop.

Push operation rotates the queue by moving all elements except the new one, so it takes O(n). Pop just dequeues the front element, so it takes O(1).

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