Stack (Data Structure)

data-structures

Definition

Stack

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. In a stack, all insertions and deletions are restricted to a single end, called the top.

It provides three primary operations:

1. $\mathrm{push}(v)$: Adds element $v$ to the top of the stack.
2. $\mathrm{pop}()$: Removes and returns the element at the top.
3. $\mathrm{peek}()$: Returns the element at the top without removing it.

Visual Representation

A stack is often compared to a stack of physical objects, where only the top item is accessible:

Implementation

Array-based

Using a dynamic array or a fixed-size array with a top index:

• $\mathrm{push}$:$O(1)$ (amortised if resizing is needed).
• $\mathrm{pop}$:$O(1)$.

Linked List

Using a singly linked list:

• New elements are pushed to the head.
• Popping occurs from the head.
• Both operations are strictly $O(1)$.

Complexity

Operation	Time Complexity
$\mathrm{push}$	$O(1)$
$\mathrm{pop}$	$O(1)$
$\mathrm{peek}$	$O(1)$
$\mathrm{search}$	$O(n)$

Use Cases

• Function Call Stack: Managing activation records in programming languages.
• Expression Evaluation: Parsing and evaluating postfix notation (Reverse Polish Notation).
• Undo/Redo: Maintaining state history in applications.
• Recursion: Emulated using an explicit stack.