How to implement a queue using two stacks?

How to Implement a Queue Using Two Stacks in JavaScript

A queue is a data structure that follows the First In, First Out (FIFO) principle, while a stack follows the Last In, First Out (LIFO) principle. To implement a queue using two stacks, you can use one stack to handle incoming elements (stack1) and another stack to handle outgoing elements (stack2). Here's how you can achieve this in JavaScript.

Concept

• stack1: Used to handle all incoming elements (enqueue operations).
• stack2: Used to handle all outgoing elements (dequeue operations). When stack2 is empty, elements from stack1 are moved to stack2, reversing the order and maintaining the FIFO behavior.

Implementation

Here is the implementation of a queue using two stacks:

class QueueUsingTwoStacks {
    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }

    // Add an element to the queue
    enqueue(element) {
        this.stack1.push(element);
    }

    // Remove and return the front element from the queue
    dequeue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }

        // If stack2 is empty, move elements from stack1 to stack2
        if (this.stack2.length === 0) {
            while (this.stack1.length > 0) {
                this.stack2.push(this.stack1.pop());
            }
        }

        return this.stack2.pop();
    }

    // Return the front element without removing it
    peek() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }

        // If stack2 is empty, move elements from stack1 to stack2
        if (this.stack2.length === 0) {
            while (this.stack1.length > 0) {
                this.stack2.push(this.stack1.pop());
            }
        }

        return this.stack2[this.stack2.length - 1];
    }

    // Check if the queue is empty
    isEmpty() {
        return this.stack1.length === 0 && this.stack2.length === 0;
    }

    // Return the size of the queue
    size() {
        return this.stack1.length + this.stack2.length;
    }

    // Print the elements of the queue
    printQueue() {
        let output = [];

        // Print elements in stack2 first (in reverse order)
        for (let i = this.stack2.length - 1; i >= 0; i--) {
            output.push(this.stack2[i]);
        }

        // Then print elements in stack1 (in original order)
        for (let i = 0; i < this.stack1.length; i++) {
            output.push(this.stack1[i]);
        }

        return output.join(' ');
    }
}

// Example usage:
const queue = new QueueUsingTwoStacks();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.printQueue()); // Output: 1 2 3
console.log(queue.dequeue()); // Output: 1
console.log(queue.printQueue()); // Output: 2 3
queue.enqueue(4);
console.log(queue.printQueue()); // Output: 2 3 4
console.log(queue.peek()); // Output: 2
console.log(queue.isEmpty()); // Output: false
console.log(queue.size()); // Output: 3

Explanation

1. enqueue(element):

   • Push the element onto stack1.

2. dequeue():

   • If both stacks are empty, the queue is empty.
   • If stack2 is empty, move all elements from stack1 to stack2 by popping from stack1 and pushing onto stack2.
   • Pop and return the top element from stack2.

3. peek():

   • If both stacks are empty, the queue is empty.
   • If stack2 is empty, move all elements from stack1 to stack2.
   • Return the top element from stack2 without removing it.

4. isEmpty():

   • Return true if both stacks are empty.

5. size():

   • Return the total number of elements in both stacks.

6. printQueue():

   • Print elements from stack2 first (in reverse order), then print elements from stack1 (in original order).

Summary

Using two stacks to implement a queue ensures that you can maintain the FIFO behavior of a queue while leveraging the LIFO nature of stacks. This implementation provides efficient enqueue and dequeue operations, making it a useful technique for solving problems where you need a queue-like data structure but only have stack operations available.

For more in-depth knowledge and practical examples on data structures and algorithms, consider exploring Grokking the Coding Interview on DesignGurus.io, which offers comprehensive courses on essential coding and interview techniques.