In this article, we will implement queue’s operations (enqueue and dequeue) using only two stacks (in the form of plain arrays) in JavaScript. Before directly jumping into understanding the problem statement let us understand briefly what exactly a stack is and also what exactly a queue is.
A stack is a linear data structure that works on the concept of Last-In-First-Out (LIFO) in which the element which comes, at last, will be removed or out at first. Similarly, a queue is also a linear data structure that works on the concept of First-In-First-OUT (FIFO) in which the element which comes at first will be removed or out at first itself. Some real-life example for better understanding the concept of the stack includes: arranging plates over one another until the last plate is put on top etc. Similarly, standing in a movie ticket collecting row where one person will collect movie tickets at first and until that person leaves the row, next person will not be allowed to collect the movie tickets, is an example of a queue.
Now that you have understood briefly about Stacks and Queues, let us understand the problem statement clearly and further we will see the solution for the problem statement itself. Following pictorial representations will describe the problem statement clearly which is to implement queue operations (enqueue and dequeue) using only two stacks-
The above pictorial representation represents the enqueue operation which was being performed with several elements (like a ,b, c and so on) which are inserted into stack (declared in the form of plain array).
The above pictorial representation represents the dequeue operation which was being performed using several elements as well as two stacks by which we will first pop (remove) the last element from the first stack and then we will add that removed element into another stack and further remove or pop the element from the another stack. Basically removing and adding into another stack is done so that this works in reverse to what exactly stack works, or we could say reversing is done here so as to make our logic similar to queue functionality rather than working as stack itself.
Now that you have understood the problem statement very clearly let us move forward to see the approaches to solve the above illustrated problem statement.
Approach 1:
- In this approach we will first initialize two stacks (in the form of two plain arrays).
- Thereafter we will perform enqueue operation into the first stack with several elements which are given by user itself.
- Further after performing enqueue operation we will define the dequeue operation for the above inserted elements into the first stack.
- For dequeue operation we will first have to pop or remove the last element from the first stack.
- Then after removing or popping out the last element from the first stack we will add that popped element into another stack (which is also in form of array).
- Then after the adding the element into the new array we will pop or remove that element from the next stack and this way we could perform the dequeue operation.
Example:
Javascript
<script> // Two stacks declared in the form of plain array let stack1 = []; let stack2 = []; // Method that will perform our enqueue operation function enqueue(element) { stack1.push(element); console.log("Stack-1 elements are enqueue: ", stack1); } // Method that will perform our dequeue operation function dequeue() { if (stack2.length === 0) { if (stack1.length === 0) { console.log( "Dequeue not possible because queue is empty.."); } while (stack1.length > 0) { let x = stack1.pop(); stack2.push(x); } } console.log("Element after Dequeue: " + stack2.pop()); } enqueue("a"); enqueue("b"); enqueue("c"); dequeue(); dequeue(); </script> |
Output:
Stack-1 elements are enqueue: [ 'a' ] Stack-1 elements are enqueue: [ 'a', 'b' ] Stack-1 elements are enqueue: [ 'a', 'b', 'c' ] Element after Dequeue: a Element after Dequeue: b
Approach 2:
- This approach works dynamically for multiple enqueue and dequeue operations.
- Here we will handle multiple cases like if dequeue was called before enqueue, or multiple dequeue’s are called, or if enqueue is just called after dequeue or only single operation is just called after dequeue.
- As similar to first approach here also we are going to make two separate functions or methods for both enqueue and dequeue operations.
- In these two separate methods we will perform the individual logics of enqueue and dequeue respectively.
Example:
Javascript
<script> // Two stacks declared in array form let stack1 = []; let stack2 = []; // Method to implement enqueue operation function enqueue(element) { // if dequeue was called before actual // enqueue operation if (stack2.length > 0) { let len = stack2.length; for (let i = 0; i < len; i++) { let p = stack2.pop(); stack1.push(p); } } stack1.push(element); console.log("Elements after Enqueue: ", stack1); } // Method to implement dequeue operation...... function dequeue() { // If dequeue was called consecutively, all // the elements would be in stack2 if (stack2.length > 0) { console.log("Element after dequeue : " + stack2.pop()); } // If enqueue was called right before // this dequeue, stack2 is empty else if (stack2.length === 0) { if (stack1.length === 0) { // If the first operation is // dequeue itself console.log("Queue is empty"); } else if (stack1.length === 1) { // If a single operation as // enqueue was performed console.log(stack1.pop()); } // If enqueue was called before this // operation, all the elements are in // stack1, so pop them and push the // elements into stack2, then pop() else if (stack1.length > 0) { let len = stack1.length; for (let i = 0; i < len; i++) { let p = stack1.pop(); stack2.push(p); } console.log("Element after dequeue: " + stack2.pop()); } } } enqueue("a"); enqueue("b"); enqueue("c"); dequeue(); enqueue("d"); enqueue("e"); dequeue(); dequeue(); dequeue(); enqueue("f"); </script> |
Output:
Elements after Enqueue: [ 'a' ] Elements after Enqueue: [ 'a', 'b' ] Elements after Enqueue: [ 'a', 'b', 'c' ] Element after dequeue: a Elements after Enqueue: [ 'b', 'c', 'd' ] Elements after Enqueue: [ 'b', 'c', 'd', 'e' ] Element after dequeue: b Element after dequeue : c Element after dequeue : d
