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

“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).”

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
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

“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).”

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
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