Data Structure and Algorithms with JS - Part 3 : Stack and Queue

Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed.

Stacks are commonly used to store data temporarily while a program is executing. They can be used to implement function calls, as well as to reverse the order of items.

Operations that are typically supported by stacks include:

• push: adds an element to the top of the stack
• pop: removes the element at the top of the stack and returns it
• peek: returns the element at the top of the stack without removing it
• isEmpty: returns true if the stack is empty, false otherwise

Here is an Example of a Stack implementation using LinkedList in Javascript

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

class Stack {
  constructor() {
    this.top = null
    this.bottom = null
    this.length = 0
  }
  peek() {
    return this.bottom.value
  }
  isEmpty() {
    return !!this.length
  }
  push(value) {
    let newNode = new StackNode(value)
    if (!this.top) {
      this.top = newNode
      this.bottom = newNode
    } else {
      newNode.next = this.top
      this.top = newNode
    }
    this.length++
    return this
  }
  pop() {
    if (!this.top) return null
    let value = this.top.value
    if (this.length === 1) {
      this.bottom = null
    }
    this.top = this.top.next
    this.length--
    return value
  }
}
const myStack = new Stack()
console.log(myStack.push("google"))
/**
 Stack {
  top: StackNode { value: 'google', next: null },
  bottom: StackNode { value: 'google', next: null },
  length: 1
}
 */
console.log(myStack.push("udemy"))
/**
 Stack {
  top: StackNode {
    value: 'udemy',
    next: StackNode { value: 'google', next: null }
  },
  bottom: StackNode { value: 'google', next: null },
  length: 2
}
 */
console.log(myStack.push("discord"))
/**
 Stack {
  top: StackNode {
    value: 'discord',
    next: StackNode { value: 'udemy', next: [StackNode] }
  },
  bottom: StackNode { value: 'google', next: null },
  length: 3
}
 */
console.log(myStack.pop()) //discord
console.log(myStack.pop()) //udemy
console.log(myStack.peek()) //google
console.log(myStack.isEmpty()) //true

We can implement stack using array and linked list both.

Array-based stack: This type of stack is implemented using an array, where the elements are stored in contiguous memory locations. The array can be resized as needed to accommodate new elements. Insertion and deletion operations are typically O(1) time complexity.

Linked list-based stack: This type of stack is implemented using a linked list, where each node in the list contains a value and a pointer to the next node in the list. Insertion and deletion operations are typically O(1) time complexity.

Stacks are widely used in computer science and have many practical applications. Some common uses of stacks include:

Evaluating mathematical expressions: Stacks are often used to evaluate mathematical expressions, such as infix, prefix, and postfix notation.

Compiler design: Stacks are used in compiler design for tasks such as syntax parsing, symbol table management, and code generation.

Function calls: Stacks are used to store information about function calls in a program, including the return address and the values of local variables. Javascript call stack and an error we encounter in infinite loop stack overflow. 😝😝

Undo/redo functionality: Stacks can be used to implement undo/redo functionality in text editors, image editors, and other software applications.

Backtracking: Stacks can be used to store the state of a problem as it is being solved, allowing the algorithm to backtrack and try alternative solutions if necessary.

Maze solving: Stacks can be used to store the path taken during a maze-solving algorithm, allowing the algorithm to backtrack and try alternative paths if necessary.

Topological sorting: Stacks can be used to implement topological sorting algorithms, which are used to order the vertices of a directed acyclic graph.

Memory management: Stacks are used in memory management to keep track of the memory used by a program and to allocate and deallocate memory as needed.

DFS (depth-first search): Stacks are used to implement DFS algorithms, which traverse the graph or tree vertically.

Here are some Leetcode problems that involve stacks:

1. Valid Parentheses: Given a string containing just the characters ’(’, ’)’, ’{’, ’}’, ’[’ and ’]’, determine if the input string is valid.

2. Evaluate Reverse Polish Notation: Evaluate the value of an arithmetic expression in Reverse Polish Notation.

3. Basic Calculator: Implement a basic calculator to evaluate a simple expression string.

4. Decode String: Given an encoded string, return its decoded string.

5. Min Stack: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

6. Maximal Rectangle: Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

7. Trapping Rain Water: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

8. Evaluate Division: Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers.

9. Remove Duplicate Letters: Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Queue

A queue is a linear data structure that follows the first-in, first-out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are often used to store data that needs to be processed in a specific order, and they support a limited set of operations, such as inserting an element at the back of the queue (also known as enqueuing), removing an element from the front of the queue (also known as dequeuing), and checking the element at the front of the queue.

Queues can be implemented using an array or a linked list. Array-based queues have a fixed size and may need to be resized if the number of elements exceeds the capacity of the array. Linked list-based queues can grow and shrink dynamically as elements are added and removed.

Here is an Example of a Queue implementation using LinkedList in Javascript

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

class Queue {
  constructor() {
    this.first = null
    this.last = null
    this.length = 0
  }
  peek() {
    return this.first.value
  }
  enqueue(value) {
    let newNode = new QueueNode(value)
    if (!this.first) {
      this.first = newNode
      this.last = newNode
    }
    this.last.next = newNode
    this.last = newNode
    this.length++
    return this.last
  }
  dequeue() {
    if (!this.first) return null
    if (this.first === this.last) this.last = null
    let value = this.first.value
    this.first = this.first.next
    this.length--
    return value
  }
}
const myQ = new Queue()
console.log(myQ.enqueue("Joy")) //QueueNode { value: 'Joy', next: null }
console.log(myQ.enqueue("Matt")) //QueueNode { value: 'Matt', next: null }
console.log(myQ.enqueue("Pav")) //QueueNode { value: 'Pav', next: null }
console.log(myQ.dequeue()) //Joy
console.log(myQ.enqueue("Sam")) //QueueNode { value: 'Sam', next: null }
console.log(myQ.dequeue()) //Matt
console.log(myQ.dequeue()) //Pav

There are several types of queue data structures, each with its own characteristics and use cases:

Standard queue: A standard queue is a basic queue data structure that supports the operations of enqueuing and dequeuing elements. It can be implemented using an array or a linked list.

Circular queue: A circular queue is a queue data structure that uses a fixed-size array and wraps around when the end of the array is reached. It allows for efficient insertion and deletion operations, but requires careful handling to avoid overwriting elements that have not yet been dequeued.

Priority queue: A priority queue is a queue data structure where each element has a priority associated with it. Elements are dequeued in order of their priority, with the highest priority element being dequeued first. Priority queues can be implemented using an array, a linked list, or a heap data structure.

Double-ended queue (deque):A double-ended queue (deque) is a queue data structure that allows for efficient insertion and deletion at both ends of the queue. It can be implemented using an array or a linked list.

Blocking queue: A blocking queue is a queue data structure that blocks enqueuing operations if the queue is full and dequeuing operations if the queue is empty. This can be used to synchronize multiple threads or processes that are accessing the queue.

Concurrent queue: A concurrent queue is a queue data structure that is designed to be thread-safe, allowing multiple threads to enqueue and dequeue elements concurrently without the need for explicit synchronization.

Some common uses of queues include:

Task scheduling: Queues can be used to store tasks that need to be processed in a specific order, such as jobs in a printer queue or tasks in a CPU scheduling algorithm.

Communication buffers: Queues can be used to store data that needs to be transmitted between two systems, such as packets in a network communication protocol.

BFS (breadth-first search): Queues are used to implement BFS algorithms, which traverse the graph or tree horizontally (level by level)..

Event-driven programming: Queues can be used to store events that need to be processed in a specific order, such as user input events in a graphical user interface (GUI).

Asynchronous programming: Queues can be used to store tasks that need to be executed asynchronously, such as in a web server handling multiple requests simultaneously.

Here are some Leetcode problems that involve queues :

1. Implement Queue using Stacks: Implement a first-in, first-out (FIFO) queue using only two stacks.

2. Rotate Array: Given an array, rotate the array to the right by k steps, where k is non-negative.

3. Queue Reconstruction by Height: Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

4. Find Median from Data Stream: Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

5. Sliding Window Maximum: Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

6. Design Circular Queue: Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

7. Number of Islands: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

8. Number of Provinces: There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c. A province is a group of directly or indirectly connected cities and no other cities outside of the group. Return the total number of provinces.

Conclusion

In conclusion, we can say that Stacks and Queues are linear data structures that are used to store and manipulate data in a specific order. Stacks follow the last-in, first-out (LIFO) principle, while Queues follow the first-in, first-out (FIFO) principle. Both data structures support a limited set of operations, such as pushing and popping elements in the case of stacks, and enqueuing and dequeuing elements in the case of queues.