Implement a Stack using Queue

Learn how to implement a stack using a single queue in javascript.

Implementation

• We will be using a single queue for creating the stack.
• So every time we will add a new data to the queue, we will move the existing data to the back of the new data.
• This way we will be able to mimic the stack implementation using the queue operations.

Implementing stack using a single queue

function Stack(){
   let queue = new Queue();

   //Other methods go here

}

---

Pushing data in the stack

We will enqueue the data in the queue and move the existing data to the back of the new data.

//Push
  this.push = function(elm){
    let size = queue.size();
    
    queue.enqueue(elm);
    
    //Move old data after the new data
    for(let i = 0; i < size; i++){
      let x = queue.dequeue();
      queue.enqueue(x);
    }
  }

---

Pop the data from the stack

//Pop
  this.pop = function(){
    if(queue.isEmpty()){
      return null;
    }
    
    return queue.dequeue();
  }

---

Peek the data in the stack

//Peek
  this.peek = function(){
    if(queue.isEmpty()){
      return null;
    }
    
    return queue.front();
  }

---

Size of the stack

//Size
  this.size = function(){
    return queue.size();
  }

---

Check if stack is empty

//IsEmpty
  this.isEmpty = function(){
    return queue.isEmpty();
  }

---

Clear the stack

//Clear
  this.clear = function(){
    queue.clear();
    return true;
  }

---

Convert the stack to an array

//ToArray
  this.toArray = function(){
    return queue.toArray();
  }

---

Complete Code

function Stack() {
  let queue = new Queue();
  
  //Push
  this.push = function(elm){
    let size = queue.size();
    
    queue.enqueue(elm);
    
    //Move old data after the new data
    for(let i = 0; i < size; i++){
      let x = queue.dequeue();
      queue.enqueue(x);
    }
  }
  
  //Pop
  this.pop = function(){
    if(queue.isEmpty()){
      return null;
    }
    
    return queue.dequeue();
  }
  
  //Peek
  this.peek = function(){
    if(queue.isEmpty()){
      return null;
    }
    
    return queue.front();
  }
  
  //Size
  this.size = function(){
    return queue.size();
  }
  
  //IsEmpty
  this.isEmpty = function(){
    return queue.isEmpty();
  }
  
  //Clear
  this.clear = function(){
    queue.clear();
    return true;
  }
  
  //ToArray
  this.toArray = function(){
    return queue.toArray();
  }
}

Input:
let stack = new Stack();   //creating new instance of Stack
 stack.push(1);
 stack.push(2);
 stack.push(3);
 console.log(stack.peek());
 console.log(stack.isEmpty());
 console.log(stack.size());
 console.log(stack.pop());
 console.log(stack.toArray());
 console.log(stack.size());
 stack.clear();  //clear the stack
 console.log(stack.isEmpty());

Output:
3
false
3
3
[2, 1]
2
true

We can wrap this inside a closure and IIFE (Immediately Invoked Function Expression) to make all the properties and methods private.

let Stack = (function(){

return function Stack() {
    let queue = new Queue();

    //Push
    this.push = function(elm){
      let size = queue.size();

      queue.enqueue(elm);

      //Move old data after the new data
      for(let i = 0; i < size; i++){
        let x = queue.dequeue();
        queue.enqueue(x);
      }
    }

    //Pop
    this.pop = function(){
      if(queue.isEmpty()){
        return null;
      }

      return queue.dequeue();
    }

    //Peek
    this.peek = function(){
      if(queue.isEmpty()){
        return null;
      }

      return queue.front();
    }

    //Size
    this.size = function(){
      return queue.size();
    }

    //IsEmpty
    this.isEmpty = function(){
      return queue.isEmpty();
    }

    //Clear
    this.clear = function(){
      queue.clear();
      return true;
    }

    //ToArray
    this.toArray = function(){
      return queue.toArray();
    }
  }

}());

Time Complexity

Because we are copying the data at the end of the queue after adding a new data, the insert operation changes to O(N).

---

Space Complexity