Implement Stack Using Queue in DSA Javascript - Build from Scratch

Implement Stack Using Queue

📖 Scenario: Imagine you are building a simple text editor that needs to keep track of the last few actions a user performed. You want to use a stack to store these actions so you can undo them in reverse order. However, you only have a queue data structure available. Your task is to create a stack using a queue.

🎯 Goal: Build a stack using a single queue in JavaScript. You will implement the push and pop operations of the stack using queue operations.

📋 What You'll Learn

Create a queue using an array named queue

Create a variable size to track the number of elements in the queue

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

Implement a pop function that removes and returns the top element of the stack using the queue

Print the result of popping elements from the stack

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, expression evaluation, and backtracking algorithms. Sometimes you only have queues available, so knowing how to build a stack from a queue is useful.

💼 Career

Understanding how to implement one data structure using another shows problem-solving skills and deep knowledge of data structures, which is valuable in software engineering interviews and real-world coding.

1

Create the queue data structure

Create an empty array called queue to represent the queue and a variable size set to 0 to track the number of elements.

DSA Javascript

const queue = []
let size = 0
// Your code here

Hint

Use an array to represent the queue and a number variable to track its size.

2

Implement the push function

Write a function called push that takes a parameter x. Inside the function, add x to the end of queue using queue.push(x) and increase size by 1.

DSA Javascript

const queue = []
let size = 0

function push(x) {
  // Your code here
}

Hint

Use queue.push(x) to add the element and update size.

3

Implement the pop function

Write a function called pop that removes and returns the last pushed element to simulate stack pop using the queue. Use a loop to move the first size - 1 elements from the front of queue to the back using queue.shift() and queue.push(). Then remove the last element with queue.shift(), decrease size by 1, and return that element.

DSA Javascript

const queue = []
let size = 0

function push(x) {
  queue.push(x)
  size += 1
}

function pop() {
  // Your code here
}

Hint

Rotate the queue elements except the last one, then remove and return the last element.

4

Test the stack implementation

Use push to add 10, 20, and 30 to the stack. Then use pop twice and print the results using console.log.

DSA Javascript

const queue = []
let size = 0

function push(x) {
  queue.push(x)
  size += 1
}

function pop() {
  for (let i = 0; i < size - 1; i++) {
    queue.push(queue.shift())
  }
  size -= 1
  return queue.shift()
}

// Your code here

Hint

Push three numbers, then pop twice and print the popped values.

Practice

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

easy

A. Use two stacks to implement a queue

B. Use an array to implement a queue

C. Use a linked list to implement a stack

D. Use a queue to simulate stack operations by reversing order

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

   To implement stack using queue, we reverse the order of elements in the queue to mimic LIFO behavior.

3. Final Answer:

   Use a queue to simulate stack operations by reversing order -> Option D

4. Quick Check:

   Stack via queue = reverse order [OK]

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

Common Mistakes:

• Confusing stack with queue behavior
• Trying to implement queue using stack instead
• Ignoring order reversal needed for stack simulation

2. Which of the following is the correct syntax to enqueue an element `x` into a JavaScript queue implemented as an array named `queue`?

easy

A. queue.shift(x);

B. queue.push(x);

C. queue.pop(x);

D. queue.unshift(x);

Solution

1. Step 1: Identify enqueue operation in JavaScript array

   Enqueue means adding element at the end of the queue, which is done by push().

2. Step 2: Check other methods

   pop() removes from end, shift() removes from front, unshift() adds at front, so only push() adds at end.

3. Final Answer:

   queue.push(x); -> Option B

4. Quick Check:

   Enqueue = push() [OK]

Hint: Use push() to add at queue end in JavaScript arrays [OK]

Common Mistakes:

• Using pop() instead of push() to add elements
• Using shift() or unshift() incorrectly for enqueue
• Confusing enqueue with dequeue operations

3. Consider this JavaScript code implementing a stack using one queue:

class Stack {
  constructor() {
    this.queue = [];
  }
  push(x) {
    this.queue.push(x);
    for (let i = 0; i < this.queue.length - 1; i++) {
      this.queue.push(this.queue.shift());
    }
  }
  pop() {
    return this.queue.shift();
  }
}
const s = new Stack();
s.push(1);
s.push(2);
s.push(3);
console.log(s.pop());

What will be printed?

medium

A. 2

B. 1

C. 3

D. undefined

Solution

1. Step 1: Understand push operation

   Push adds element at end, then rotates queue to move new element to front, simulating stack top.

2. Step 2: Trace push and pop calls

   Push 1: queue=[1]; Push 2: queue=[2,1]; Push 3: queue=[3,2,1]; Pop removes front, which is 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Stack pop = last pushed = 3 [OK]

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

Common Mistakes:

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

4. The following code attempts to implement a stack using two queues. What is the error?

class Stack {
  constructor() {
    this.q1 = [];
    this.q2 = [];
  }
  push(x) {
    this.q1.push(x);
  }
  pop() {
    while (this.q1.length > 1) {
      this.q2.push(this.q1.shift());
    }
    return this.q1.shift();
  }
}

medium

A. pop() does not swap q1 and q2 after operation

B. push() should use q2 instead of q1

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

D. Constructor should initialize q1 and q2 as objects, not arrays

Solution

1. Step 1: Analyze pop method

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

2. Step 2: Identify missing step

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

3. Final Answer:

   pop() does not swap q1 and q2 after operation -> Option A

4. Quick Check:

   Swap queues after pop to maintain stack [OK]

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

Common Mistakes:

• Forgetting to swap queues after pop
• Returning from wrong queue
• Incorrect initialization of queues

5. You want to implement a stack using a single queue in JavaScript. Which approach correctly maintains stack order after each push operation?

class Stack {
  constructor() {
    this.queue = [];
  }
  push(x) {
    this.queue.push(x);
    // What should be done here?
  }
  pop() {
    return this.queue.shift();
  }
}

hard

A. Rotate the queue by dequeuing and enqueuing all elements except the last pushed

B. Sort the queue in descending order after each push

C. Clear the queue and add elements again in reverse order

D. Do nothing; queue order naturally matches stack order

Solution

1. Step 1: Understand stack order with one queue

   Stack is LIFO, but queue is FIFO, so after push, rotate queue to bring new element front.

2. Step 2: Rotate queue after push

   Remove elements from front and add them to back except the last pushed, so last pushed is at front.

3. Final Answer:

   Rotate the queue by dequeuing and enqueuing all elements except the last pushed -> Option A

4. Quick Check:

   Rotate queue after push to simulate stack [OK]

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

Common Mistakes:

• Not rotating queue after push
• Trying to sort queue which is inefficient
• Assuming queue order matches stack without changes