Implementing a Queue Data Structure using Two Stacks in JavaScript :rocket:

LeetCode Question
In this blog post, we will explore how to implement a Queue data structure using two Stacks in JavaScript. Queues and stacks are fundamental data structures used in computer science to manage collections of elements. A Queue follows the First-In-First-Out (FIFO) principle, whereas a Stack follows the Last-In-First-Out (LIFO) principle. By using two stacks, we can achieve the FIFO behavior required for a Queue. 🧱

Understanding the Code 🤔

Let's start by understanding the code provided above. The code defines a constructor function for the MyQueue class, which will be our Queue data structure implemented using two stacks. Here's the code snippet for reference:

var MyQueue = function() {
    this.pushStack = [];
    this.popStack = [];
};

How the Implementation Works ⚙️

The implementation of the Queue using two Stacks is achieved through the following methods:

enqueue(x):

MyQueue.prototype.enqueue = function(x) {
    while (this.popStack.length) {
        this.pushStack.push(this.popStack.pop());
    }
    this.pushStack.push(x);
};

This method is used to add an element x to the Queue. To maintain the FIFO behavior, it first transfers all elements from the popStack to the pushStack (in reverse order) and then pushes the new element to the pushStack.

dequeue():

MyQueue.prototype.dequeue= function() {
    while (this.pushStack.length) {
        this.popStack.push(this.pushStack.pop());
    }
    return this.popStack.pop();
};

This method is used to dequeue and return the front element of the Queue (the oldest element). To do this, it transfers all elements from the pushStack to the popStack (in reverse order) and then pops and returns the top element of the popStack.

peek():

MyQueue.prototype.peek = function() {
    while (this.pushStack.length) {
        this.popStack.push(this.pushStack.pop());
    }
    return this.popStack[this.popStack.length - 1];
};

This method is used to retrieve the front element of the Queue without removing it. Like the dequeue() method, it transfers all elements from the pushStack to the popStack (in reverse order) and returns the top element of the popStack without popping it.

empty():

MyQueue.prototype.empty = function() {
    return !this.popStack.length && !this.pushStack.length;
};

This method checks whether the Queue is empty or not. It returns true if both the pushStack and popStack are empty; otherwise, it returns false.

Let's test the code

// Create a new instance of MyQueue
const queue = new MyQueue();

// Push elements into the Queue
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

// Pop an element from the Queue
const poppedElement = queue.dequeue();
console.log("Popped element:", poppedElement); // Output: Popped element: 1

// Peek at the front element of the Queue
const frontElement = queue.peek();
console.log("Front element:", frontElement); // Output: Front element: 2

// Check if the Queue is empty
const isEmpty = queue.empty();
console.log("Is Queue empty?", isEmpty); // Output: Is Queue empty? false

Advantages and Limitations ✔️ ❌

Using two Stacks to implement a Queue provides several advantages:

1. It allows us to achieve the FIFO behavior of a Queue while still leveraging the efficient push and pop operations of Stacks.

2. The code is simple and easy to understand, making it suitable for educational purposes and small-scale implementations.

However, this implementation has some limitations:

1. The peek(), dequeue(), and enqueue() methods have a time complexity of O(n) in the worst case, where n is the number of elements in the Queue. This is due to the need to transfer elements between the two stacks.

Optimised implementation for enqueue operation

MyQueue.prototype.enqueue = function (x) {
  this.pushStack.push(x);
};

MyQueue.prototype.dequeue = function () {
  while (this.pushStack.length) {
    this.popStack.push(this.pushStack.pop());
  }
  const poppedItem = this.popStack.pop();
// move elements back to pushStack
  while (this.popStack.length) {
    this.pushStack.push(this.popStack.pop());
  }
  return poppedItem;
};

MyQueue.prototype.peek = function () {
  while (this.pushStack.length) {
    this.popStack.push(this.pushStack.pop());
  }
  const peekedItem = this.popStack[this.popStack.length - 1];
// move elements back to pushStack
  while (this.popStack.length) {
    this.pushStack.push(this.popStack.pop());
  }
  return peekedItem;
};

MyQueue.prototype.empty = function () {
  return !this.pushStack.length;
};

This implementation optimizes the enqueue operation by keeping all the elements in the push stack after every operation.

Optimised implementation for dequeue operation

MyQueue.prototype.enqueue = function (x) {
  while (this.popStack.length) {
    this.pushStack.push(this.popStack.pop());
  }
  this.pushStack.push(x);
// move elements back to popStack
  while (this.pushStack.length) {
    this.popStack.push(this.pushStack.pop());
  }
};

MyQueue.prototype.dequeue = function () {
  return this.popStack.pop();
};

MyQueue.prototype.peek = function () {
  return this.popStack[this.popStack.length - 1];
};

MyQueue.prototype.empty = function () {
  return !this.popStack.length;
};

This implementation optimizes the dequeue operation by keeping all the elements in the pop stack after each operation.
It also optimizes the peek operation as a by product.

1. The empty() method has a time complexity of O(1), as it only checks if both stacks are empty.

Conclusion 👏

In this blog post, we learned how to implement a Queue data structure using two Stacks in JavaScript. We explored the code that enables us to maintain the FIFO behavior of a Queue by utilizing the LIFO property of Stacks. While this implementation provides a simple and intuitive way to create a Queue, it's important to keep in mind the potential performance impact, especially in scenarios with a large number of elements.

As a software developer, understanding data structures and their implementations is essential for writing efficient and optimized code. Implementing data structures from scratch can also improve your problem-solving skills and enhance your ability to design more complex algorithms. 💪

Feel free to experiment with the code and explore further optimizations to create an even more efficient Queue implementation. Happy coding! 💻

Connect with me on my:

LinkedIn
GitHub
Twitter

Comments

[Amit Bora]

Great explanation and concept understanding..