Implement Stack Using Queue in DSA Typescript - Build from Scratch

Implement Stack Using Queue

📖 Scenario: Imagine you are building a simple system that needs a stack to manage tasks, but you only have a queue available. You want to create a stack using the queue operations.

🎯 Goal: Build a stack data structure using a single queue. You will implement push and pop methods to add and remove elements following the Last-In-First-Out (LIFO) order.

📋 What You'll Learn

Create a queue using an array called queue

Create a push function that adds an element to the stack using the queue

Create a pop function that removes the top element from the stack using the queue

Print the state of the queue after operations to show the stack behavior

💡 Why This Matters

🌍 Real World

Sometimes, only certain data structures are available, so you need to build others using them. This helps in understanding how data structures work internally.

💼 Career

Understanding how to implement one data structure using another is a common interview question and helps improve problem-solving skills.

1

Create the queue data structure

Create an empty array called queue to represent the queue.

DSA Typescript

# Your code here

Hint

Use an array to represent the queue. Start with an empty array named queue.

2

Add the push function

Create a function called push that takes a number x and adds it to the queue. Then rotate the queue to simulate stack push behavior.

DSA Typescript

const queue: number[] = [];

// Write the push function below
# Your code here

Hint

After adding the new element, move all previous elements behind it by removing from front and adding to back.

3

Add the pop function

Create a function called pop that removes and returns the top element from the stack by removing the front element from the queue.

DSA Typescript

const queue: number[] = [];

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

// Write the pop function below
# Your code here

Hint

Remove the front element from the queue to simulate popping from the stack.

4

Print the queue after push and pop operations

Use push to add 10, then 20, then 30 to the stack. Then use pop once. Finally, print the queue array to show the current stack state.

DSA Typescript

const queue: number[] = [];

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

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

// Push 10, 20, 30
// Pop once
// Print the queue
# Your code here

Hint

After pushing 10, 20, 30 and popping once, the queue should show [20, 10].

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