Stacks

Introduction

Stack: Last-In-First-Out (LIFO) abstract data type. Insert/remove: same end (top). Operations: push (add), pop (remove), peek (view top). Fundamental: recursion, parsing, memory management. Analogy: stack of dishes.

"Stacks are the backbone of computation: function calls, parsing, backtracking. Their simple LIFO discipline enables elegant solutions to inherently recursive problems." -- Fundamental data structures

Stack Definition

LIFO Principle

Last element in: first element out. Push 1, 2, 3: stack is [1, 2, 3]. Pop: returns 3 (last added). Push 4: stack is [1, 2, 4].

Abstract Data Type

Operations: push(x), pop(), peek(), isEmpty(), size(). Implementation: array or linked list (both O(1)).

Example

Push A: [A]Push B: [A, B]Push C: [A, B, C]Pop: [A, B] (returned C)Peek: returns BPush D: [A, B, D]

Basic Operations

Push (Insert)

Add element to topTime: O(1)Space: O(1)

Pop (Remove)

Remove top element, return itTime: O(1)Error: if empty (underflow)

Peek (Access)

View top without removingTime: O(1)Error: if empty

isEmpty (Check)

Test if stack emptyTime: O(1)

Size (Count)

Number of elementsTime: O(1) or O(n) depending on implementation

Implementation

Array-Based

class ArrayStack: data = array[0..max-1] top = -1 push(x): if top == max-1: error (overflow) top++ data[top] = x pop(): if top == -1: error (underflow) result = data[top] top-- return result

Linked List-Based

class LinkedStack: head = null push(x): new_node = Node(x) new_node.next = head head = new_node pop(): if head == null: error (underflow) result = head.data head = head.next return result

Comparison

Time Complexity

All Operations

Push: O(1). Pop: O(1). Peek: O(1). isEmpty: O(1). Space: O(n) total for n elements.

Guarantee

Worst-case: all operations O(1). No degradation: perfect data structure for LIFO needs. Predictable performance.

Applications

Function Call Stack

Each call: pushed to stack. Return: pops. Recursion: natural fit. Stack overflow: too many calls.

Memory Management

Local variables: stored on stack. Automatic cleanup: function return. Fast allocation/deallocation.

Undo/Redo

Actions: push to stack. Undo: pop. Redo: second stack. Perfect for command history.

Parsing and Compilation

Bracket matching: push/pop. Expression evaluation: operators, operands. Syntax validation: nesting.

Function Calls and Recursion

Call Stack

main() calls f1() Stack: [main] f1() calls f2() Stack: [main, f1] f2() returns Stack: [main] f1() calls f3() Stack: [main, f1, f3] f3() returns Stack: [main] f1() returnsStack: []

Recursion

Each call: adds frame to stack. Base case: terminates. Backtracking: natural (previous state on stack).

Stack Overflow

Infinite recursion: stack fills. Stack limited: typically MB-GB. Deep recursion: hits limit.

Tail Recursion

Optimization: reuse frame (last call). Not all languages support. Manual: convert to iteration.

Parsing and Validation

Bracket Matching

Check if brackets balanced: "({[]})"Push ( { [ on stackPop for ) } ] (must match type)Empty at end: validExample: ( { [ ] } ) all pop in reverse order

Algorithm

for each char in string: if open bracket: push if close bracket: if stack empty: error (unmatched) if top != matching open: error (mismatched) popif stack not empty: error (unclosed)

Valid Examples

( ) [ { } ], ( [ ( ) ] ), { [ ( ) ] }. Invalid: ) (, [ { } ), ( [ )

Expression Evaluation

Postfix (RPN)

3 4 + means 3 + 4 = 7Algorithm: push numbers, apply operatorsfor each token: if number: push if operator: pop two operands apply operator push resultFinal: stack has result

Infix to Postfix

Convert "3 + 4 * 2" to "3 4 2 * +"Use stack for operators (respects precedence)Higher precedence: deeper in stack

Advantage

No parentheses needed (implicit in RPN). Evaluation: O(n) single pass. Natural for stack machine.

Practical Examples

Depth-First Search (DFS)

Graph traversal: use stack. Iterative: avoids recursion. Post-order: useful for topological sort.

Browser Back Button

History: stack of pages. Back: pop stack. Forward: second stack.

Text Editor

Undo: stack of actions. Redo: separate stack. Perfect implementation.

Memory Allocation

Local variables: stack. Automatic cleanup. Fast allocation (pointer increment).

Stack Variants

Minstack

Track minimum: alongside data. Push: update min. Pop: restore previous min. Extra space: O(n).

Monotonic Stack

Keep elements in order: for finding next greater/smaller. Complex: but efficient for specific queries.

Stack of Stacks

Nested stacks: handle overflow gracefully. Pop entire sub-stack. Rare: specialized use.

Performance Characteristics

Best Case

All operations: O(1). Space: O(n) for n elements. Predictable: no surprises.

Worst Case

Same as average: O(1) per operation. No degradation: guaranteed performance.

Space Efficiency

Minimal overhead: array or linked list. No search structure needed. Tight memory usage.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to Algorithms." MIT Press, 3rd edition, 2009.
• Knuth, D. E. "The Art of Computer Programming: Fundamental Algorithms." Vol. 1, Addison-Wesley, 3rd edition, 1997.
• Sedgewick, R., and Wayne, K. "Algorithms." Addison-Wesley, 4th edition, 2011.
• Weiss, M. A. "Data Structures and Problem Solving Using Java." Addison-Wesley, 4th edition, 2010.
• Goodrich, M. T., Tamassia, R., and Goldwasser, M. H. "Data Structures and Algorithms in Java." Wiley, 6th edition, 2014.