Eventually Bitwise

Stack

Overview

A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. The last element added to the stack is the first one to be removed. Think of it like a stack of physical plates.

Core Concepts

  • Push: Adding an element to the top of the stack.
  • Pop: Removing the top element from the stack.
  • Peek (or Top): Looking at the top element without removing it.
  • IsEmpty: Checking if the stack contains any elements.
  • Time Complexity:
    • Push: $O(1)$.
    • Pop: $O(1)$.
    • Peek: $O(1)$.
    • Search: $O(n)$.

Code Examples

class Stack<T> {
    private items: T[] = [];

    push(element: T): void { this.items.push(element); }
    pop(): T | undefined { return this.items.pop(); }
    peek(): T | undefined { return this.items[this.items.length - 1]; }
    isEmpty(): boolean { return this.items.length === 0; }
}

const history = new Stack<string>();
history.push("Page 1");
history.push("Page 2");
console.log(history.pop()); // "Page 2"

Use Cases

  • Function Call Stack: How programming languages manage active subroutines and return addresses.
  • Undo Mechanisms: In text editors, the last action performed is the first one undone.
  • Expression Parsing: Used by compilers to evaluate postfix notation or balance parentheses in code.

Gotchas

  • Stack Overflow: Occurs when a stack (specifically the call stack) exceeds its allocated memory, often due to infinite recursion.
  • Underflow: Attempting to pop or peek from an empty stack.

Related Notes

, ,