Stack as ADT - Learning Module

Loading content...

0/276

The Stack Interface — Push, Pop, Peek, isEmpty

The Four Pillars of Stack Operations

Every data structure is defined by the operations it supports. For the Stack Abstract Data Type, there are exactly four core operations that form its essence:

Push: Add an element to the top
Pop: Remove and return the top element
Peek (or Top): View the top element without removing it
isEmpty: Check whether the stack contains any elements

While some implementations include additional operations (like size() or clear()), these four are the canonical operations that define stack behavior. Understanding each one precisely—its semantics, its edge cases, its complexity guarantees—is essential for mastering the stack data structure and for building reliable software.

What You Will Learn

By the end of this page, you will have a complete, precise understanding of each stack operation. You'll know exactly what each operation does, what guarantees it provides, how it handles edge cases (especially empty stacks), and how these operations compose to enable powerful algorithms. This precision is what separates amateurs from professionals.

Push — Adding Elements to the Stack

The push operation is the fundamental way to add data to a stack. Its behavior is deceptively simple but has important implications.

Formal Definition:

push(element) — Adds the specified element to the top of the stack. After this operation, the element becomes the new top and will be the first element returned by a subsequent pop or peek operation.

Key Properties:

Push Operation Characteristics

•Order-Preserving: The element pushed most recently is always at the top. This maintains the LIFO invariant.
•Non-Destructive to Existing Elements: Push never modifies or removes existing elements. It only adds a new top.
•Always Succeeds (in typical implementations): Unlike pop, push doesn't have a natural failure condition. However, in bounded (fixed-capacity) stacks, push may fail if the stack is full.
•Time Complexity: O(1) — Constant time in well-designed implementations. This is a defining characteristic; if push isn't O(1), reconsider your design.
•Space Complexity: O(1) for the operation itself (though the stack's total space grows by one element).

Visualization:

Imagine a stack containing [A, B] (with B at the top). After push(C):

Before:          After push(C):
┌───┐            ┌───┐
│ B │ ← top      │ C │ ← new top
├───┤            ├───┤
│ A │            │ B │
└───┘            ├───┤
                 │ A │
                 └───┘

The new element C is now at the top. A and B remain exactly where they were, unchanged.

pushOperation
1
2
3
4
5
6
7
8
9
10
11
// Push operation behavior demonstration
const stack = new Stack<string>();
 
stack.push("A");    // Stack: [A] (A is top)
stack.push("B");    // Stack: [A, B] (B is top)
stack.push("C");    // Stack: [A, B, C] (C is top)
 
// The stack now contains three elements.
// C will be the first to come out (LIFO).
// Pushing never fails in unbounded stacks.
// Each push takes O(1) time.

Bounded Stacks and Overflow

In fixed-capacity stack implementations (common in embedded systems or when using a fixed-size array), push can fail with a 'stack overflow' error when the stack is full. This is where the famous 'stack overflow' error name comes from—though in runtime contexts, it usually refers to the call stack exceeding its memory limit.

Pop — Removing Elements from the Stack

The pop operation is the counterpart to push—it removes and returns the most recently added element. This is where the LIFO property manifests directly.

Formal Definition:

pop() — Removes the element at the top of the stack and returns it. After this operation, the element that was second from the top (if any) becomes the new top.

Key Properties:

Pop Operation Characteristics

•Destructive Operation: Unlike peek, pop modifies the stack. The element is permanently removed (unless you save the return value).
•Returns the Removed Element: Pop isn't just removal; it's retrieval + removal. The caller receives the element that was at the top.
•LIFO Ordering: Pop always returns the most recently pushed element that hasn't already been popped. This is the defining behavior of stacks.
•Precondition: Stack Must Be Non-Empty: Popping from an empty stack is an error. How this error is handled varies by implementation (exception, special return value, undefined behavior).
•Time Complexity: O(1) — Constant time. Pop should always be a fast operation.

Visualization:

Imagine a stack containing [A, B, C] (with C at the top). After pop():

Before pop():    After pop():
┌───┐            ┌───┐
│ C │ ← top      │ B │ ← new top
├───┤            ├───┤
│ B │            │ A │
├───┤            └───┘
│ A │            
└───┘            Returns: C

C is removed and returned. B is now the top. A remains unchanged at the bottom.

popOperation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Pop operation behavior demonstration
const stack = new Stack<string>();
stack.push("A");
stack.push("B");
stack.push("C");
 
// Stack is now [A, B, C] with C at top
 
const first = stack.pop();   // Returns "C", Stack: [A, B]
const second = stack.pop();  // Returns "B", Stack: [A]
const third = stack.pop();   // Returns "A", Stack: []
 
// Stack is now empty
// The next pop would throw an error!
try {
    stack.pop();  // Error: Stack is empty
} catch (e) {
    console.log("Cannot pop from empty stack");
}

The Empty Stack Problem

Popping from an empty stack is one of the most common sources of bugs when working with stacks. Always either check isEmpty() before popping, or be prepared to handle the error/exception. Different languages handle this differently: Java throws NoSuchElementException, Python raises IndexError, and some C implementations have undefined behavior.

Peek/Top — Viewing the Top Element

The peek operation (sometimes called top) allows you to see what's at the top of the stack without modifying the stack. This is crucial for algorithms that need to make decisions based on the top element.

Formal Definition:

peek() — Returns the element at the top of the stack without removing it. The stack remains unchanged after this operation.

Key Properties:

Peek Operation Characteristics

•Non-Destructive: Unlike pop, peek leaves the stack exactly as it was. The element remains at the top.
•Idempotent: Calling peek multiple times in succession always returns the same value (assuming no other operations modify the stack).
•Read-Only Access: Peek provides observation without mutation—essential for making decisions before committing to a pop.
•Precondition: Stack Must Be Non-Empty: Like pop, peeking at an empty stack is an error.
•Time Complexity: O(1) — Just returning a reference to the top element, no traversal needed.

Comparison with Pop:

Aspect	peek()	pop()
Returns top element?	Yes	Yes
Removes top element?	No	Yes
Changes stack state?	No	Yes
Can be called repeatedly with same result?	Yes	No
Safe for "look before you leap" logic?	Yes	No

peekOperation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Peek operation behavior demonstration
const stack = new Stack<number>();
stack.push(10);
stack.push(20);
stack.push(30);
 
// Stack: [10, 20, 30] with 30 at top
 
console.log(stack.peek());   // Output: 30
console.log(stack.peek());   // Output: 30 (same result, stack unchanged)
console.log(stack.size());   // Output: 3 (still 3 elements)
 
// Peek is perfect for conditional logic before popping
if (stack.peek() > 25) {
    const value = stack.pop();  // Now we commit to removing it
    console.log("Removed:", value);  // Output: Removed: 30
}
 
console.log(stack.peek());   // Output: 20 (new top after pop)

Why Peek Matters

Peek enables 'look before you leap' programming. In bracket matching, you peek to see if the top bracket matches the current one before deciding to pop. In expression evaluation, you peek at operator precedence before deciding to apply operators. Without peek, many stack algorithms would be much more awkward to implement.

isEmpty — Checking Whether the Stack Is Empty

The isEmpty operation is a query operation that reports whether the stack currently contains any elements. While it might seem trivially simple, it's absolutely essential for safe stack usage.

Formal Definition:

isEmpty() — Returns true if the stack contains zero elements, false otherwise.

Key Properties:

isEmpty Operation Characteristics

•Boolean Result: Returns exactly true or false—a binary condition.
•Non-Destructive: Like peek, isEmpty merely queries the stack without modifying it.
•Always Succeeds: Unlike pop and peek, isEmpty can never fail. It's valid on any stack, including an empty one.
•Guard Condition: isEmpty is primarily used as a precondition check before pop or peek operations.
•Time Complexity: O(1) — Implementations typically track size explicitly, making this an instant check.

Critical Usage Pattern:

The most important use of isEmpty is to guard pop and peek operations:

if (!stack.isEmpty()) {
    const value = stack.pop();  // Safe: we know there's at least one element
    process(value);
}

Alternatively, in loop contexts:

while (!stack.isEmpty()) {
    const value = stack.pop();  // Safe: loop condition guarantees non-empty
    process(value);
}

This pattern—check isEmpty before pop/peek—is so fundamental that it should become automatic.

isEmptyOperation
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
// isEmpty operation behavior demonstration
const stack = new Stack<string>();
 
console.log(stack.isEmpty());  // Output: true (stack starts empty)
 
stack.push("first");
console.log(stack.isEmpty());  // Output: false (stack has one element)
 
stack.push("second");
console.log(stack.isEmpty());  // Output: false (stack has two elements)
 
stack.pop();
console.log(stack.isEmpty());  // Output: false (stack still has one element)
 
stack.pop();
console.log(stack.isEmpty());  // Output: true (back to empty)
 
// The canonical "drain the stack" pattern:
stack.push("A");
stack.push("B");
stack.push("C");
 
while (!stack.isEmpty()) {
    console.log(stack.pop());  // Outputs: C, B, A (LIFO order)
}
// Stack is now guaranteed to be empty

isEmpty vs. size() == 0

Some programmers use size() == 0 instead of isEmpty(). While functionally equivalent, isEmpty() is preferred because: (1) it's more readable and intent-clear, (2) some implementations might compute isEmpty() more efficiently than size(), and (3) it's the canonical idiom across standard libraries.

Additional Operations — size(), clear(), and Others

While push, pop, peek, and isEmpty form the essential core of the Stack ADT, many implementations provide additional convenience operations. These are not strictly necessary (you can achieve their effects with the core operations), but they enhance usability and sometimes performance.

Common Additional Stack Operations
Operation	Description	Time Complexity	Notes
size()	Returns the number of elements in the stack	O(1)*	Useful for capacity checks; can be computed from isEmpty but less efficient that way
clear()	Removes all elements from the stack	O(1) or O(n)**	Resets stack to empty state; useful for reusing stack objects
isFull()	Returns true if stack is at maximum capacity	O(1)	Only relevant for bounded stacks; unbounded stacks are never 'full'
toArray()	Returns all elements as an array	O(n)	Useful for debugging, iteration, or interfacing with array-based APIs
search(element)	Returns the position of an element from the top	O(n)	Legacy operation (in Java Stack); not commonly used

Notes on time complexity:

* size() is O(1) if the implementation tracks count explicitly, which most do. If not, it would require traversing the stack, making it O(n).

** clear() is O(1) if the implementation simply resets pointers/indices. In languages with garbage collection, this is common. In languages with manual memory management, clear() might need to deallocate each element, making it O(n).

additionalOperations
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
// Additional stack operations demonstration
const stack = new Stack<number>();
 
// Build up the stack
stack.push(10);
stack.push(20);
stack.push(30);
 
// size() - how many elements?
console.log(stack.size());  // Output: 3
 
// Using size for iteration (less common than isEmpty loop)
const count = stack.size();
for (let i = 0; i < count; i++) {
    console.log(stack.pop());  // Outputs: 30, 20, 10
}
 
// Rebuild...
stack.push(100);
stack.push(200);
 
// clear() - reset to empty
stack.clear();
console.log(stack.isEmpty());  // Output: true
console.log(stack.size());     // Output: 0

Minimalism vs. Convenience

There's a design tension between minimal interfaces (just the essential operations) and rich interfaces (many convenience methods). The purist view is that size() isn't necessary because you can track it externally. The pragmatic view is that size() is so commonly needed that including it reduces boilerplate and bugs. Most production stack implementations include size().

Error Handling Strategies for Stack Operations

What happens when you pop or peek an empty stack? Different languages and libraries handle this differently. Understanding these approaches is crucial for writing robust code.

The Three Common Approaches:

Error Handling Approaches

•Exception/Error Throwing — The operation throws an exception (Java's NoSuchElementException, Python's IndexError). The caller must catch the exception or allow it to propagate. This is explicit and prevents silent failures.
•Special Return Value — The operation returns a special value like null, undefined, or None to indicate failure. The caller must check the return value. This avoids exception overhead but risks null pointer errors if the caller forgets to check.
•Undefined Behavior — The operation's behavior is undefined for empty stacks. This is common in low-level C code. It's fastest (no checks) but dangerous if misused.

Exception-Based (Recommended)

•Errors are explicit and impossible to ignore
•Stack traces aid debugging
•Matches language idioms (Java, Python)
•Works well with try-catch patterns
•Clear separation of success/failure paths

Special Return Value

•Errors can be silently ignored
•null can propagate and cause distant failures
•Caller must remember to check return
•Ambiguous if null is a valid element
•Mixing data and signaling in return value

errorHandling
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
// Exception-based error handling (recommended)
class Stack<T> {
    private items: T[] = [];
    
    pop(): T {
        if (this.isEmpty()) {
            throw new Error("Stack underflow: cannot pop from empty stack");
        }
        return this.items.pop()!;
    }
    
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Stack underflow: cannot peek empty stack");
        }
        return this.items[this.items.length - 1];
    }
    
    isEmpty(): boolean {
        return this.items.length === 0;
    }
}
 
// Safe usage pattern with exceptions:
const stack = new Stack<number>();
stack.push(42);
 
try {
    while (true) {
        console.log(stack.pop());
    }
} catch (e) {
    console.log("Stack is now empty");
}
 
// Better: check first to avoid exception overhead
while (!stack.isEmpty()) {
    console.log(stack.pop());
}

Defensive Programming

The safest approach is to always check isEmpty() before pop/peek, treating the exception as a bug catcher rather than a control flow mechanism. Exceptions are for exceptional situations—an empty stack should be detected proactively, not reactively.

Operation Composition and Common Idioms

Individual stack operations gain their power when composed into idiomatic patterns. These patterns recur across countless algorithms and become second nature to experienced programmers.

Common Stack Idioms

•Push-Pop Symmetry: Every push has a corresponding pop in balanced algorithms. In bracket matching, each '(' pushed requires a ')' to pop it. Mismatched counts indicate an error.
•Drain Loop: while (!isEmpty()) { process(pop()); } — Process all elements in LIFO order. This is the most common iteration pattern for stacks.
•Peek-Then-Pop: if (peek() == expected) { pop(); } — Make a decision based on the top, then conditionally modify. Essential for parsers and evaluators.
•Push-All-Pop-All: Push n items, then pop n items to get them in reverse order. This is how stacks reverse sequences.
•Conditional Push/Pop: Use peek to decide whether to push or pop. Monotonic stack algorithms depend heavily on this pattern.

stackIdioms
TypeScript
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
// Idiom 1: Push-All, Pop-All (Reversal)
function reverse<T>(items: T[]): T[] {
    const stack = new Stack<T>();
    
    // Push all items
    for (const item of items) {
        stack.push(item);
    }
    
    // Pop all items (they come out reversed)
    const reversed: T[] = [];
    while (!stack.isEmpty()) {
        reversed.push(stack.pop());
    }
    
    return reversed;
}
 
// Idiom 2: Peek-Then-Pop (Bracket Matching)
function isValidBrackets(s: string): boolean {
    const stack = new Stack<string>();
    const pairs: Record<string, string> = {
        ')': '(',
        ']': '[',
        '}': '{',
    };
    
    for (const char of s) {
        if ('([{'.includes(char)) {
            stack.push(char);  // Push opening brackets
        } else if (')]}').includes(char)) {
            // Peek to check match, then pop
            if (stack.isEmpty() || stack.peek() !== pairs[char]) {
                return false;
            }
            stack.pop();  // Matched - remove opening bracket
        }
    }
    
    return stack.isEmpty();  // Valid if all brackets matched
}
 
// Idiom 3: Drain Loop (Process All)
function processAllInReverse(items: number[]): void {
    const stack = new Stack<number>();
    
    for (const item of items) {
        stack.push(item);
    }
    
    // Classic drain loop
    while (!stack.isEmpty()) {
        const current = stack.pop();
        console.log("Processing:", current);
    }
}

Patterns Become Intuition

These idioms may seem mechanical now, but with practice, they become automatic. When you see a problem requiring reversal, your mind will immediately reach for push-all-pop-all. When you see matching pairs, you'll think peek-then-pop. This is algorithmic fluency.

Complexity Guarantees

A key part of the Stack ADT contract is the performance guarantee for each operation. While the ADT doesn't specify implementation, it does typically come with expectations about efficiency.

Stack Operation Complexity Guarantees
Operation	Time Complexity	Space Complexity	Notes
push(x)	O(1) amortized*	O(1)	Must be constant time for the stack to be useful
pop()	O(1)	O(1)	Always constant time; no traversal needed
peek()	O(1)	O(1)	Just returning a reference; trivial
isEmpty()	O(1)	O(1)	Simple comparison; trivial
size()	O(1)**	O(1)	Assuming size is tracked explicitly
clear()	O(1) or O(n)***	O(1)	Depends on memory management

Notes:

* push() is O(1) amortized for dynamic array implementations because occasional resizing operations take O(n). However, averaging over many operations, each push costs O(1). Linked list implementations have true O(1) push with no amortization needed.

** size() is O(1) if the implementation maintains an explicit count variable. This is standard practice.

*** clear() can be O(1) if we just reset an index (array-based) or null out the head pointer (linked list) and let garbage collection handle cleanup. In languages requiring manual deallocation, it may be O(n).

These guarantees are what make stacks so powerful for algorithm design. When you use a stack, you can rely on every fundamental operation being essentially instant, no matter how many elements are in the stack.

Why O(1) Matters

An algorithm that performs n stack operations (push/pop) runs in O(n) time total. If stack operations were O(n) each, the algorithm would be O(n²)—unacceptable for large inputs. The constant-time guarantee for stack operations is what makes stack-based algorithms efficient.

Summary: The Stack Interface

We've thoroughly explored each operation that defines the Stack ADT. This precision—knowing exactly what each operation does, when it fails, and how fast it runs—is what enables you to use stacks confidently in any context.

Key Takeaways

•push(x) adds x to the top in O(1) time. It never fails in unbounded stacks.
•pop() removes and returns the top element in O(1) time. It fails on empty stacks.
•peek() returns the top element without removing it in O(1) time. It fails on empty stacks.
•isEmpty() checks for emptiness in O(1) time. It never fails.
•Always check isEmpty() before pop/peek to avoid errors. This is the fundamental defensive pattern.
•Additional operations like size() and clear() are common conveniences, not core requirements.
•Error handling varies by language, but exception-based approaches are generally preferred.
•Common idioms (drain loop, peek-then-pop, push-all-pop-all) become automatic with practice.

What's next:

Now that we understand the Stack ADT's operations precisely, the next page explores why ADT thinking matters for stacks in particular. We'll see how the separation of interface and implementation enables flexibility, maintainability, and clean software design.

Page Complete

You now have complete mastery of the Stack ADT interface. You know what push, pop, peek, and isEmpty do; when they fail; how fast they run; and how they compose into common patterns. This knowledge is the foundation for implementing stacks and for using them effectively in algorithms.

The Stack Interface — Push, Pop, Peek, isEmpty

The Four Pillars of Stack Operations

Every data structure is defined by the operations it supports. For the Stack Abstract Data Type, there are exactly four core operations that form its essence:

Push: Add an element to the top
Pop: Remove and return the top element
Peek (or Top): View the top element without removing it
isEmpty: Check whether the stack contains any elements

What You Will Learn

Push — Adding Elements to the Stack

The push operation is the fundamental way to add data to a stack. Its behavior is deceptively simple but has important implications.

Formal Definition:

push(element) — Adds the specified element to the top of the stack. After this operation, the element becomes the new top and will be the first element returned by a subsequent pop or peek operation.

Key Properties:

Push Operation Characteristics

•Order-Preserving: The element pushed most recently is always at the top. This maintains the LIFO invariant.
•Non-Destructive to Existing Elements: Push never modifies or removes existing elements. It only adds a new top.
•Always Succeeds (in typical implementations): Unlike pop, push doesn't have a natural failure condition. However, in bounded (fixed-capacity) stacks, push may fail if the stack is full.
•Time Complexity: O(1) — Constant time in well-designed implementations. This is a defining characteristic; if push isn't O(1), reconsider your design.
•Space Complexity: O(1) for the operation itself (though the stack's total space grows by one element).

Visualization:

Imagine a stack containing [A, B] (with B at the top). After push(C):

Before:          After push(C):
┌───┐            ┌───┐
│ B │ ← top      │ C │ ← new top
├───┤            ├───┤
│ A │            │ B │
└───┘            ├───┤
                 │ A │
                 └───┘

The new element C is now at the top. A and B remain exactly where they were, unchanged.

pushOperation
1
2
3
4
5
6
7
8
9
10
11
// Push operation behavior demonstration
const stack = new Stack<string>();
 
stack.push("A");    // Stack: [A] (A is top)
stack.push("B");    // Stack: [A, B] (B is top)
stack.push("C");    // Stack: [A, B, C] (C is top)
 
// The stack now contains three elements.
// C will be the first to come out (LIFO).
// Pushing never fails in unbounded stacks.
// Each push takes O(1) time.

Bounded Stacks and Overflow

Pop — Removing Elements from the Stack

The pop operation is the counterpart to push—it removes and returns the most recently added element. This is where the LIFO property manifests directly.

Formal Definition:

pop() — Removes the element at the top of the stack and returns it. After this operation, the element that was second from the top (if any) becomes the new top.

Key Properties:

Pop Operation Characteristics

•Destructive Operation: Unlike peek, pop modifies the stack. The element is permanently removed (unless you save the return value).
•Returns the Removed Element: Pop isn't just removal; it's retrieval + removal. The caller receives the element that was at the top.
•LIFO Ordering: Pop always returns the most recently pushed element that hasn't already been popped. This is the defining behavior of stacks.
•Precondition: Stack Must Be Non-Empty: Popping from an empty stack is an error. How this error is handled varies by implementation (exception, special return value, undefined behavior).
•Time Complexity: O(1) — Constant time. Pop should always be a fast operation.

Visualization:

Imagine a stack containing [A, B, C] (with C at the top). After pop():

Before pop():    After pop():
┌───┐            ┌───┐
│ C │ ← top      │ B │ ← new top
├───┤            ├───┤
│ B │            │ A │
├───┤            └───┘
│ A │            
└───┘            Returns: C

C is removed and returned. B is now the top. A remains unchanged at the bottom.

popOperation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Pop operation behavior demonstration
const stack = new Stack<string>();
stack.push("A");
stack.push("B");
stack.push("C");
 
// Stack is now [A, B, C] with C at top
 
const first = stack.pop();   // Returns "C", Stack: [A, B]
const second = stack.pop();  // Returns "B", Stack: [A]
const third = stack.pop();   // Returns "A", Stack: []
 
// Stack is now empty
// The next pop would throw an error!
try {
    stack.pop();  // Error: Stack is empty
} catch (e) {
    console.log("Cannot pop from empty stack");
}

The Empty Stack Problem

Peek/Top — Viewing the Top Element

Formal Definition:

peek() — Returns the element at the top of the stack without removing it. The stack remains unchanged after this operation.

Key Properties:

Peek Operation Characteristics

•Non-Destructive: Unlike pop, peek leaves the stack exactly as it was. The element remains at the top.
•Idempotent: Calling peek multiple times in succession always returns the same value (assuming no other operations modify the stack).
•Read-Only Access: Peek provides observation without mutation—essential for making decisions before committing to a pop.
•Precondition: Stack Must Be Non-Empty: Like pop, peeking at an empty stack is an error.
•Time Complexity: O(1) — Just returning a reference to the top element, no traversal needed.

Comparison with Pop:

Aspect	peek()	pop()
Returns top element?	Yes	Yes
Removes top element?	No	Yes
Changes stack state?	No	Yes
Can be called repeatedly with same result?	Yes	No
Safe for "look before you leap" logic?	Yes	No

peekOperation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Peek operation behavior demonstration
const stack = new Stack<number>();
stack.push(10);
stack.push(20);
stack.push(30);
 
// Stack: [10, 20, 30] with 30 at top
 
console.log(stack.peek());   // Output: 30
console.log(stack.peek());   // Output: 30 (same result, stack unchanged)
console.log(stack.size());   // Output: 3 (still 3 elements)
 
// Peek is perfect for conditional logic before popping
if (stack.peek() > 25) {
    const value = stack.pop();  // Now we commit to removing it
    console.log("Removed:", value);  // Output: Removed: 30
}
 
console.log(stack.peek());   // Output: 20 (new top after pop)

Why Peek Matters

isEmpty — Checking Whether the Stack Is Empty

The isEmpty operation is a query operation that reports whether the stack currently contains any elements. While it might seem trivially simple, it's absolutely essential for safe stack usage.

Formal Definition:

isEmpty() — Returns true if the stack contains zero elements, false otherwise.

Key Properties:

isEmpty Operation Characteristics

•Boolean Result: Returns exactly true or false—a binary condition.
•Non-Destructive: Like peek, isEmpty merely queries the stack without modifying it.
•Always Succeeds: Unlike pop and peek, isEmpty can never fail. It's valid on any stack, including an empty one.
•Guard Condition: isEmpty is primarily used as a precondition check before pop or peek operations.
•Time Complexity: O(1) — Implementations typically track size explicitly, making this an instant check.

Critical Usage Pattern:

The most important use of isEmpty is to guard pop and peek operations:

if (!stack.isEmpty()) {
    const value = stack.pop();  // Safe: we know there's at least one element
    process(value);
}

Alternatively, in loop contexts:

while (!stack.isEmpty()) {
    const value = stack.pop();  // Safe: loop condition guarantees non-empty
    process(value);
}

This pattern—check isEmpty before pop/peek—is so fundamental that it should become automatic.

isEmptyOperation
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
// isEmpty operation behavior demonstration
const stack = new Stack<string>();
 
console.log(stack.isEmpty());  // Output: true (stack starts empty)
 
stack.push("first");
console.log(stack.isEmpty());  // Output: false (stack has one element)
 
stack.push("second");
console.log(stack.isEmpty());  // Output: false (stack has two elements)
 
stack.pop();
console.log(stack.isEmpty());  // Output: false (stack still has one element)
 
stack.pop();
console.log(stack.isEmpty());  // Output: true (back to empty)
 
// The canonical "drain the stack" pattern:
stack.push("A");
stack.push("B");
stack.push("C");
 
while (!stack.isEmpty()) {
    console.log(stack.pop());  // Outputs: C, B, A (LIFO order)
}
// Stack is now guaranteed to be empty

isEmpty vs. size() == 0

Additional Operations — size(), clear(), and Others

Common Additional Stack Operations
Operation	Description	Time Complexity	Notes
size()	Returns the number of elements in the stack	O(1)*	Useful for capacity checks; can be computed from isEmpty but less efficient that way
clear()	Removes all elements from the stack	O(1) or O(n)**	Resets stack to empty state; useful for reusing stack objects
isFull()	Returns true if stack is at maximum capacity	O(1)	Only relevant for bounded stacks; unbounded stacks are never 'full'
toArray()	Returns all elements as an array	O(n)	Useful for debugging, iteration, or interfacing with array-based APIs
search(element)	Returns the position of an element from the top	O(n)	Legacy operation (in Java Stack); not commonly used

Notes on time complexity:

* size() is O(1) if the implementation tracks count explicitly, which most do. If not, it would require traversing the stack, making it O(n).

additionalOperations
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
// Additional stack operations demonstration
const stack = new Stack<number>();
 
// Build up the stack
stack.push(10);
stack.push(20);
stack.push(30);
 
// size() - how many elements?
console.log(stack.size());  // Output: 3
 
// Using size for iteration (less common than isEmpty loop)
const count = stack.size();
for (let i = 0; i < count; i++) {
    console.log(stack.pop());  // Outputs: 30, 20, 10
}
 
// Rebuild...
stack.push(100);
stack.push(200);
 
// clear() - reset to empty
stack.clear();
console.log(stack.isEmpty());  // Output: true
console.log(stack.size());     // Output: 0

Minimalism vs. Convenience

Error Handling Strategies for Stack Operations

What happens when you pop or peek an empty stack? Different languages and libraries handle this differently. Understanding these approaches is crucial for writing robust code.

The Three Common Approaches:

Error Handling Approaches

•Exception/Error Throwing — The operation throws an exception (Java's NoSuchElementException, Python's IndexError). The caller must catch the exception or allow it to propagate. This is explicit and prevents silent failures.
•Special Return Value — The operation returns a special value like null, undefined, or None to indicate failure. The caller must check the return value. This avoids exception overhead but risks null pointer errors if the caller forgets to check.
•Undefined Behavior — The operation's behavior is undefined for empty stacks. This is common in low-level C code. It's fastest (no checks) but dangerous if misused.

Exception-Based (Recommended)

•Errors are explicit and impossible to ignore
•Stack traces aid debugging
•Matches language idioms (Java, Python)
•Works well with try-catch patterns
•Clear separation of success/failure paths

Special Return Value

•Errors can be silently ignored
•null can propagate and cause distant failures
•Caller must remember to check return
•Ambiguous if null is a valid element
•Mixing data and signaling in return value

errorHandling
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
// Exception-based error handling (recommended)
class Stack<T> {
    private items: T[] = [];
    
    pop(): T {
        if (this.isEmpty()) {
            throw new Error("Stack underflow: cannot pop from empty stack");
        }
        return this.items.pop()!;
    }
    
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Stack underflow: cannot peek empty stack");
        }
        return this.items[this.items.length - 1];
    }
    
    isEmpty(): boolean {
        return this.items.length === 0;
    }
}
 
// Safe usage pattern with exceptions:
const stack = new Stack<number>();
stack.push(42);
 
try {
    while (true) {
        console.log(stack.pop());
    }
} catch (e) {
    console.log("Stack is now empty");
}
 
// Better: check first to avoid exception overhead
while (!stack.isEmpty()) {
    console.log(stack.pop());
}

Defensive Programming

Operation Composition and Common Idioms

Individual stack operations gain their power when composed into idiomatic patterns. These patterns recur across countless algorithms and become second nature to experienced programmers.

Common Stack Idioms

•Push-Pop Symmetry: Every push has a corresponding pop in balanced algorithms. In bracket matching, each '(' pushed requires a ')' to pop it. Mismatched counts indicate an error.
•Drain Loop: while (!isEmpty()) { process(pop()); } — Process all elements in LIFO order. This is the most common iteration pattern for stacks.
•Peek-Then-Pop: if (peek() == expected) { pop(); } — Make a decision based on the top, then conditionally modify. Essential for parsers and evaluators.
•Push-All-Pop-All: Push n items, then pop n items to get them in reverse order. This is how stacks reverse sequences.
•Conditional Push/Pop: Use peek to decide whether to push or pop. Monotonic stack algorithms depend heavily on this pattern.

stackIdioms
TypeScript
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
// Idiom 1: Push-All, Pop-All (Reversal)
function reverse<T>(items: T[]): T[] {
    const stack = new Stack<T>();
    
    // Push all items
    for (const item of items) {
        stack.push(item);
    }
    
    // Pop all items (they come out reversed)
    const reversed: T[] = [];
    while (!stack.isEmpty()) {
        reversed.push(stack.pop());
    }
    
    return reversed;
}
 
// Idiom 2: Peek-Then-Pop (Bracket Matching)
function isValidBrackets(s: string): boolean {
    const stack = new Stack<string>();
    const pairs: Record<string, string> = {
        ')': '(',
        ']': '[',
        '}': '{',
    };
    
    for (const char of s) {
        if ('([{'.includes(char)) {
            stack.push(char);  // Push opening brackets
        } else if (')]}').includes(char)) {
            // Peek to check match, then pop
            if (stack.isEmpty() || stack.peek() !== pairs[char]) {
                return false;
            }
            stack.pop();  // Matched - remove opening bracket
        }
    }
    
    return stack.isEmpty();  // Valid if all brackets matched
}
 
// Idiom 3: Drain Loop (Process All)
function processAllInReverse(items: number[]): void {
    const stack = new Stack<number>();
    
    for (const item of items) {
        stack.push(item);
    }
    
    // Classic drain loop
    while (!stack.isEmpty()) {
        const current = stack.pop();
        console.log("Processing:", current);
    }
}

Patterns Become Intuition

Complexity Guarantees

A key part of the Stack ADT contract is the performance guarantee for each operation. While the ADT doesn't specify implementation, it does typically come with expectations about efficiency.

Stack Operation Complexity Guarantees
Operation	Time Complexity	Space Complexity	Notes
push(x)	O(1) amortized*	O(1)	Must be constant time for the stack to be useful
pop()	O(1)	O(1)	Always constant time; no traversal needed
peek()	O(1)	O(1)	Just returning a reference; trivial
isEmpty()	O(1)	O(1)	Simple comparison; trivial
size()	O(1)**	O(1)	Assuming size is tracked explicitly
clear()	O(1) or O(n)***	O(1)	Depends on memory management

Notes:

** size() is O(1) if the implementation maintains an explicit count variable. This is standard practice.

Why O(1) Matters

Summary: The Stack Interface

Key Takeaways

•push(x) adds x to the top in O(1) time. It never fails in unbounded stacks.
•pop() removes and returns the top element in O(1) time. It fails on empty stacks.
•peek() returns the top element without removing it in O(1) time. It fails on empty stacks.
•isEmpty() checks for emptiness in O(1) time. It never fails.
•Always check isEmpty() before pop/peek to avoid errors. This is the fundamental defensive pattern.
•Additional operations like size() and clear() are common conveniences, not core requirements.
•Error handling varies by language, but exception-based approaches are generally preferred.
•Common idioms (drain loop, peek-then-pop, push-all-pop-all) become automatic with practice.

What's next:

Page Complete