Implement queue using two stack

Learn how to implement queue using two stack in javascript.

We will create the queue data structure using two different stacks instead of using an array or linkedlist.

Following is the list of operations we will be adding in our queue.

• enqueue: Adds the element in the queue.
• dequeue: Removes the element from the queue.
• peek: Returns the top element.

There are two different approaches which can be used to create queue using stack.
1. By making the enqueue operation costly.
2. Making the dequeue operation costly.

As you know that generally the enqueue and dequeue operation of queue is performed in O(1) time.

But as we are using stack rather than array or linked list, either one of the operation will be running in O(n) time. It is up to us to decide which way we want to proceed.

Implement queue using stack by making the enqueue operation costly.

Every time an item is added to the queue first copy all the items from the stack1 to the stack2 then add the new element to the stack2.

Then again copy all the items back from stack2 to stack1.

This way we keep FIFO principal in place by keeping the first element at front and last element at end.

//Enqueue costly
class QueueUsingStack {
  constructor() {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }
  
  enqueue = (x) => {
    while(!this.stack1.isEmpty()){
      this.stack2.push(this.stack1.pop());
    }
    
    this.stack2.push(x);
    
    while(!this.stack2.isEmpty()){
      this.stack1.push(this.stack2.pop());
    }
  }
  
  dequeue = () => {
    return this.stack1.pop();
  }
  
  peek = () => {
    return this.stack1.peek();
  }
  
  size = () => {
    return this.stack1.size();
  }
  
  isEmpty = () => {
    return this.stack1.isEmpty();
  }
  
  clear = () => {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }
}

Input:
const queue = new QueueUsingStack();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.peek());

Output:
10
10
20
20
30

Time Complexity

This is the most efficient way because once we have stored the data in organized way all other operations works perfectly, we don’t need to change them.

---

Making the dequeue costly

In this we will store the element in LIFO order using stack, but while removing the element we will have to copy all the elements into another stack so that the first element is at the top and can be removed.

And then copy all the elements back to the first stack.

The only problem with this way is that for the peek operation also we have to do the same process, this makes two operations to run in O(n) time which makes it highly inefficient.

It is always to better to store the data in organized way so that all the later process don’t get affected.

class QueueUsingStack {
  constructor() {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }
  
  enqueue = (x) => {
    this.stack1.push(x);
  }
  
  dequeue = () => {
    while(!this.stack1.isEmpty()){
      this.stack2.push(this.stack1.pop());
    }
    
    const item = this.stack2.pop();
    
    while(!this.stack2.isEmpty()){
      this.stack1.push(this.stack2.pop());
    }
    
    return item;
  }
  
  peek = () => {
    while(!this.stack1.isEmpty()){
      this.stack2.push(this.stack1.pop());
    }
    
    const item = this.stack2.peek();
    
    while(!this.stack2.isEmpty()){
      this.stack1.push(this.stack2.pop());
    }
    
    return item;
  }
  
  size = () => {
    return this.stack1.size();
  }
  
  isEmpty = () => {
    return this.stack1.isEmpty();
  }
  
  clear = () => {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }
}

Input:
const queue = new QueueUsingStack();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.peek());

Output:
10
10
20
20
30

Time Complexity