JavaScript Series #122: Mastering Stacks and Queues in JavaScript

Welcome to another installment of our JavaScript Series! Today, we're diving into two fundamental linear data structures: Stacks and Queues. Understanding these concepts is crucial for any JavaScript developer, as they form the bedrock of many algorithms and application architectures. While JavaScript arrays can often mimic their behavior, truly grasping their principles and optimal implementations will elevate your problem-solving skills.

Let's explore what Stacks and Queues are, how they operate, how to implement them efficiently in JavaScript, and their common use cases.

---

What is a Stack?

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Imagine a stack of plates: you can only add a new plate to the top, and you can only remove the topmost plate. The last plate you put on is the first one you take off.

This principle makes stacks useful for scenarios where the most recently added item needs to be processed first.

Key Stack Operations:

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

Implementing a Stack in JavaScript (Array-based):

The simplest way to implement a stack in JavaScript is by using an array. JavaScript's built-in array methods push() and pop() directly correspond to stack operations, making it incredibly straightforward.

class Stack {
    constructor() {
        this.items = []; // An array to hold stack elements
    }

    // Add an element to the top of the stack
    push(element) {
        this.items.push(element);
    }

    // Remove and return the top element
    pop() {
        if (this.isEmpty()) {
            return "Underflow"; // Or throw an error
        }
        return this.items.pop();
    }

    // Return the top element without removing it
    peek() {
        if (this.isEmpty()) {
            return "No elements in Stack";
        }
        return this.items[this.items.length - 1];
    }

    // Check if the stack is empty
    isEmpty() {
        return this.items.length === 0;
    }

    // Return the size of the stack
    size() {
        return this.items.length;
    }

    // (Optional) Clear the stack
    clear() {
        this.items = [];
    }

    // (Optional) Print the stack elements
    printStack() {
        let str = "";
        for (let i = this.items.length - 1; i >= 0; i--) {
            str += this.items[i] + "\n";
        }
        return str;
    }
}

Usage Example:

const myStack = new Stack();

console.log(myStack.isEmpty()); // true

myStack.push(10);
myStack.push(20);
myStack.push(30);

console.log(myStack.printStack());
// Output:
// 30
// 20
// 10

console.log(myStack.peek()); // 30
console.log(myStack.pop());  // 30
console.log(myStack.size()); // 2

console.log(myStack.printStack());
// Output:
// 20
// 10

Real-World Applications of Stacks:

• Function Call Stack: When functions are called in a program, they are pushed onto a call stack. When a function returns, it's popped off.
• Undo/Redo Functionality: Text editors and graphic design software often use stacks to manage changes, allowing users to undo (pop) or redo (push) actions.
• Browser History: The back button in a web browser works like a stack, pushing new pages as you navigate and popping them off when you go back.
• Expression Evaluation and Parsing: Used in compilers to evaluate arithmetic expressions and check for balanced parentheses.

---

What is a Queue?

A Queue is another linear data structure that adheres to the FIFO (First In, First Out) principle. Think of a line at a grocery store: the first person to join the line is the first person to be served. New people join the back of the line, and people are served from the front.

Queues are perfect for situations where items need to be processed in the order they arrived.

Key Queue Operations:

• enqueue(element): Adds an element to the back (or "rear") of the queue.
• dequeue(): Removes and returns the element from the front of the queue.
• front() or peek(): Returns the front element without removing it.
• isEmpty(): Checks if the queue is empty.
• size(): Returns the number of elements in the queue.

Implementing a Queue in JavaScript (Class-based, optimized):

While an array can be used for a queue (using push() for enqueue and shift() for dequeue), shift() has a performance drawback: it re-indexes all remaining elements, leading to O(n) time complexity for dequeue operations. For better performance, especially with large queues, we can implement a queue using an object to store items and track headIndex and tailIndex pointers. This provides O(1) average time complexity for both enqueue and dequeue.

class Queue {
    constructor() {
        this.items = {}; // Using an object for O(1) dequeue
        this.headIndex = 0;
        this.tailIndex = 0;
    }

    // Add an element to the back of the queue
    enqueue(element) {
        this.items[this.tailIndex] = element;
        this.tailIndex++;
    }

    // Remove and return the front element
    dequeue() {
        if (this.isEmpty()) {
            return undefined; // Or throw an error
        }
        const element = this.items[this.headIndex];
        delete this.items[this.headIndex]; // Remove the element
        this.headIndex++;
        return element;
    }

    // Return the front element without removing it
    front() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.headIndex];
    }

    // Check if the queue is empty
    isEmpty() {
        return this.headIndex === this.tailIndex;
    }

    // Return the size of the queue
    size() {
        return this.tailIndex - this.headIndex;
    }

    // (Optional) Clear the queue
    clear() {
        this.items = {};
        this.headIndex = 0;
        this.tailIndex = 0;
    }

    // (Optional) Print queue elements (for debugging)
    printQueue() {
        let str = "";
        for (let i = this.headIndex; i < this.tailIndex; i++) {
            str += this.items[i] + " ";
        }
        return str.trim();
    }
}

Usage Example:

const myQueue = new Queue();

console.log(myQueue.isEmpty()); // true

myQueue.enqueue("Task 1");
myQueue.enqueue("Task 2");
myQueue.enqueue("Task 3");

console.log(myQueue.printQueue()); // Task 1 Task 2 Task 3

console.log(myQueue.front());    // Task 1
console.log(myQueue.dequeue());  // Task 1
console.log(myQueue.size());     // 2

console.log(myQueue.printQueue()); // Task 2 Task 3

myQueue.enqueue("Task 4");
console.log(myQueue.printQueue()); // Task 2 Task 3 Task 4

Real-World Applications of Queues:

• Printer Queues: Documents are printed in the order they were submitted.
• Task Scheduling: Operating systems use queues to manage processes, giving CPU time to processes in the order they request it.
• Message Queuing: In distributed systems, messages are often placed in queues to be processed by consumers in a reliable, ordered fashion.
• Breadth-First Search (BFS) Algorithm: Used in graph traversal to explore all neighbors at the current depth before moving to the next level.

---

Stacks vs. Queues: Key Differences

While both Stacks and Queues are linear data structures, their fundamental difference lies in their processing order:

• Order of Processing:
  • Stack: LIFO (Last In, First Out)
  • Queue: FIFO (First In, First Out)
• Primary Operations:
  • Stack: push (add to top), pop (remove from top)
  • Queue: enqueue (add to rear), dequeue (remove from front)
• Analogy:
  • Stack: A stack of plates, a pile of books.
  • Queue: A line of people, a queue at a ticket counter.
• Use Cases:
  • Stack: Function call management, undo/redo, backtracking algorithms.
  • Queue: Task scheduling, message buffering, breadth-first search.

---

Conclusion

Stacks and Queues are indispensable tools in a developer's arsenal. Their distinct LIFO and FIFO behaviors make them suitable for a wide range of problems, from managing program flow to organizing data processing. By understanding their principles and implementing them efficiently in JavaScript, you gain powerful techniques for building more robust and performant applications.

Practice implementing these data structures and consider how they could simplify common programming challenges you encounter. Happy coding!