Skip to content

A Comprehensive Guide to Implementing Stack, Queue and Deque Data Structures using Linked Lists in JavaScript

Posted on:April 7, 2023 at 12:35 PM

Stack, queue and deque example

Table of contents

Open Table of contents

Stack

A stack is a linear type data structure that follows the Last In First Out (LIFO) principle means that the last element inserted in stack comes out first. You can think of the stack data structure as the pile of plates on top of another.
Stack example

Stack has three main operations. They are:

Overflow and underflow

Overflow happens when we try to push more items on a stack than it can be hold. In details, when we try to push an item into a stack that has already reached its maximum size then the insertion will generate an error. So we need to check the stack condition before insertion.
Underflow happens when we try to pop an item from an empty stack. So in this situation pop operation will generate an error.

Application of Stack Data Structure

Application of Stack in real life

Big O of common operations

Big O Of Stack

Stack implementation using Linked List

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  
  push(value) {
  	let node= new Node(value)
    node.next = this.head
    this.head = node
    this.length++
  }
  
  pop(){
  	if(this.isEmpty()) return
    
    const removedNode = this.head
    this.head = removedNode.next
    this.length--
    return removedNode.value
  }
  
  peek() {
  	if(this.isEmpty()) return
    return this.head.value
  }
  
  isEmpty() {
  	return this.length === 0
  }
  
  print() {
  	if(this.isEmpty()) return
    let data = this.head
    
    while(data) {
			console.log(data.value)
      
      data = data.next
    }
  }
}

let stack = new Stack()
stack.push(5)
stack.push(10)
stack.push(15)
stack.push(20)
console.log(`POPed Value: ${stack.pop()}`)
console.log(`Head/peek Value: ${stack.peek()}`)
stack.print()

Queue

From wikipedia In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. So operations in queue are performed in First In First Out (FIFO) order - the item that inserts in first will come out first. You can think of the queue data structure as the ticket queue outside of a cinema hall.
Queue

Queue has three main operations. They are:

Application of Queue Data Structure

  1. Task Scheduling
  2. Resource Allocation
  3. Batch Processing
  4. Message Buffering
  5. Event Handling
  6. Traffic Management
  7. Operating systems
  8. Network protocols
  9. Printer queues
  10. Web servers
  11. When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
  12. When data is transferred asynchronously (data not necessarily received at the same rate as sent) between two processes. Examples include IO Buffers, pipes, etc.
  13. Buffer for devices like keyboard
  14. CPU Scheduling
  15. Memory management
  16. Queues in routers/ switches
  17. Mail Queues

Issues in applications of Queue

  1. Overflow: If a queue has a fixed size, it can become full, leading to a queue overflow. This can happen if elements are added to the queue faster than they are removed. To prevent overflow, some implementations use dynamic resizing or circular buffers.
  2. Underflow: If a queue is empty and an attempt is made to remove an element, this can lead to a queue underflow. This can happen if elements are removed from the queue faster than they are added. To prevent underflow, some implementations use sentinel values or null pointers to represent an empty queue.

Big O of common operations

Big O Of Queue

Queue implementation using Linked List

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  enqueue(value) {
  	let node= new Node(value)
    
    if(this.isEmpty()) {
    	this.head = node
      this.tail = node
    } else {
    	this.tail.next = node
      this.tail = node
    }
    this.size++
  }
  
  dequeue(){
  	if(this.isEmpty()) return
    
    const removedNode = this.head
    
    if (this.size === 1) {
      this.head = null
      this.tail = null
      this.size--
      return removedNode.value
    }
   
    this.head = removedNode.next
    this.size--
    return removedNode.value
  }
  
  peek() {
  	if(this.isEmpty()) return
    return this.head.value
  }
  
  isEmpty() {
  	return this.size === 0
  }
  
  print() {
  	if(this.isEmpty()) return
    let data = this.head
    
    while(data) {
			console.log(data.value)
      
      data = data.next
    }
  }
}

let queue = new Queue()
queue.enqueue(5)
queue.enqueue(10)
queue.enqueue(15)
queue.enqueue(20)
console.log(`POPed Value: ${queue.dequeue()}`)
console.log(`Head/peek Value: ${queue.peek()}`)
queue.print()

Deque

From wikipedia: In computer science, a double-ended queue (abbreviated to deque, pronounced deck, like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).It is also often called a head-tail linked list, though properly this refers to a specific data structure implementation of a deque.
In short, it is a type of queue data structure that allows insertion and removal of elements from both ends(front or rear). Dequeue

Application of Deque Data Structure

  1. Applied as both stack and queue, as it supports both operations.
  2. Storing a web browser’s history.
  3. Storing a software application’s list of undo operations.
  4. Job scheduling algorithm
  5. Palindrome checking
  6. Graph traversal
  7. Task scheduler
  8. Multi-level undo/redo functionality
  9. In computer science, deque can be used in many algorithms like LRU Cache, Round Robin Scheduling, Expression Evaluation.

Big O of common operations

Big O Of Dequeue

Deque implementation using Linked List

The methods we will implement in this article is given below:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.previous = null;
  }
}

class Deque {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  addToFront(value) {
  	let node= new Node(value)
    
    if(this.isEmpty()) {
    	this.head = node
      this.tail = node
    } else {
    	this.head.previous = node
      node.next = this.head
      this.head = node
    }
    this.size++
  }
  
  addToRear(value) {
  	let node= new Node(value)
    
    if(this.isEmpty()) {
    	this.head = node
      this.tail = node
    } else {
    	this.tail.next = node
      node.previous = this.tail
      this.tail = node
    }
    this.size++
  }
  
  removeFromFront(){
  	if(this.isEmpty()) return
    
    const removedNode = this.head
    
    if (this.size === 1) {
      this.head = null
      this.tail = null
      this.size--
      return removedNode.value
    }
   
    this.head = removedNode.next
    this.head.previous = null
    this.size--
    return removedNode.value
  }
  
  removeFromRear(){
  	if(this.isEmpty()) return
    
    const removedNode = this.tail
    
    if (this.size === 1) {
      this.head = null
      this.tail = null
      this.size--
      return removedNode.value
    }
   
    this.tail = removedNode.previous
    this.tail.next = null
    this.size--
    return removedNode.value
  }
  
  peekFront() {
  	if(this.isEmpty()) return
    return this.head.value
  }
  
  peekRear() {
  	if(this.isEmpty()) return
    return this.tail.value
  }
  
  isEmpty() {
  	return this.size === 0
  }
  
  print() {
  	if(this.isEmpty()) return
    let data = this.head
    
    while(data) {
			console.log(data.value)
      
      data = data.next
    }
  }
}

let deque = new Deque()
deque.addToFront(5)
deque.addToRear(10)
deque.addToRear(15)
deque.addToRear(20)
deque.addToFront(2)
deque.print()
console.log(`Remove from front Value: ${deque.removeFromFront()}`)
console.log(`Remove from end Value: ${deque.removeFromRear()}`)
console.log(`Head Value: ${deque.peekFront()}`)
console.log(`Tail Value: ${deque.peekRear()}`)
deque.print()

Difference between Stack and Queue

  1. A stack is a data structure that stores a collection of elements, with operations to push (add) and pop (remove) elements from the top of the stack. A queue is a data structure that stores a collection of elements, with operations to enqueue (add) elements at the back of the queue, and dequeue (remove) elements from the front of the queue.
  2. Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list. Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.
  3. Stacks are often used for tasks that require backtracking, such as parsing expressions or implementing undo functionality. Queues are often used for tasks that involve processing elements in a specific order, such as handling requests or scheduling tasks.
  4. Insertion and deletion in stacks takes place only from one end of the list called the top. Insertion and deletion in queues takes place from the opposite ends of the list. The insertion takes place at the rear of the list and the deletion takes place from the front of the list.
  5. Insert operation is called push operation. Insert operation is called enqueue operation.
  6. Stacks are implemented using an array or linked list data structure. Queues are implemented using an array or linked list data structure.
  7. Delete operation is called pop operation. Delete operation is called dequeue operation.
  8. In stacks we maintain only one pointer to access the list, called the top, which always points to the last element present in the list. In queues we maintain two pointers to access the list. The front pointer always points to the first element inserted in the list and is still present, and the rear pointer always points to the last inserted element.
  9. Stack is used in solving problems works on recursion. Queue is used in solving problems having sequential processing.
  10. Stacks are often used for recursive algorithms or for maintaining a history of function calls. Queues are often used in multithreaded applications, where tasks are added to a queue and executed by a pool of worker threads.
  11. Stack does not have any types. Queue is of three types – 1. Circular Queue 2. Priority queue 3. double-ended queue.
  12. Examples of stack-based languages include PostScript and Forth. Examples of queue-based algorithms include Breadth-First Search (BFS) and printing a binary tree level-by-level.

References

  1. https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
  2. https://www.geeksforgeeks.org/stack-data-structure/
  3. https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-stack/
  4. https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-stack
  5. https://en.wikipedia.org/wiki/Queue_(abstract_data_type)
  6. https://www.geeksforgeeks.org/applications-of-queue-data-structure/
  7. https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-queue
  8. https://en.wikipedia.org/wiki/Double-ended_queue
  9. https://www.geeksforgeeks.org/deque-set-1-introduction-applications/
  10. https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-deque-double-ended-queue
  11. https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/