Implement Queues and Stacks in Javascript

Java collection framework provides stack and queue classes. However, in Javascript we do not have stacks and queues provided for us. In this blog, we are going to implement stacks and queues in two ways: using arrays and linked lists.

Stacks

Definition

“Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).”

Implement Stacks Using Arrays

class Stack{
  constructor(){
    this.items = []
  }
isEmpty(){
    return this.items.length === 0
  }
push(data){
    this.items.push(data)
  }
pop(){
    if(this.isEmpty()){
      return null
    }
    return this.items.pop()
  }
}
let s = new Stack()
s.push(1)
s.push(2)
s.push(3)
console.log(s)       //Stack { items: [ 1, 2, 3 ] }
console.log(s.pop()) //3
console.log(s.pop()) //2
console.log(s.pop()) //1
console.log(s.pop()) //null
s.isEmpty()          //true

Implement Stacks Using Linked Lists

class Node{
  constructor(data){
    this.val = data
    this.next = null
  }
}
class Stack{
  constructor(){
    this.root = null
    this.size = 0
  }
  isEmpty(){
    return this.size===0
  }
   push(data){
    let node = new Node(data)
    if(!this.root){
      this.root = node
    }else{
       let cur = this.root
       while(cur.next){
        cur = cur.next
    }
      cur.next = node
    }
      this.size++
   }
   pop(){
    if(this.isEmpty()) {
      return null
    }else if(this.size === 1){
      let res = this.root
      this.root = null
      this.size--
      return res
    }else{
      let cur = this.root
      while(cur.next && cur.next.next){
        cur = cur.next
      }
      let res = cur.next 
      cur.next = null
      this.size--
      return res
    }
  }
}
let stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)

console.log(stack.pop()) //Node { val: 4, next: null }
console.log(stack.pop()) //Node { val: 3, next: null }
console.log(stack.pop()) //Node { val: 2, next: null }
console.log(stack.pop()) //Node { val: 1, next: null }
console.log(stack.pop()) //null
stack.isEmpty()          //true

Queues

Definition

“A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).”

Implement Queues Using Arrays

class Queue{
  constructor(){
    this.items = []
  }
isEmpty(){
    return this.items.length === 0
  }
enqueue(data){
    this.items.push(data)
  }
dequeue(){
    if(this.isEmpty()){
      return null
    }
    return this.items.shift()
  }
}
let q = new Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
console.log(q)           //Queue { items: [ 1, 2, 3 ] }
console.log(q.dequeue()) //1
console.log(q.dequeue()) //2
console.log(q.dequeue()) //3
console.log(q.dequeue()) //null
q.isEmpty()              //true

Implement Queues Using Linked Lists

class Node{
  constructor(data){
    this.val = data
    this.next = null
  }
}
class Queue{
  constructor(){
    this.root = null
    this.size = 0
  }
  isEmpty(){
    return this.size===0
  }
  enqueue(data){
    let node = new Node(data)
    if(!this.root){
      this.root = node
     
    }else{
      let cur = this.root
      while(cur.next){
      cur = cur.next
    }
      cur.next = node
    }
      this.size++
  }
  dequeue(){
    if(this.isEmpty()) return null
    let res = this.root 
    this.root = this.root.next
    this.size--
    return res
  } 
}
let q = new Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
console.log(q.dequeue()) 
//Node {
//   val: 1,
//   next: Node { val: 2, next: Node { val: 3, next: [Node] } }
// }
console.log(q.dequeue())
// Node {
//   val: 2,
//   next: Node { val: 3, next: Node { val: 4, next: [Node] } }
// }
console.log(q.dequeue())
// Node { val: 3, next: Node { val: 4, next: null } }
console.log(q.dequeue())
// Node { val: 4, next: null }
console.log(q.dequeue()) // null
q.isEmpty() //true

Sources:

Array

Dynamic array