Stacks and Queues in JavaScript

This tutorial will cover the basics of stacks and queues, and provide you with JavaScript code examples for implementing and using these data structures.

Table of Contents

Stacks

• Definition
• Implementation
• Common operations
• Example use-case

Queues

• Definition
• Implementation
• Common operations
• Example use-case

Stacks

Definition

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The item added last is the first one to be removed.

Implementation

We will create a simple Stack class in JavaScript to implement our stack data structure.

javascriptCopy
class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

Common operations

• push(element): Adds an element to the top of the stack.
• pop(): Removes the top element from the stack and returns it.
• peek(): Returns the top element without removing it from the stack.
• isEmpty(): Returns true if the stack is empty, otherwise false.
• size(): Returns the number of elements in the stack.

Example use-case: Reverse a string

Let's reverse a string using a stack:

javascriptCopy
function reverseString(str) {
  const stack = new Stack();

  for (let i = 0; i < str.length; i++) {
    stack.push(str[i]);
  }

  let reversed = "";
  while (!stack.isEmpty()) {
    reversed += stack.pop();
  }

  return reversed;
}

console.log(reverseString("Hello, world!")); // Output: "!dlrow ,olleH"

Queues

Definition

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The item added first is the first one to be removed.

Implementation

We will create a simple Queue class in JavaScript to implement our queue data structure.

javascriptCopy
class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

Common operations

• enqueue(element): Adds an element to the end of the queue.
• dequeue(): Removes the front element from the queue and returns it.
• front(): Returns the front element without removing it from the queue.
• isEmpty(): Returns true if the queue is empty, otherwise false.
• size(): Returns the number of elements in the queue.

Example use-case:

Print binary numbers from 1 to n

Let's print the binary numbers from 1 to n using a queue:

javascriptCopy
function generateBinaryNumbers(n) {
  const queue = new Queue();
  let result = [];

  queue.enqueue("1");

  for (let i = 1; i <= n; i++) {
    let currentBinary = queue.dequeue();
    result.push(currentBinary);

    let nextBinary1 = currentBinary + "0";
    let nextBinary2 = currentBinary + "1";

    queue.enqueue(nextBinary1);
    queue.enqueue(nextBinary2);
  }

  return result;

  console.log(generateBinaryNumbers(5)); // Output: [ '1', '10', '11', '100', '101' ]
}

In this example, we use a queue to generate binary numbers from 1 to n. We initialize the queue with the binary number '1'. In each iteration, we dequeue the front element, add it to our result, and enqueue two new elements formed by appending '0' and '1' to the dequeued binary number. This continues until we have generated n binary numbers.

This tutorial provided an overview of stacks and queues, along with their implementations and use-cases in JavaScript. Stacks and queues are versatile data structures that can be applied to various problems to achieve efficient and organized solutions.