JavaScript program to implement stack using queue
In this article, we implement a JavaScript program to make a stack using a queue data structure. It provides essential stack methods like push(), pop(), and peek(), isEmpty() operations, utilizing either one or two queues to simulate the behavior of a stack.
Examples:
Input:
push(2)
push(3)
pop()
peek()
push(4)
isEmpty()
Output:
3 2 false
Explanation:
push(2): The stack will be {2}
push(3): The stack will be {2 3}
pop():Pops last element (3), stack will be {2}
peek(): Peek top element of the stack 2
push(4): The stack will be {2 4}
isEmpty(): The stack is not empty so its "false".
Input:
push(1)
push(2)
push(3)
pop()
peek()
clear()
Output: 3 2
Explanation:
push(1): The stack will be {1}
push(2): The stack will be {1,2}
push(3): The stack will be {1,2,3}
pop(): It pops last element (3), stack will be {1,2}
peek(): It peeks top element of the stack 2
clear() stack will be {}
These are the following approaches:
Table of Content
- Using one Queue
- Using two Queues
Using one Queue
In this approach, we will create a class and we will write the essential methods for implementation of the stack. as stack has pop, push, peek methods. we will going to build each method by crating a queue at first. stack and queue are opposite that’s why for FIFO and LIFO conditions we are adding some conditional statements.
Example: This example shows the implementation of the above-explained approach.
class Stack {
constructor() {
this.queue = [];
}
push(value) {
// Add new element to the end of the queue
this.queue.push(value);
// Rotate the queue so that the
// new element is at the front
for (let i = 0; i < this.queue.length - 1; i++) {
this.queue.push(this.queue.shift());
}
}
pop() {
if (this.isEmpty()) {
return null; // Stack is empty
}
// Pop the top element from the
// front of the queue
return this.queue.shift();
}
peek() {
if (this.isEmpty()) {
return null;
}
// Return the front element of the queue
return this.queue[0];
}
isEmpty() {
return this.queue.length === 0;
}
clear(){
let tempQueue = this.queue;
this.queue = [];
return tempQueue;
}
}
// Example usage
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // Output: 3
console.log(stack.peek()); // Output: 2
console.log(stack);
stack.clear();
console.log(stack);
Output
3
2
2
1
Stack { queue: [] }
Stack { queue: [] }
Time complexity: O(n) for pushing elements into stack but other operation like ‘pop’, ‘peek’ have only 0( 1 ).
Space complexity: O(n) for storing elements in the stack. n is used for representing number of elements.
Using two Queues
In this approach, we are using two queues to implement the stack. we have created a class named stack and defined methods like push, pop, peek, clear and isEmpty. every methods has some conditions according to the need.
Example: This example shows the implementation of the above-explained approach.
class Stack {
constructor() {
this.queue1 = [];
this.queue2 = [];
}
push(value) {
// Push new element to queue1
this.queue1.push(value);
}
pop() {
if (this.isEmpty()) {
return null; // Stack is empty
}
// Move all elements from queue1 to
// queue2 except the last one
while (this.queue1.length > 1) {
this.queue2.push(this.queue1.shift());
}
// Pop the last element from queue1
// (which is the top of stack)
const popped = this.queue1.shift();
// Swap queue1 and queue2
[this.queue1, this.queue2] = [this.queue2, this.queue1];
return popped;
}
peek() {
if (this.isEmpty()) {
return null;
}
return this.queue1[this.queue1.length - 1];
}
isEmpty() {
return this.queue1.length === 0;
}
clear(){
let tempQueue = this.queue1;
this.queue1 = [];
this.queue2 = [];
return tempQueue;
}
}
// Example usage:
const stack = new Stack();
stack.push(1)
stack.push(2)
stack.push(3)
stack.pop()
stack.peek()
console.log(stack.pop());
console.log(stack.peek());
Time complexity: O(n) for popping elements but other operation like ‘push’ have only 0(1) time complexity.
Space complexity: O(n) for storing elements in the queue.
Contact Us