Linear Data Structures

Stack — Last In, First Out

A stack is the simplest useful data structure. It follows one rule: the last element added is always the first one removed. Think of a stack of plates — you always add to the top and always take from the top. You never reach into the middle. This single constraint — LIFO — makes the stack the backbone of function calls, expression evaluation, undo operations, and backtracking algorithms.

The Concept

What is a Stack?

A stack is a collection of elements with a strict access rule: you can only interact with the top element. Adding an element places it on top. Removing an element takes it from the top. The element at the bottom is the oldest — and completely inaccessible until everything above it has been removed.

After pushing 12, 35, 61

⬆️PUSH 61 — added on top

⬇️POP — removes 61 (top)

👁️PEEK — reads 61, no removal

❓isEmpty — checks if size = 0

Why LIFO matters: When a function calls another function, the calling function must be "remembered" so control can return to it when the called function finishes. The call stack does exactly this — each function call is pushed, and when it returns, it is popped. The most recent call is always resolved first.

Operations

Push · Pop · Peek · isEmpty

A stack has only four operations. All of them are O(1) — constant time regardless of how many elements the stack holds. This is what makes the stack both simple and powerful.

⬆️

PUSH(value)

Adds a new element on top of the stack. The stack grows upward. If the stack is implemented with an array, increment the top pointer; with a linked list, insert at the head. O(1)

⬇️

POP()

Removes and returns the top element. If the stack is empty, this is an underflow error. Decrement the top pointer (array) or update the head pointer (linked list). O(1)

👁️

PEEK() / TOP()

Returns the top element without removing it. Read-only access to the top. Used to inspect the next item to be processed without consuming it. O(1)

❓

isEmpty()

Returns true if the stack has no elements. Used as a loop condition in most stack-based algorithms — "keep processing while the stack is not empty." O(1)

// Stack using array (pseudocode) top = -1 arr[MAX_SIZE] function push(value): if top == MAX_SIZE - 1: error("Stack Overflow") top = top + 1 arr[top] = value function pop(): if top == -1: error("Stack Underflow") value = arr[top] top = top - 1 return value function peek(): if top == -1: error("Stack is empty") return arr[top]

Stack Overflow vs Stack Underflow: Overflow happens when you push onto a full stack (array implementation with fixed size). Underflow happens when you pop from an empty stack. Both are runtime errors. The name "Stack Overflow" — the famous Q&A website — is a nod to this exact error that every programmer eventually encounters.

Two Implementations

Array-Based vs Linked-List-Based Stack

A stack is an abstract data type — the LIFO rule defines its behaviour, not its internal storage. It can be implemented using either an array or a linked list. Both give O(1) for all four operations, but they differ in memory behaviour.

🗃️

Array-Based Stack

A single array with a top index pointer. Push increments top; pop decrements it.

Pros: Cache-friendly, simple, fast in practice.
Cons: Fixed maximum size. Overflow if the stack grows beyond the declared array size. Memory is allocated upfront even if unused.

🔗

Linked-List-Based Stack

Each push creates a new node at the head; each pop removes the head node.

Pros: Dynamic size — grows as needed, no overflow unless memory is exhausted.
Cons: Extra memory per element (the NEXT pointer). Pointer chasing is slightly slower than array indexing.

Performance

Time and Space Complexity

Operation	Array Stack	Linked-List Stack	Notes
Push	O(1)	O(1)	Increment top / insert at head
Pop	O(1)	O(1)	Decrement top / remove head
Peek	O(1)	O(1)	Read arr[top] / read head.data
isEmpty	O(1)	O(1)	Check top == -1 / head == NULL
Search	O(n)	O(n)	Must pop until found — defeats the purpose
Space	O(n)	O(n)	Linked list uses extra n pointer words

All four primary operations are O(1) — this is why stacks are used so heavily in system design. No matter how many elements the stack holds, every push, pop, and peek takes the same constant time.

Applications

Where Stacks Are Used

📞

Function Call Stack

Every time a program calls a function, the CPU pushes a stack frame onto the call stack. The frame stores the function's local variables, parameters, and the return address — where execution should resume after the function completes. When the function returns, its frame is popped and control returns to the caller. Recursive functions push a new frame for every recursive call. If recursion goes too deep without a base case, the stack overflows — the dreaded "stack overflow" crash.

main() calls factorial(5) → push frame for factorial(5) factorial(5) calls factorial(4) → push frame for factorial(4) factorial(4) calls factorial(3) → push frame for factorial(3) ...base case reached: factorial(1) returns 1 pop factorial(1) → return to factorial(2) pop factorial(2) → return to factorial(3) ... and so on

🧮

Expression Evaluation

Compilers and calculators use two stacks to evaluate arithmetic expressions: an operand stack for numbers and an operator stack for operators. The algorithm reads the expression left to right. Numbers are pushed to the operand stack. Operators are pushed to the operator stack, but before pushing, any operator with equal or higher precedence already on the stack is popped and applied first — this correctly handles operator precedence without parentheses.

Expression: ( 3 + 5 ) * 2 Token ( → push to operator stack: Op: [( ] Opnd: [] Token 3 → push to operand stack: Op: [( ] Opnd: [3] Token + → push to operator stack: Op: [( +] Opnd: [3] Token 5 → push to operand stack: Op: [( +] Opnd: [3 5] Token ) → pop and evaluate: 3 + 5 = 8 Opnd: [8] Token * → push to operator stack: Op: [* ] Opnd: [8] Token 2 → push to operand stack: Op: [* ] Opnd: [8 2] End → pop and evaluate: 8 * 2 = 16 Result: 16

↩️

Undo / Redo in Text Editors

Every edit action — typing a character, deleting a word, formatting a paragraph — is pushed onto an undo stack as it is performed. When the user presses Ctrl+Z, the top action is popped and reversed. To support Redo, the reversed action is pushed onto a separate redo stack. Pressing Ctrl+Y pops from the redo stack and re-applies it. This dual-stack architecture handles arbitrarily long undo histories in O(1) per operation.

🔙

Backtracking Algorithms

Algorithms that explore possibilities and need to retreat when a path fails — such as solving a maze, the N-Queens problem, or Sudoku — use a stack to remember the choices made so far. At each decision point, the current state is pushed. If a dead end is reached, the state is popped and the algorithm tries a different branch. This is why iterative DFS (Depth-First Search) on a graph uses an explicit stack, while recursive DFS uses the implicit call stack.

🔡

Bracket Matching and Syntax Checking

Compilers check whether brackets, parentheses, and braces are correctly matched by scanning the source code left to right. When an opening bracket is encountered, it is pushed. When a closing bracket is encountered, the top is popped and checked — if the popped bracket matches the closing one, the pair is valid. If the stack is empty at a closing bracket, or non-empty at the end of the file, the code has a syntax error.

Input: { [ ( ) ] } { → push Stack: [{] [ → push Stack: [{ [] ( → push Stack: [{ [ (] ) → pop ( Stack: [{ [] match ✓ ] → pop [ Stack: [{] match ✓ } → pop { Stack: [] match ✓ → Valid!

Interactive Learning

Games and Demos

The Expression Evaluator demo shows the two-stack algorithm step by step — press Start on any preset expression then Step through it token by token, watching the Operand and Operator stacks change in real time. The Linear DS Quest lets you push and pop on a live stack.