Queue Using2 Stacks Algorithm
The Queue Using 2 Stacks Algorithm is an ingenious method to implement a queue data structure using two stacks. A queue is a data structure that stores elements in a linear fashion, following the First-In-First-Out (FIFO) principle, which means that the element added first will be removed first. The basic operations of a queue are enqueue (add an element at the rear) and dequeue (remove an element from the front). However, a stack is a data structure that follows the Last-In-First-Out (LIFO) principle, where the element added last is the first to be removed. The basic operations of a stack are push (add an element at the top) and pop (remove an element from the top).
To implement a queue using two stacks, we can use the first stack (stack1) to enqueue elements and the second stack (stack2) to dequeue elements. When an element is enqueued, it is simply pushed onto stack1. When an element needs to be dequeued, it is popped from stack2 if it is not empty; otherwise, all elements from stack1 are transferred to stack2 in reverse order (by repeatedly popping from stack1 and pushing to stack2) and then the top element of stack2 is popped. This process ensures that the oldest element (enqueued first) is dequeued first, thus maintaining the FIFO property of a queue. By using this algorithm, we efficiently utilize the LIFO property of stacks to achieve the desired functionality of a queue data structure.
// implementation of Queue using 2 stacks
// contribution made by hamza chabchoub for a university project
class Queue {
constructor () {
this.inputStack = []
this.outputStack = []
}
// Push item into the inputstack
enqueue (item) {
this.inputStack.push(item)
}
dequeue (item) {
// push all items to outputstack
this.outputStack = []
if (this.inputStack.length > 0) {
while (this.inputStack.length > 0) {
this.outputStack.push(this.inputStack.pop())
}
}
// display the top element of the outputstack
if (this.outputStack.length > 0) {
console.log(this.outputStack.pop())
// repush all the items to the inputstack
this.inputStack = []
while (this.outputStack.length > 0) {
this.inputStack.push(this.outputStack.pop())
}
}
}
// display elements of the inputstack
listIn () {
let i = 0
while (i < this.inputStack.length) {
console.log(this.inputStack[i])
i++
}
}
// display element of the outputstack
listOut () {
let i = 0
while (i < this.outputStack.length) {
console.log(this.outputStack[i])
i++
}
}
}
// testing
const queue = new Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(8)
queue.enqueue(9)
console.log(queue.dequeue())
// ans = 1
console.log(queue.dequeue())
// ans = 2
