Stack#

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added is the first one to be removed. Think of it like a physical stack of plates—you can only add a new plate to the top, and you can only remove the plate that is currently on top.

Key Characteristics

LIFO Structure: Element access is restricted to the newest data point.
Single Access Point: All insertions and deletions occur exclusively at one end, called the Top.
Linear Order: Elements are organized sequentially in a straight line.
Constant Time Complexity: Core operations execute in \(O(1)\) time.
Dynamic or Static Sizes: Can be built using fixed arrays or dynamic linked lists.
Limited Direct Access: Cannot read or modify elements in the middle without popping the top elements first.

Boundary Conditions

Stack Overflow: Occurs when trying to push an item onto an already full stack.
Stack Underflow: Occurs when trying to pop an item from an empty stack.

Advantages and Disadvantages#

Advantages

\(O(1)\) Time Complexity: Push, pop, and peek operations run in constant time.
No Shifting Required: Adding or removing data never requires shifting elements around.
Memory Efficiency: Requires minimal memory overhead because it only tracks a single top pointer.
Inherent LIFO Management: Perfectly models real-world undo/redo histories and browser back buttons.
Automated Cleanup: Automatically allocates and deallocates memory during function call execution.
Algorithm Simplicity: Simplifies implementations of backtracking, text parsing, and string reversals.

Disadvantages

No Random Access: You cannot read or modify elements in the middle without popping the top.
Risk of Overflow: Fixed-size array implementations crash with a stack overflow error if filled past capacity.
Risk of Underflow: Attempting to pop elements from an entirely empty stack triggers an underflow error.
Inflexible Resizing: Static array variations cannot scale up dynamically if your data needs expand.
Memory Wastage Potential: Oversizing a static stack pre-allocates contiguous memory that may sit entirely unused.
Poor Search/Sort Capability: Searching for a specific value forces you to systematically destroy the structure.

Core Operations#

Every operation on a stack happens at a single point called the Top of Stack and runs in \(O(1)\) time complexity.

Push: Adds an item tothe top of the stack.
Pop: Removes and returns the top item. Calling this on an empty stack causes a stack underflow error.
Peek or Top: Returns the value of the top item without removing it.
isEmpty: Checks if the stack is completely empty.
isFull: Checks if a fixed-size stack has reached its maximum capacity (causes a stack overflow if exceeded).

Visualization#

https://media.geeksforgeeks.org/wp-content/uploads/20230116192305/stack-768.png — *Source*: GeeksforGeeks#

Implementation#

#include <stdexcept>
#include <vector>

int getSize(std::vector<int> &array) {
  return array.size();
}

bool isEmpty(std::vector<int> &array) {
  return getSize(array) == 0;
}

int peek(std::vector<int> &array) {
  if (isEmpty(array)) {
    throw std::out_of_range("Empty Stack");
  }
  return array[getSize(array) - 1];
}

int pop(std::vector<int> &array) {
  if (isEmpty(array)) {
    throw std::out_of_range("Empty Stack");
  }
  int value = array[getSize(array) - 1];
  array.pop_back();
  return value;
}

void push(std::vector<int> &array, int value) {
  array.emplace_back(value);
}

class Stack[T]:
  def __init__(self) -> None:
    self.__stack: list[T] = list()

  def is_empty(self) -> bool:
    return self.size == 0

  def peek(self) -> T:
    if self.is_empty():
      raise IndexError("Empty Stack")
    return self.__stack[-1]

  def pop(self) -> T:
    if self.is_empty():
      raise IndexError("Empty Stack")
    return self.__stack.pop()

  def push(self, item: T) -> None:
    self.__stack.append(item)

  def size(self) -> int:
    return len(self.__stack)