Stacks & Queues

Stacks and Queues are abstract data types that restrict how you insert and remove elements. They can both be implemented under the hood using either Arrays or Linked Lists.

The Stack (LIFO)

A Stack follows the LIFO (Last-In, First-Out) principle. Think of a physical stack of plates in a cafeteria. You add new plates to the top, and when a customer needs a plate, they take one off the top. The last plate placed on the stack is the first one removed.

Core Operations:

• Push: Add an element to the top ($O(1)$).
• Pop: Remove the top element ($O(1)$).
• Peek / Top: Look at the top element without removing it ($O(1)$).

Real-World Uses:

• Undo functionality in text editors (Ctrl+Z).
• Call Stack in programming languages (managing function calls and recursion).
• Browser History (Back button).

The Queue (FIFO)

A Queue follows the FIFO (First-In, First-Out) principle. Think of a physical line of people at a movie theater. The first person to get in line is the first person to buy a ticket and leave the line. People join the line at the back.

Core Operations:

• Enqueue (Push): Add an element to the back ($O(1)$).
• Dequeue (Shift/Pop): Remove the front element ($O(1)$).
• Peek / Front: Look at the front element without removing it ($O(1)$).

Real-World Uses:

• Task Scheduling / Job Queues (e.g., printing documents).
• Breadth-First Search (BFS) in graphs.
• Handling asynchronous requests in web servers (like Node.js Event Loop).

[!WARNING] If you implement a Queue using a standard JavaScript/Python array, calling .shift() to remove the front element is $O(N)$ because the entire array must shift left! To achieve true $O(1)$ queue operations, you must implement it using a Linked List or a Ring Buffer.

Advanced Variations

Double-Ended Queue (Deque)

Pronounced "deck". A queue where you can add or remove elements from both the front and the back in $O(1)$ time. Implementation: Usually built using a Doubly Linked List.

Monotonic Stack

A specialized stack where the elements are kept strictly increasing or strictly decreasing. It is a powerful tool for solving specific array problems in $O(N)$ time.

Example Problem: Find the "Next Greater Element" for every item in an array. Instead of an $O(N^2)$ nested loop, you iterate backwards. You pop elements off the stack if they are smaller than the current element. The top of the stack is guaranteed to be your "Next Greater Element".

function nextGreaterElement(arr: number[]): number[] {
  const result = new Array(arr.length).fill(-1);
  const stack: number[] = []; // Will hold values in monotonically decreasing order
  
  for (let i = arr.length - 1; i >= 0; i--) {
    // Pop smaller elements. They are useless now because the current element 
    // is bigger and is physically closer to any elements to the left of i.
    while (stack.length > 0 && stack[stack.length - 1] <= arr[i]) {
      stack.pop();
    }
    
    // The top of the stack is the next greater element
    if (stack.length > 0) {
      result[i] = stack[stack.length - 1];
    }
    
    // Push current element onto stack
    stack.push(arr[i]);
  }
  
  return result;
}