Day 76: Stacks and Queues - Harshil Chovatiya

Day 76: Stacks and Queues

Brief: Day 76 focuses on two essential linear data structures: stacks and queues. Stacks follow the Last-In-First-Out (LIFO) principle, while queues adhere to the First-In-First-Out (FIFO) principle. These structures find applications in various domains, including algorithmic problem-solving, system design, and real-world scenarios. We'll delve into their characteristics, implementations, operations, and solve problems to reinforce our understanding.

Topics Covered:

1. Stacks:

   - Definition: A stack is a collection of elements with two principal operations: push (adds an element to the top) and pop (removes the top element).

   - Implementation: Using arrays or linked lists to represent stacks.

   - Applications: Function call stack, expression evaluation, backtracking algorithms.

2. Queues:

   - Definition: A queue is a collection of elements with two principal operations: enqueue (adds an element to the rear) and dequeue (removes the front element).

   - Implementation: Using arrays or linked lists to represent queues.

   - Applications: Task scheduling, breadth-first search, printer spooling.

3. Common Operations and Problems:

   - Stack Operations: Push, pop, peek (retrieve the top element without removing), and isEmpty (check if the stack is empty).

   - Queue Operations: Enqueue, dequeue, peek, and isEmpty.

   - Problem Solving: Solving problems using stacks (e.g., balanced parentheses) and queues (e.g., level-order traversal of a tree).

In-Depth Examples:

1. Stack Implementation using Arrays:

                                   
                                   
       class Stack {
           constructor() {
               this.items = [];
           }
       
           push(item) {
               this.items.push(item);
           }
       
           pop() {
               if (!this.isEmpty()) {
                   return this.items.pop();
               }
               return null;
           }
       
           peek() {
               if (!this.isEmpty()) {
                   return this.items[this.items.length - 1];
               }
               return null;
           }
       
           isEmpty() {
               return this.items.length === 0;
           }
       }
                                   
                               

2. Queue Implementation using Linked Lists:

                                   
                                   
       class Node {
           constructor(data) {
               this.data = data;
               this.next = null;
           }
       }
       
       class Queue {
           constructor() {
               this.front = null;
               this.rear = null;
           }
       
           enqueue(item) {
               const newNode = new Node(item);
               if (!this.front) {
                   this.front = newNode;
               } else {
                   this.rear.next = newNode;
               }
               this.rear = newNode;
           }
       
           dequeue() {
               if (!this.isEmpty()) {
                   const item = this.front.data;
                   this.front = this.front.next;
                   if (!this.front) {
                       this.rear = null;
                   }
                   return item;
               }
               return null;
           }
       
           peek() {
               return this.front ? this.front.data : null;
           }
       
           isEmpty() {
               return this.front === null;
           }
       }
                                   
                               

3. Problem: Valid Parentheses using Stack:

                                   
                                   
       function isValidParentheses(s) {
           const stack = [];
           const mapping = {')': '(', '}': '{', ']': '['};
           for (let char of s) {
               if (char in mapping) {
                   const topElement = stack.pop() || '#';
                   if (mapping[char] !== topElement) {
                       return false;
                   }
               } else {
                   stack.push(char);
               }
           }
           return stack.length === 0;
       }
                                   
                               

Conclusion:

Day 76 has equipped us with a solid understanding of stacks and queues, their implementations, operations, and applications. These data structures play pivotal roles in various algorithms and real-world scenarios, making them indispensable in our journey through data structures and algorithms. As we progress, let's continue exploring and applying stacks and queues in problem-solving to sharpen our skills and deepen our understanding.

Social Media