Stack

Abstract

A Stack is an Abstract Data Type that enforces the Last In, First Out ($\text{LIFO}$) operational protocol. Elements are added and extracted strictly from a single boundary margin called the top.

• Category: Boundary Restricted ADT
• Core Rule: The most recently added element is always the first one removed.
• Common Backing Implementations: Array Lists, Singly-Linked Lists, or Deques.

---

Core Functional Interface

A compliant Stack interface exposes three primary operations:

Operation	Detailed Functional Execution
push(element)	Places a new element onto the top boundary of the Stack.
pop()	Extracts and removes the top-most element from the Stack.
peek() / top()	Evaluates and returns the top-most element without removing it.

---

Implementation Frameworks

A Stack interface can be efficiently implemented using several concrete backing data structures:

1. Array List Backbone

• push(element): Appends to the trailing array index in amortized $O(1)$ time.
• pop(): Decrements size and removes the trailing element in $O(1)$ time without requiring data shifting.
• peek(): Accesses the trailing index directly in $O(1)$ constant time.

2. Singly-Linked List Backbone

• push(element): Prepends a new node at the head in $O(1)$ time.
• pop(): Advances the head pointer to head.next in $O(1)$ time.
• peek(): Inspects head.data in $O(1)$ constant time.

---

Operational Complexity Analysis

$\begin{array}{ccc}\mathbf{Operation}& \mathbf{Array}\mathbf{List}\mathbf{Backbone}& \mathbf{Singly}\text{-}\mathbf{Linked}\mathbf{List}\mathbf{Backbone}\\ \text{push(element)}& \text{Amortized }O(1)& O(1)\\ \text{pop()}& O(1)& O(1)\\ \text{peek() / top()}& O(1)& O(1)\end{array}$

Algorithm 19 Stack Interface Operations (Linked List Implementation)

procedure Push($element, top$)

$newNode \gets \text{Allocate new node with } data = element$

$newNode.next \gets top$

$top \gets newNode$

procedure Pop($top$)

if $top == \text{NULL}$ then

return $\text{Underflow Error}$

$poppedData \gets top.data$

$top \gets top.next$

return $poppedData$

---

Core Architectural Applications

• Function Call Stack & Recursion: Manages activation records, local variables, and return addresses during nested function calls in programming language runtimes.
• Expression Parsing & Evaluation: Evaluates mathematical expressions and converts infix notation to postfix using algorithms like Dijkstra’s Shunting-Yard.
• Backtracking Algorithms: Powers Depth-First Search (DFS) graph exploration routines and maze-solving algorithms.
• Undo/Redo History: Stores historical state snapshots in text editors and browser navigation buffers.

---

Related Notes

• Queues
• Deques
• Array Lists
• Linked List