Data Structures & AlgorithmsStack Operations & Interface

Stack Operations & Interface

LevelBeginner

Duration55 mins

TopicStack Operations & Interface

2 / 5

Pop — Removing Elements from the Top

The Stack's Principal Retrieval Mechanism

If push is how data enters a stack, pop is how it leaves. The pop operation removes and returns the topmost element—the most recently pushed item still on the stack. This simple action, repeated in various patterns, powers everything from undo systems to expression evaluation to function call management.

Pop is where the LIFO (Last-In, First-Out) principle manifests most clearly. When you pop, you're not choosing which element to remove; the stack has already decided. The most recent push determines the next pop's result. This constraint transforms what could be chaos into predictable, reversible operations.

What You Will Learn

By the end of this page, you will master the pop operation completely—understanding its semantics, its dual relationship with push, implementations in both array and linked list forms, its complexity characteristics, critical edge cases (especially the empty stack), and the patterns where pop is central to algorithmic solutions.

What Pop Means Conceptually

The pop operation performs two actions atomically:

Retrieves the element at the top of the stack
Removes that element from the stack

After a pop, the stack shrinks by one element, and the element that was second from the top becomes the new top.

The inverse relationship with push:

Pop and push are inverse operations. If you push element X and then immediately pop, you get X back, and the stack returns to its state before the push. This reversibility is fundamental to stack semantics and enables use cases like undo operations and backtracking algorithms.

Push-Pop Inverse Relationship
1
2
3
4
5
6
7
8
9
10
11
Initial state:    [10, 20]     ← 20 is on top
                        ↑ top
 
push(30):         [10, 20, 30]  ← 30 is now on top
                           ↑ top
 
pop():            [10, 20]     ← Returns 30; stack restored to previous state
                        ↑ top
 
Observation: pop() undoes the effect of the previous push()
             The stack returns to exactly the state it had before the push

Tracing a sequence of operations:

Let's trace through multiple push and pop operations to see how the stack evolves:

Push-Pop Operation Trace
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Operation         Stack State           Returns    Notes
─────────────────────────────────────────────────────────────
initial           []                     -          empty stack
push(A)           [A]                    -          A is top
push(B)           [A, B]                 -          B is top
push(C)           [A, B, C]              -          C is top
pop()             [A, B]                 C          C removed, B is now top
pop()             [A]                    B          B removed, A is now top
push(D)           [A, D]                 -          D is top
push(E)           [A, D, E]              -          E is top
pop()             [A, D]                 E          E removed, D is now top
pop()             [A]                    D          D removed, A is now top
pop()             []                     A          A removed, stack empty
pop()             []                     ERROR      Cannot pop empty stack!
 
Key insight: Elements exit in reverse order of entry.
A was first in, last out. C was last in, first out. LIFO in action.

Pop Consumes Data

Unlike peek (which we'll cover later), pop is destructive—it removes the element from the stack. Once popped, an element is gone from the stack forever unless you push it back. This makes pop a 'commitment' operation: you're done with that element.

The Pop Contract — Preconditions and Postconditions

Like all well-designed operations, pop has a clear contract that specifies what must be true before calling it, what will be true after, and what guarantees it provides.

Pop Operation Contract

•Precondition: The stack is not empty. Attempting to pop from an empty stack is an error condition (stack underflow).
•Postcondition #1: The method returns the element that was at the top of the stack.
•Postcondition #2: That element is no longer in the stack.
•Postcondition #3: The stack's size has decreased by exactly 1. If size() was n before pop, it's n - 1 after.
•Postcondition #4: The element that was second from the top (if any) is now at the top.
•Invariant preserved: The stack maintains LIFO order—remaining elements retain their relative positions.

Pop Contract Summary
Aspect	Description
Input	None (pop takes no parameters)
Output	The element that was at the top of the stack
Side Effect	Removes the top element; decrements size
Time Guarantee	O(1) in all standard implementations
Space Guarantee	O(1) — no additional space needed
Failure Mode	Stack underflow if called on empty stack

Stack Underflow vs Overflow

Stack overflow (too many pushes) and stack underflow (popping empty stack) are symmetric error conditions. Overflow relates to capacity limits; underflow relates to emptiness. Both must be handled, but underflow is more common in practice—it's easy to pop more times than you pushed.

Pop Implementation — Array-Based Stack

In an array-based stack, pop retrieves the element at the current top index and decrements the index. The element isn't physically removed from the array (it may still occupy the memory slot), but it's logically removed—the stack's invariants no longer consider it part of the stack.

The key insight: We read the element at topIndex, then decrement topIndex. The order matters—we need the element before we logically remove it.

ArrayStack.ts - Pop Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class ArrayStack<T> {
    private items: T[];
    private topIndex: number;
    private capacity: number;
 
    constructor(capacity: number = 1000) {
        this.items = new Array<T>(capacity);
        this.topIndex = -1;  // -1 indicates empty stack
        this.capacity = capacity;
    }
 
    /**
     * Pop: Remove and return the top element
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     * 
     * @throws Error if stack is empty (stack underflow)
     * @returns The element that was at the top
     */
    pop(): T {
        // Precondition check: ensure stack is not empty
        if (this.topIndex < 0) {
            throw new Error("Stack Underflow: Cannot pop from an empty stack");
        }
 
        // Retrieve the top element
        const poppedElement = this.items[this.topIndex];
 
        // Optional: Clear the reference to help garbage collection
        // (especially important for object types)
        this.items[this.topIndex] = undefined as any;
 
        // Decrement top index — element is now logically removed
        this.topIndex--;
 
        // Return the popped element
        return poppedElement;
    }
 
    /**
     * Check if stack is empty
     */
    isEmpty(): boolean {
        return this.topIndex < 0;
    }
 
    /**
     * Push for completeness
     */
    push(element: T): void {
        if (this.topIndex >= this.capacity - 1) {
            throw new Error("Stack Overflow");
        }
        this.topIndex++;
        this.items[this.topIndex] = element;
    }
}

Step-by-step execution of pop():

Array Pop Step-by-Step
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Before pop():
    items:    [10, 20, 30, _, _, ...]    (capacity 1000)
    topIndex: 2                           ← 30 is the top element
 
Step 1: Check precondition
    topIndex (2) >= 0? Yes, proceed.
 
Step 2: Retrieve top element
    poppedElement = items[2] = 30
 
Step 3: Clear reference (optional but recommended)
    items[2] = undefined
 
Step 4: Decrement topIndex
    topIndex = 1
 
Step 5: Return poppedElement (30)
 
After pop():
    items:    [10, 20, undefined, _, _, ...]
    topIndex: 1                           ← 20 is now the top
    returned: 30

Why Clear the Reference?

Setting the popped slot to undefined (or null) prevents memory leaks in garbage-collected languages. Without clearing, the array holds a reference to the popped object, preventing it from being garbage collected even though it's 'logically' gone from the stack. This is called 'loitering.'

Pop Implementation — Linked List-Based Stack

In a linked list-based stack, pop removes the head node and promotes the second node to become the new head. This is a pointer manipulation operation that naturally frees the old head for garbage collection.

The key insight: The head node is the top. Pop reads the head's value, then advances the head pointer to head.next. The old head node becomes unreferenced and will be collected.

LinkedListStack.ts - Pop Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class StackNode<T> {
    value: T;
    next: StackNode<T> | null;
 
    constructor(value: T) {
        this.value = value;
        this.next = null;
    }
}
 
class LinkedListStack<T> {
    private head: StackNode<T> | null;
    private count: number;
 
    constructor() {
        this.head = null;
        this.count = 0;
    }
 
    /**
     * Pop: Remove and return the top element
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     * 
     * @throws Error if stack is empty (stack underflow)
     * @returns The element that was at the top
     */
    pop(): T {
        // Precondition check: ensure stack is not empty
        if (this.head === null) {
            throw new Error("Stack Underflow: Cannot pop from an empty stack");
        }
 
        // Retrieve the value from the head node
        const poppedValue = this.head.value;
 
        // Update head to point to the next node
        // This disconnects the old head, making it eligible for GC
        this.head = this.head.next;
 
        // Decrement the count
        this.count--;
 
        // Return the popped value
        return poppedValue;
    }
 
    /**
     * Check if stack is empty
     */
    isEmpty(): boolean {
        return this.head === null;
    }
 
    /**
     * Push for completeness
     */
    push(element: T): void {
        const newNode = new StackNode(element);
        newNode.next = this.head;
        this.head = newNode;
        this.count++;
    }
}

Visualizing linked list pop:

Linked List Pop Visualization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Before pop():
    head → [30 | next] → [20 | next] → [10 | null]
           ↑ top
 
Step 1: Check precondition
    head !== null? Yes, proceed.
 
Step 2: Retrieve value from head
    poppedValue = head.value = 30
 
Step 3: Update head pointer
    head = head.next
    
    [30 | next] → [20 | next] → [10 | null]
    (orphaned)    ↑ new head
    
Step 4: Decrement count (3 → 2)
 
Step 5: Return poppedValue (30)
 
After pop():
    head → [20 | next] → [10 | null]
           ↑ top (new)
    
    The node containing 30 is now unreferenced and will be garbage collected.
    Stack contains: 20 (top), 10 (bottom)

Automatic Memory Management

In linked list implementations, pop naturally allows garbage collection of the removed node—no explicit cleanup needed. The moment head advances, the old node has no references pointing to it (assuming you didn't keep any external references) and becomes eligible for collection.

Pop Complexity Analysis

Pop is one of the most efficient operations in computer science—constant time in all standard implementations. This efficiency is what makes stacks so valuable for performance-critical applications.

Pop Time Complexity Across Implementations
Implementation	Best Case	Worst Case	Average	Notes
Fixed Array	O(1)	O(1)	O(1)	Index decrement, array access
Dynamic Array	O(1)	O(1)	O(1)	No shrinking on individual pop
Linked List	O(1)	O(1)	O(1)	Pointer update only

Why is pop always O(1)?

Pop operates only on the top element. It never needs to examine, shift, or reorganize other elements in the stack. Whether your stack has 10 elements or 10 million, pop performs the same constant number of operations:

Read one element (from top index or head node)
Update one pointer/index
Optionally update a size counter

No loops. No traversals. No searching. Just direct access and a pointer/index update.

Dynamic Array Shrinking

Some dynamic array implementations shrink the array when it becomes too empty (e.g., below 25% capacity). This can make individual pop operations O(n) during shrinking. However, like resizing on push, this amortizes to O(1) over many operations. Many practical implementations don't shrink on pop to avoid this complexity.

Pop Space Complexity Analysis
Implementation	Space Overhead	Notes
Fixed Array	O(1)	No new allocations; index update only
Dynamic Array	O(1) amortized	May free memory during shrinking
Linked List	O(1)	Node becomes eligible for GC; no explicit work

The Empty Stack Problem — Critical Edge Case

The most critical edge case for pop is the empty stack. Attempting to pop from an empty stack is an error—there's nothing to return, and the operation cannot complete successfully. This is called stack underflow.

Why is this edge case so important?

Unlike push (where overflow is rare with dynamic arrays and abundant memory), underflow is extremely common in real code. It's easy to write a loop that pops 'one too many times' or to forget that a sequence of operations might empty the stack.

Strategies for Handling Empty Stack Pop

•Throw an exception (recommended): Make the caller explicitly aware of the error. The bug surfaces immediately rather than causing silent data corruption. Most standard libraries use this approach.
•Return a sentinel value (null/undefined/None): Simple but dangerous. The caller might forget to check, and null propagates through the system causing mysterious failures elsewhere.
•Return an Optional/Maybe type: Forced checking at the type level. Languages with algebraic data types (Rust, Haskell, modern TypeScript) can use this pattern effectively.
•Return a default value: Caller provides a fallback. stack.popOr(defaultValue) returns the top if present, or the default if empty. Clear intent but may mask bugs.
•Caller always checks isEmpty first: Shifts responsibility to the caller. Works but requires discipline and doubles the number of calls.

EmptyStackHandlingStrategies.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Strategy 1: Throw exception (most common, recommended)
pop(): T {
    if (this.isEmpty()) {
        throw new Error("Stack Underflow: Cannot pop from empty stack");
    }
    return this.internalPop();
}
 
// Strategy 2: Return nullable (requires careful caller handling)
popOrNull(): T | null {
    if (this.isEmpty()) {
        return null;  // Caller MUST check for null
    }
    return this.internalPop();
}
 
// Strategy 3: Return Optional type (type-safe handling)
popOptional(): { hasValue: true; value: T } | { hasValue: false } {
    if (this.isEmpty()) {
        return { hasValue: false };
    }
    return { hasValue: true, value: this.internalPop() };
}
 
// Strategy 4: Return with fallback
popOr(defaultValue: T): T {
    if (this.isEmpty()) {
        return defaultValue;  // Caller provides fallback
    }
    return this.internalPop();
}
 
// Strategy 5: Caller always checks (defensive coding)
// Usage:
if (!stack.isEmpty()) {
    const value = stack.pop();  // Safe because we checked
    process(value);
}

Silent Failures Are Dangerous

Returning null or a default value on empty stack pop can mask bugs. Your stack appears to work, but it's actually returning incorrect data. The bug might only manifest much later, in a completely different part of the codebase, making it extremely hard to diagnose. Prefer explicit failures via exceptions.

Pop in Algorithmic Patterns

Pop is the action that 'consumes' stack data. Understanding common pop patterns helps you implement stack-based algorithms correctly and recognize when you've made an error (like popping at the wrong time).

Common Pop Patterns

•Matching pop: Pop when you encounter a 'closer' that matches a previously pushed 'opener.' Example: popping opening parenthesis when you see a closing parenthesis.
•Exhaustive pop: Pop everything (while not empty) to process all accumulated items. Example: processing all remaining stack items at the end of an algorithm.
•Conditional pop: Pop only when the top meets certain criteria. Example: in monotonic stacks, pop while the top is greater/less than the current element.
•Process-then-pop: Peek to check the top, process it, then pop. Example: when processing depends on knowing what's at top before committing to removal.
•Restoration pop: Pop to restore a saved state for backtracking. Example: undo operations, recursive state restoration, bracket validation.

PopPatternExamples.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Pattern 1: Matching pop (parentheses validation)
function isValidParentheses(s: string): boolean {
    const stack: string[] = [];
    const pairs: Record<string, string> = {')': '(', ']': '[', '}': '{'};
    
    for (const char of s) {
        if ('([{'.includes(char)) {
            stack.push(char);  // Push openers
        } else if (')]}');.includes(char)) {
            // Matching pop: must match the most recently pushed opener
            if (stack.length === 0 || stack.pop() !== pairs[char]) {
                return false;
            }
        }
    }
    return stack.length === 0;  // All openers must be matched
}
 
// Pattern 2: Exhaustive pop (drain the stack)
function processAllRemaining(stack: Stack<Task>): void {
    while (!stack.isEmpty()) {
        const task = stack.pop();  // Pop everything
        task.finalize();
    }
}
 
// Pattern 3: Conditional pop (monotonic stack)
function nextGreaterElement(nums: number[]): number[] {
    const result = new Array(nums.length).fill(-1);
    const stack: number[] = [];  // stores indices
    
    for (let i = 0; i < nums.length; i++) {
        // Pop while current element is greater than stack top
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            const idx = stack.pop()!;
            result[idx] = nums[i];  // Current is the next greater
        }
        stack.push(i);
    }
    return result;
}

The Pop-Push Balance

In most stack algorithms, there's a logical balance between pushes and pops. For bracket matching, every opener pushed should eventually be popped when its closer is found. Unbalanced pushes/pops usually indicate an error—either in the algorithm or in the input data.

Summary: Mastering Pop

We've examined pop from every angle—its semantics, its relationship with push, its implementations, and its role in algorithms. Here are the essential takeaways:

Key Takeaways

•Pop retrieves and removes: Unlike peek, pop is destructive. The returned element is no longer in the stack. This is a commitment—you're done with that element.
•Pop inverts push: Pushing X then immediately popping returns X and restores the previous state. This inverse relationship enables undo, backtracking, and state management.
•O(1) always: Pop is constant-time in all implementations. It operates only on the top element, requiring no traversal or reorganization.
•Empty stack is critical: Popping an empty stack is an error (underflow). Always check isEmpty before pop, or design your algorithm to guarantee the stack won't be empty when you pop.
•Various error-handling strategies: Exceptions, null returns, Optional types, and defaults all have trade-offs. Prefer explicit exceptions to surface bugs early.
•Pop patterns are recognizable: Matching pop, exhaustive pop, conditional pop—these patterns recur across stack-based algorithms.

What's Next:

We've covered the two 'active' stack operations: push (adding) and pop (removing). Next, we'll explore peek—the 'passive' operation that lets you see the top element without modifying the stack. Understanding peek completes your knowledge of stack interaction patterns.

Page Complete

You now have comprehensive knowledge of the pop operation—its semantics, implementations, complexity, edge cases, and algorithmic patterns. Together with push, pop gives you the core tools for stack manipulation. Next: peek, the read-only view of the stack's top.

2 / 5

Loading learning content...

Data Structures & AlgorithmsStack Operations & Interface

Stack Operations & Interface

LevelBeginner

Duration55 mins

TopicStack Operations & Interface

2 / 5

Pop — Removing Elements from the Top

The Stack's Principal Retrieval Mechanism

What You Will Learn

What Pop Means Conceptually

The pop operation performs two actions atomically:

Retrieves the element at the top of the stack
Removes that element from the stack

After a pop, the stack shrinks by one element, and the element that was second from the top becomes the new top.

The inverse relationship with push:

Push-Pop Inverse Relationship
1
2
3
4
5
6
7
8
9
10
11
Initial state:    [10, 20]     ← 20 is on top
                        ↑ top
 
push(30):         [10, 20, 30]  ← 30 is now on top
                           ↑ top
 
pop():            [10, 20]     ← Returns 30; stack restored to previous state
                        ↑ top
 
Observation: pop() undoes the effect of the previous push()
             The stack returns to exactly the state it had before the push

Tracing a sequence of operations:

Let's trace through multiple push and pop operations to see how the stack evolves:

Push-Pop Operation Trace
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Operation         Stack State           Returns    Notes
─────────────────────────────────────────────────────────────
initial           []                     -          empty stack
push(A)           [A]                    -          A is top
push(B)           [A, B]                 -          B is top
push(C)           [A, B, C]              -          C is top
pop()             [A, B]                 C          C removed, B is now top
pop()             [A]                    B          B removed, A is now top
push(D)           [A, D]                 -          D is top
push(E)           [A, D, E]              -          E is top
pop()             [A, D]                 E          E removed, D is now top
pop()             [A]                    D          D removed, A is now top
pop()             []                     A          A removed, stack empty
pop()             []                     ERROR      Cannot pop empty stack!
 
Key insight: Elements exit in reverse order of entry.
A was first in, last out. C was last in, first out. LIFO in action.

Pop Consumes Data

The Pop Contract — Preconditions and Postconditions

Like all well-designed operations, pop has a clear contract that specifies what must be true before calling it, what will be true after, and what guarantees it provides.

Pop Operation Contract

•Precondition: The stack is not empty. Attempting to pop from an empty stack is an error condition (stack underflow).
•Postcondition #1: The method returns the element that was at the top of the stack.
•Postcondition #2: That element is no longer in the stack.
•Postcondition #3: The stack's size has decreased by exactly 1. If size() was n before pop, it's n - 1 after.
•Postcondition #4: The element that was second from the top (if any) is now at the top.
•Invariant preserved: The stack maintains LIFO order—remaining elements retain their relative positions.

Pop Contract Summary
Aspect	Description
Input	None (pop takes no parameters)
Output	The element that was at the top of the stack
Side Effect	Removes the top element; decrements size
Time Guarantee	O(1) in all standard implementations
Space Guarantee	O(1) — no additional space needed
Failure Mode	Stack underflow if called on empty stack

Stack Underflow vs Overflow

Pop Implementation — Array-Based Stack

The key insight: We read the element at topIndex, then decrement topIndex. The order matters—we need the element before we logically remove it.

ArrayStack.ts - Pop Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class ArrayStack<T> {
    private items: T[];
    private topIndex: number;
    private capacity: number;
 
    constructor(capacity: number = 1000) {
        this.items = new Array<T>(capacity);
        this.topIndex = -1;  // -1 indicates empty stack
        this.capacity = capacity;
    }
 
    /**
     * Pop: Remove and return the top element
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     * 
     * @throws Error if stack is empty (stack underflow)
     * @returns The element that was at the top
     */
    pop(): T {
        // Precondition check: ensure stack is not empty
        if (this.topIndex < 0) {
            throw new Error("Stack Underflow: Cannot pop from an empty stack");
        }
 
        // Retrieve the top element
        const poppedElement = this.items[this.topIndex];
 
        // Optional: Clear the reference to help garbage collection
        // (especially important for object types)
        this.items[this.topIndex] = undefined as any;
 
        // Decrement top index — element is now logically removed
        this.topIndex--;
 
        // Return the popped element
        return poppedElement;
    }
 
    /**
     * Check if stack is empty
     */
    isEmpty(): boolean {
        return this.topIndex < 0;
    }
 
    /**
     * Push for completeness
     */
    push(element: T): void {
        if (this.topIndex >= this.capacity - 1) {
            throw new Error("Stack Overflow");
        }
        this.topIndex++;
        this.items[this.topIndex] = element;
    }
}

Step-by-step execution of pop():

Array Pop Step-by-Step
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Before pop():
    items:    [10, 20, 30, _, _, ...]    (capacity 1000)
    topIndex: 2                           ← 30 is the top element
 
Step 1: Check precondition
    topIndex (2) >= 0? Yes, proceed.
 
Step 2: Retrieve top element
    poppedElement = items[2] = 30
 
Step 3: Clear reference (optional but recommended)
    items[2] = undefined
 
Step 4: Decrement topIndex
    topIndex = 1
 
Step 5: Return poppedElement (30)
 
After pop():
    items:    [10, 20, undefined, _, _, ...]
    topIndex: 1                           ← 20 is now the top
    returned: 30

Why Clear the Reference?

Pop Implementation — Linked List-Based Stack

The key insight: The head node is the top. Pop reads the head's value, then advances the head pointer to head.next. The old head node becomes unreferenced and will be collected.

LinkedListStack.ts - Pop Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class StackNode<T> {
    value: T;
    next: StackNode<T> | null;
 
    constructor(value: T) {
        this.value = value;
        this.next = null;
    }
}
 
class LinkedListStack<T> {
    private head: StackNode<T> | null;
    private count: number;
 
    constructor() {
        this.head = null;
        this.count = 0;
    }
 
    /**
     * Pop: Remove and return the top element
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     * 
     * @throws Error if stack is empty (stack underflow)
     * @returns The element that was at the top
     */
    pop(): T {
        // Precondition check: ensure stack is not empty
        if (this.head === null) {
            throw new Error("Stack Underflow: Cannot pop from an empty stack");
        }
 
        // Retrieve the value from the head node
        const poppedValue = this.head.value;
 
        // Update head to point to the next node
        // This disconnects the old head, making it eligible for GC
        this.head = this.head.next;
 
        // Decrement the count
        this.count--;
 
        // Return the popped value
        return poppedValue;
    }
 
    /**
     * Check if stack is empty
     */
    isEmpty(): boolean {
        return this.head === null;
    }
 
    /**
     * Push for completeness
     */
    push(element: T): void {
        const newNode = new StackNode(element);
        newNode.next = this.head;
        this.head = newNode;
        this.count++;
    }
}

Visualizing linked list pop:

Linked List Pop Visualization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Before pop():
    head → [30 | next] → [20 | next] → [10 | null]
           ↑ top
 
Step 1: Check precondition
    head !== null? Yes, proceed.
 
Step 2: Retrieve value from head
    poppedValue = head.value = 30
 
Step 3: Update head pointer
    head = head.next
    
    [30 | next] → [20 | next] → [10 | null]
    (orphaned)    ↑ new head
    
Step 4: Decrement count (3 → 2)
 
Step 5: Return poppedValue (30)
 
After pop():
    head → [20 | next] → [10 | null]
           ↑ top (new)
    
    The node containing 30 is now unreferenced and will be garbage collected.
    Stack contains: 20 (top), 10 (bottom)

Automatic Memory Management

Pop Complexity Analysis

Pop Time Complexity Across Implementations
Implementation	Best Case	Worst Case	Average	Notes
Fixed Array	O(1)	O(1)	O(1)	Index decrement, array access
Dynamic Array	O(1)	O(1)	O(1)	No shrinking on individual pop
Linked List	O(1)	O(1)	O(1)	Pointer update only

Why is pop always O(1)?

Read one element (from top index or head node)
Update one pointer/index
Optionally update a size counter

No loops. No traversals. No searching. Just direct access and a pointer/index update.

Dynamic Array Shrinking

Pop Space Complexity Analysis
Implementation	Space Overhead	Notes
Fixed Array	O(1)	No new allocations; index update only
Dynamic Array	O(1) amortized	May free memory during shrinking
Linked List	O(1)	Node becomes eligible for GC; no explicit work

The Empty Stack Problem — Critical Edge Case

Why is this edge case so important?

Strategies for Handling Empty Stack Pop

•Throw an exception (recommended): Make the caller explicitly aware of the error. The bug surfaces immediately rather than causing silent data corruption. Most standard libraries use this approach.
•Return a sentinel value (null/undefined/None): Simple but dangerous. The caller might forget to check, and null propagates through the system causing mysterious failures elsewhere.
•Return an Optional/Maybe type: Forced checking at the type level. Languages with algebraic data types (Rust, Haskell, modern TypeScript) can use this pattern effectively.
•Return a default value: Caller provides a fallback. stack.popOr(defaultValue) returns the top if present, or the default if empty. Clear intent but may mask bugs.
•Caller always checks isEmpty first: Shifts responsibility to the caller. Works but requires discipline and doubles the number of calls.

EmptyStackHandlingStrategies.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Strategy 1: Throw exception (most common, recommended)
pop(): T {
    if (this.isEmpty()) {
        throw new Error("Stack Underflow: Cannot pop from empty stack");
    }
    return this.internalPop();
}
 
// Strategy 2: Return nullable (requires careful caller handling)
popOrNull(): T | null {
    if (this.isEmpty()) {
        return null;  // Caller MUST check for null
    }
    return this.internalPop();
}
 
// Strategy 3: Return Optional type (type-safe handling)
popOptional(): { hasValue: true; value: T } | { hasValue: false } {
    if (this.isEmpty()) {
        return { hasValue: false };
    }
    return { hasValue: true, value: this.internalPop() };
}
 
// Strategy 4: Return with fallback
popOr(defaultValue: T): T {
    if (this.isEmpty()) {
        return defaultValue;  // Caller provides fallback
    }
    return this.internalPop();
}
 
// Strategy 5: Caller always checks (defensive coding)
// Usage:
if (!stack.isEmpty()) {
    const value = stack.pop();  // Safe because we checked
    process(value);
}

Silent Failures Are Dangerous

Pop in Algorithmic Patterns

Common Pop Patterns

•Matching pop: Pop when you encounter a 'closer' that matches a previously pushed 'opener.' Example: popping opening parenthesis when you see a closing parenthesis.
•Exhaustive pop: Pop everything (while not empty) to process all accumulated items. Example: processing all remaining stack items at the end of an algorithm.
•Conditional pop: Pop only when the top meets certain criteria. Example: in monotonic stacks, pop while the top is greater/less than the current element.
•Process-then-pop: Peek to check the top, process it, then pop. Example: when processing depends on knowing what's at top before committing to removal.
•Restoration pop: Pop to restore a saved state for backtracking. Example: undo operations, recursive state restoration, bracket validation.

PopPatternExamples.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Pattern 1: Matching pop (parentheses validation)
function isValidParentheses(s: string): boolean {
    const stack: string[] = [];
    const pairs: Record<string, string> = {')': '(', ']': '[', '}': '{'};
    
    for (const char of s) {
        if ('([{'.includes(char)) {
            stack.push(char);  // Push openers
        } else if (')]}');.includes(char)) {
            // Matching pop: must match the most recently pushed opener
            if (stack.length === 0 || stack.pop() !== pairs[char]) {
                return false;
            }
        }
    }
    return stack.length === 0;  // All openers must be matched
}
 
// Pattern 2: Exhaustive pop (drain the stack)
function processAllRemaining(stack: Stack<Task>): void {
    while (!stack.isEmpty()) {
        const task = stack.pop();  // Pop everything
        task.finalize();
    }
}
 
// Pattern 3: Conditional pop (monotonic stack)
function nextGreaterElement(nums: number[]): number[] {
    const result = new Array(nums.length).fill(-1);
    const stack: number[] = [];  // stores indices
    
    for (let i = 0; i < nums.length; i++) {
        // Pop while current element is greater than stack top
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            const idx = stack.pop()!;
            result[idx] = nums[i];  // Current is the next greater
        }
        stack.push(i);
    }
    return result;
}

The Pop-Push Balance

Summary: Mastering Pop

We've examined pop from every angle—its semantics, its relationship with push, its implementations, and its role in algorithms. Here are the essential takeaways:

Key Takeaways

•Pop retrieves and removes: Unlike peek, pop is destructive. The returned element is no longer in the stack. This is a commitment—you're done with that element.
•Pop inverts push: Pushing X then immediately popping returns X and restores the previous state. This inverse relationship enables undo, backtracking, and state management.
•O(1) always: Pop is constant-time in all implementations. It operates only on the top element, requiring no traversal or reorganization.
•Empty stack is critical: Popping an empty stack is an error (underflow). Always check isEmpty before pop, or design your algorithm to guarantee the stack won't be empty when you pop.
•Various error-handling strategies: Exceptions, null returns, Optional types, and defaults all have trade-offs. Prefer explicit exceptions to surface bugs early.
•Pop patterns are recognizable: Matching pop, exhaustive pop, conditional pop—these patterns recur across stack-based algorithms.

What's Next:

Page Complete

2 / 5