Data Structures & AlgorithmsStacks

Common Stack Patterns & Problem Types

LevelIntermediate

Duration75 mins

TopicStacks

1 / 4

Reversing Sequences

The Natural Reverser

Imagine a stack of plates at a buffet. The first plate placed becomes buried at the bottom, while the last plate added sits on top. When you take plates off one by one, they come out in the opposite order from how they went in. This isn't a quirk of the stack—it's the defining property that makes stacks invaluable for reversal operations.

In this page, we'll explore why stacks are the natural data structure for reversing sequences. This isn't merely an academic observation—reversal using stacks appears in string manipulation, undo operations, expression parsing, backtracking algorithms, and countless other domains. By understanding this pattern deeply, you'll recognize reversal problems instantly and reach for stacks with confidence.

What You Will Master

By the end of this page, you will understand why LIFO order produces reversal, trace through reversal operations step-by-step, implement various reversal algorithms using stacks, recognize reversal patterns in disguise, and connect stack reversal to real-world applications like undo/redo and expression parsing.

The Fundamental Insight: LIFO as Reversal

Let's start with the core insight that every engineer should internalize: Last-In, First-Out (LIFO) order is equivalent to reversal.

This isn't coincidental—it's mathematically inherent to the stack structure. When you push elements onto a stack in order [A, B, C, D] and then pop them all, you get [D, C, B, A]. The reversal happens automatically as a consequence of LIFO ordering.

Why does this work mathematically?

Consider a sequence of n elements: e₁, e₂, e₃, ..., eₙ. When we push each element in order:

e₁ is pushed first → sits at the bottom
e₂ is pushed second → sits above e₁
...
eₙ is pushed last → sits at the top

When we pop:

First pop returns eₙ (from top)
Second pop returns eₙ₋₁
...
Last pop returns e₁ (from bottom)

The output sequence is eₙ, eₙ₋₁, ..., e₂, e₁—the exact reverse of the input.

The Reversal Principle

Push all elements of a sequence onto a stack, then pop them all. The order of elements coming out is the reverse of the order going in. This is guaranteed by the LIFO property—no algorithm trickery required.

Contrast with Queues:

To appreciate why stacks are special for reversal, consider what happens with a queue (FIFO):

Push [A, B, C, D] → Queue contains [A, B, C, D]
Dequeue all → Output is [A, B, C, D]

A queue preserves order. A stack reverses it. This fundamental difference determines which data structure to choose:

Need to maintain original order? → Queue
Need to reverse order? → Stack

Order Behavior: Stack vs Queue
Operation	Stack (LIFO)	Queue (FIFO)
Insert A, B, C, D	Top→[D, C, B, A]←Bottom	Front→[A, B, C, D]←Rear
Remove all	[D, C, B, A] — Reversed	[A, B, C, D] — Preserved
Use case	Reversal, backtracking, nesting	Order preservation, scheduling

Visualizing Stack Reversal

Let's trace through a concrete example with a visual representation. We'll reverse the string "HELLO" using a stack.

Initial state: String to reverse is "HELLO"

Phase 1: Push all characters onto the stack

Push Phase: Loading Characters onto Stack
Step	Character	Stack State (top→bottom)	Action
0	—	[ ]	Empty stack
1	H	[H]	Push 'H'
2	E	[E, H]	Push 'E'
3	L	[L, E, H]	Push 'L'
4	L	[L, L, E, H]	Push 'L'
5	O	[O, L, L, E, H]	Push 'O'

Phase 2: Pop all characters and build reversed string

Pop Phase: Building Reversed String
Step	Popped	Stack After Pop	Result So Far
1	O	[L, L, E, H]	"O"
2	L	[L, E, H]	"OL"
3	L	[E, H]	"OLL"
4	E	[H]	"OLLE"
5	H	[ ]	"OLLEH"

Reversal Complete

Input: "HELLO" → Output: "OLLEH". The stack performed the reversal through its natural LIFO behavior. We didn't write reversal logic—the data structure embodied it.

The Mental Model:

Think of the stack as a vertical tower. Elements enter through the top and must exit through the top. An element pushed early gets buried and can only escape after everything above it has left. This "burial" effect is what produces reversal.

Visually, imagine dropping letters into a narrow tube:

  ↓ Input: H, E, L, L, O
  ┌───┐
  │ O │ ← Last in (top)
  │ L │
  │ L │
  │ E │
  │ H │ ← First in (bottom)
  └───┘
  
  ↑ Output: O, L, L, E, H

The first letter to enter (H) is the last to leave. The last letter (O) is first out. Reversal is inevitable.

Implementation Patterns for Stack Reversal

Now let's codify this pattern into reusable implementations. We'll explore three common reversal scenarios:

Reversing a string — The classic example
Reversing a linked list — Using stack as auxiliary storage
Reversing only part of a sequence — Selective reversal

Pattern 1: Reversing a String

The algorithm is straightforward:

Create an empty stack
Push each character onto the stack
Pop all characters and concatenate to form the reversed string

string-reversal.py
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
def reverse_string(s: str) -> str:
    """
    Reverse a string using a stack.
    
    Time Complexity: O(n) - each character pushed and popped once
    Space Complexity: O(n) - stack holds all characters
    """
    stack = []
    
    # Phase 1: Push all characters
    for char in s:
        stack.append(char)
    
    # Phase 2: Pop all characters
    reversed_chars = []
    while stack:
        reversed_chars.append(stack.pop())
    
    return ''.join(reversed_chars)
 
 
# Example usage
original = "HELLO WORLD"
reversed_str = reverse_string(original)
print(f"Original: {original}")
print(f"Reversed: {reversed_str}")
# Output:
# Original: HELLO WORLD
# Reversed: DLROW OLLEH

Why Use a Stack When Simpler Methods Exist?

For simple string reversal, built-in methods (like Python's s[::-1] or JavaScript's s.split('').reverse().join('')) are more concise. The stack approach is valuable because: (1) it teaches the fundamental pattern, (2) it generalizes to more complex scenarios, and (3) it works identically for any sequence type without built-in reversal support.

Reversing Words in a Sentence

A more practical application of stack reversal is reversing the order of words in a sentence while keeping each word's internal character order intact.

Example:

Input: "The quick brown fox"
Output: "fox brown quick The"

This is different from reversing all characters (which would give "xof nworb kciuq ehT"). We want to treat words as atomic units and reverse their order.

reverse-words.py
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
def reverse_words(sentence: str) -> str:
    """
    Reverse the order of words in a sentence.
    
    "The quick brown fox" → "fox brown quick The"
    
    Time Complexity: O(n) where n is the length of the sentence
    Space Complexity: O(n) for the stack and output
    """
    # Split sentence into words
    words = sentence.split()
    
    # Push all words onto stack
    stack = []
    for word in words:
        stack.append(word)
    
    # Pop words to get reversed order
    reversed_words = []
    while stack:
        reversed_words.append(stack.pop())
    
    return ' '.join(reversed_words)
 
 
# Examples
print(reverse_words("The quick brown fox"))
# Output: "fox brown quick The"
 
print(reverse_words("Hello World"))
# Output: "World Hello"
 
print(reverse_words("I love data structures"))
# Output: "structures data love I"

The Key Insight:

The same LIFO principle applies whether we're reversing characters, words, or any other units. The stack doesn't care what we push—it simply returns items in reverse order. This generality is powerful:

Push numbers → Get reversed number sequence
Push list nodes → Get reversed linked list
Push tree nodes → Get reversed traversal
Push operations → Get reversed operation sequence (like undo)

Reversing a Linked List Using a Stack

While linked lists can be reversed in-place with O(1) space using pointer manipulation, the stack-based approach provides a clear, intuitive solution that's easier to implement correctly.

The Approach:

Traverse the linked list and push each node's value onto a stack
Traverse the list again and replace each node's value with the popped value

Alternatively, for creating a new reversed list:

Push all nodes onto the stack
Pop nodes and build a new list in that order

reverse-linked-list.py
Python
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
 
def reverse_linked_list_stack(head: ListNode) -> ListNode:
    """
    Reverse a linked list using a stack.
    
    This approach modifies values in-place rather than
    changing node pointers.
    
    Time Complexity: O(n) - two passes through the list
    Space Complexity: O(n) - stack holds all node values
    """
    if not head:
        return None
    
    # Phase 1: Push all values onto stack
    stack = []
    current = head
    while current:
        stack.append(current.val)
        current = current.next
    
    # Phase 2: Pop values and overwrite nodes
    current = head
    while current:
        current.val = stack.pop()
        current = current.next
    
    return head
 
 
def reverse_linked_list_new(head: ListNode) -> ListNode:
    """
    Create a new reversed linked list using a stack.
    
    This approach creates new nodes rather than modifying
    existing ones.
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    if not head:
        return None
    
    # Push all nodes onto stack
    stack = []
    current = head
    while current:
        stack.append(current)
        current = current.next
    
    # Pop nodes to build reversed list
    new_head = stack.pop()
    current = new_head
    
    while stack:
        current.next = stack.pop()
        current = current.next
    
    current.next = None  # Terminate the list
    
    return new_head
 
 
# Helper to print linked list
def print_list(head):
    values = []
    while head:
        values.append(str(head.val))
        head = head.next
    print(" -> ".join(values))
 
 
# Example: Create list 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print("Original:")
print_list(head)
 
reversed_head = reverse_linked_list_stack(head)
print("Reversed:")
print_list(reversed_head)
# Output:
# Original: 1 -> 2 -> 3 -> 4 -> 5
# Reversed: 5 -> 4 -> 3 -> 2 -> 1

Trade-off: Simplicity vs Efficiency

The stack-based reversal uses O(n) extra space. For production code where memory matters, the in-place pointer reversal (O(1) space) is preferred. However, the stack approach excels when: (1) code clarity is paramount, (2) you're debugging and want easy-to-trace logic, or (3) the linked list is small enough that O(n) space is negligible.

Real-World Applications of Stack Reversal

Stack-based reversal isn't just an academic exercise. It appears throughout software systems in practical, essential ways:

1. Undo/Redo Functionality

Every text editor, design tool, and IDE relies on stacks for undo/redo:

Undo stack: Stores operations in order they were performed
Press undo → Pop the last operation and reverse it
The LIFO order ensures you undo the most recent action first

2. Browser Navigation History

When you click "Back":

Current page is pushed to the forward stack
Previous page is popped from the back stack
The reversal of your browsing order is automatic

3. Expression Parsing and Evaluation

Converting infix to postfix notation and evaluating expressions requires reversing the order of certain tokens. The Shunting-yard algorithm uses stacks precisely because reversal is needed.

4. Path Retracing in Algorithms

Backtracking algorithms (DFS, maze solving) use stacks to:

Record the path taken
Reverse the path when returning to a decision point

Recognition Patterns for Stack Reversal

•"Reverse the order" — Any problem asking to reverse a sequence is a candidate for stacks
•"Match pairs in nesting order" — Matched pairs (parentheses, tags) require LIFO matching
•"Backtrack to previous state" — Returning to earlier positions means reversing recent moves
•"Process most recent first" — When recent items have priority, stacks provide natural ordering
•"Undo chain" — Any operation that needs undoing in reverse chronological order

Stack Reversal in Software Systems
Domain	Reversal Use Case	Why Stack?
Text Editors	Undo typed characters	Most recent keystroke undone first
Web Browsers	Navigate back through history	Most recent page popped first
Compilers	Balance and match brackets	Innermost bracket closed first
File Systems	Traverse path: /a/b/c → [c, b, a]	Deepest directory accessed first when backtracking
Game AI	Backtrack in search trees	Most recent decision reversed first
Databases	Rollback transactions	Most recent change undone first

Time and Space Complexity Analysis

Let's rigorously analyze the costs of stack-based reversal:

Time Complexity: O(n)

For a sequence of n elements:

Push phase: n push operations, each O(1) → Total: O(n)
Pop phase: n pop operations, each O(1) → Total: O(n)
Combined: O(n) + O(n) = O(2n) = O(n)

This is optimal—any reversal algorithm must at least read all elements once, which is O(n). Stack-based reversal meets this lower bound.

Space Complexity: O(n)

The stack must hold all n elements simultaneously at peak usage. This O(n) auxiliary space is the cost of using a stack.

Comparison with In-Place Reversal:

Reversal Approaches Compared
Approach	Time	Space	Code Complexity	Best For
Stack-based	O(n)	O(n)	Low	Clarity, teaching, prototyping
Two-pointer swap	O(n)	O(1)	Medium	Arrays, strings (mutable)
Pointer reversal	O(n)	O(1)	High	Linked lists in production
Recursive	O(n)	O(n) call stack	Medium	When recursion is natural

When to Choose Stack-Based Reversal

Use stack-based reversal when: (1) you're working with immutable data, (2) you need the code to be obviously correct for review or debugging, (3) memory is not constrained, or (4) the problem has other stack-based components (like expression parsing) where reversal is just one step.

Variations and Extensions

The basic reversal pattern can be extended for more sophisticated scenarios:

Partial Reversal: Reverse only a portion of a sequence—push only the elements in the target range, then pop to reverse that section.

Conditional Reversal: Reverse only elements meeting certain criteria (e.g., reverse only the vowels in a string).

Chunked Reversal: Reverse groups of elements rather than individual ones (e.g., reverse every k elements in an array).

Nested Reversal: Reverse with awareness of nesting structures (e.g., reverse a string but keep nested parentheses balanced).

partial-reversal.py
Python
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
def reverse_vowels(s: str) -> str:
    """
    Reverse only the vowels in a string.
    
    "hello world" → "hollo werld"
    
    This demonstrates conditional/selective reversal
    using a stack.
    """
    vowels = set('aeiouAEIOU')
    stack = []
    
    # Push only vowels
    for char in s:
        if char in vowels:
            stack.append(char)
    
    # Rebuild string, replacing vowels with popped values
    result = []
    for char in s:
        if char in vowels:
            result.append(stack.pop())
        else:
            result.append(char)
    
    return ''.join(result)
 
 
# Examples
print(reverse_vowels("hello"))      # "holle"
print(reverse_vowels("leetcode"))   # "leotcede"
print(reverse_vowels("aA"))         # "Aa"

The Pattern Generalizes:

In each variation, the core insight remains: push what you want to reverse, pop to get reversed order. The stack handles the reversal; your code handles the selection criteria.

Summary: Stack Reversal Mastery

We've explored the fundamental connection between stacks and reversal operations. Here are the key insights to internalize:

Key Takeaways

•LIFO = Reversal — The Last-In, First-Out property mathematically guarantees that pushing n elements and popping them all produces the reverse sequence.
•The Pattern is Universal — Characters, words, numbers, nodes, operations—any sequence can be reversed by pushing and popping.
•Time O(n), Space O(n) — Stack reversal is time-optimal but requires auxiliary space equal to the sequence length.
•Real Applications Abound — Undo/redo, browser history, expression parsing, and backtracking all rely on stack reversal.
•Recognition is Key — When you see 'reverse order,' 'most recent first,' or 'backtrack,' think stack.
•Variations Extend the Pattern — Partial, conditional, and chunked reversals all follow the same push-then-pop paradigm.

Pattern Acquired

You now understand stack reversal as a fundamental pattern. When you encounter reversal problems, the solution is immediate: push, then pop. The complexity of the problem shifts from 'how do I reverse?' to 'what do I push?'

What's Next:

Reversal is just one of several powerful stack patterns. In the next page, we'll explore tracking state during traversal—using a stack to maintain context as we process sequences where order matters. This pattern is essential for problems involving nested structures, matching pairs, and hierarchical data.

1 / 4

Loading learning content...

Data Structures & AlgorithmsStacks

Common Stack Patterns & Problem Types

LevelIntermediate

Duration75 mins

TopicStacks

1 / 4

Reversing Sequences

The Natural Reverser

What You Will Master

The Fundamental Insight: LIFO as Reversal

Let's start with the core insight that every engineer should internalize: Last-In, First-Out (LIFO) order is equivalent to reversal.

Why does this work mathematically?

Consider a sequence of n elements: e₁, e₂, e₃, ..., eₙ. When we push each element in order:

e₁ is pushed first → sits at the bottom
e₂ is pushed second → sits above e₁
...
eₙ is pushed last → sits at the top

When we pop:

First pop returns eₙ (from top)
Second pop returns eₙ₋₁
...
Last pop returns e₁ (from bottom)

The output sequence is eₙ, eₙ₋₁, ..., e₂, e₁—the exact reverse of the input.

The Reversal Principle

Contrast with Queues:

To appreciate why stacks are special for reversal, consider what happens with a queue (FIFO):

Push [A, B, C, D] → Queue contains [A, B, C, D]
Dequeue all → Output is [A, B, C, D]

A queue preserves order. A stack reverses it. This fundamental difference determines which data structure to choose:

Need to maintain original order? → Queue
Need to reverse order? → Stack

Order Behavior: Stack vs Queue
Operation	Stack (LIFO)	Queue (FIFO)
Insert A, B, C, D	Top→[D, C, B, A]←Bottom	Front→[A, B, C, D]←Rear
Remove all	[D, C, B, A] — Reversed	[A, B, C, D] — Preserved
Use case	Reversal, backtracking, nesting	Order preservation, scheduling

Visualizing Stack Reversal

Let's trace through a concrete example with a visual representation. We'll reverse the string "HELLO" using a stack.

Initial state: String to reverse is "HELLO"

Phase 1: Push all characters onto the stack

Push Phase: Loading Characters onto Stack
Step	Character	Stack State (top→bottom)	Action
0	—	[ ]	Empty stack
1	H	[H]	Push 'H'
2	E	[E, H]	Push 'E'
3	L	[L, E, H]	Push 'L'
4	L	[L, L, E, H]	Push 'L'
5	O	[O, L, L, E, H]	Push 'O'

Phase 2: Pop all characters and build reversed string

Pop Phase: Building Reversed String
Step	Popped	Stack After Pop	Result So Far
1	O	[L, L, E, H]	"O"
2	L	[L, E, H]	"OL"
3	L	[E, H]	"OLL"
4	E	[H]	"OLLE"
5	H	[ ]	"OLLEH"

Reversal Complete

Input: "HELLO" → Output: "OLLEH". The stack performed the reversal through its natural LIFO behavior. We didn't write reversal logic—the data structure embodied it.

The Mental Model:

Visually, imagine dropping letters into a narrow tube:

  ↓ Input: H, E, L, L, O
  ┌───┐
  │ O │ ← Last in (top)
  │ L │
  │ L │
  │ E │
  │ H │ ← First in (bottom)
  └───┘
  
  ↑ Output: O, L, L, E, H

The first letter to enter (H) is the last to leave. The last letter (O) is first out. Reversal is inevitable.

Implementation Patterns for Stack Reversal

Now let's codify this pattern into reusable implementations. We'll explore three common reversal scenarios:

Reversing a string — The classic example
Reversing a linked list — Using stack as auxiliary storage
Reversing only part of a sequence — Selective reversal

Pattern 1: Reversing a String

The algorithm is straightforward:

Create an empty stack
Push each character onto the stack
Pop all characters and concatenate to form the reversed string

string-reversal.py
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
def reverse_string(s: str) -> str:
    """
    Reverse a string using a stack.
    
    Time Complexity: O(n) - each character pushed and popped once
    Space Complexity: O(n) - stack holds all characters
    """
    stack = []
    
    # Phase 1: Push all characters
    for char in s:
        stack.append(char)
    
    # Phase 2: Pop all characters
    reversed_chars = []
    while stack:
        reversed_chars.append(stack.pop())
    
    return ''.join(reversed_chars)
 
 
# Example usage
original = "HELLO WORLD"
reversed_str = reverse_string(original)
print(f"Original: {original}")
print(f"Reversed: {reversed_str}")
# Output:
# Original: HELLO WORLD
# Reversed: DLROW OLLEH

Why Use a Stack When Simpler Methods Exist?

Reversing Words in a Sentence

A more practical application of stack reversal is reversing the order of words in a sentence while keeping each word's internal character order intact.

Example:

Input: "The quick brown fox"
Output: "fox brown quick The"

This is different from reversing all characters (which would give "xof nworb kciuq ehT"). We want to treat words as atomic units and reverse their order.

reverse-words.py
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
def reverse_words(sentence: str) -> str:
    """
    Reverse the order of words in a sentence.
    
    "The quick brown fox" → "fox brown quick The"
    
    Time Complexity: O(n) where n is the length of the sentence
    Space Complexity: O(n) for the stack and output
    """
    # Split sentence into words
    words = sentence.split()
    
    # Push all words onto stack
    stack = []
    for word in words:
        stack.append(word)
    
    # Pop words to get reversed order
    reversed_words = []
    while stack:
        reversed_words.append(stack.pop())
    
    return ' '.join(reversed_words)
 
 
# Examples
print(reverse_words("The quick brown fox"))
# Output: "fox brown quick The"
 
print(reverse_words("Hello World"))
# Output: "World Hello"
 
print(reverse_words("I love data structures"))
# Output: "structures data love I"

The Key Insight:

Push numbers → Get reversed number sequence
Push list nodes → Get reversed linked list
Push tree nodes → Get reversed traversal
Push operations → Get reversed operation sequence (like undo)

Reversing a Linked List Using a Stack

While linked lists can be reversed in-place with O(1) space using pointer manipulation, the stack-based approach provides a clear, intuitive solution that's easier to implement correctly.

The Approach:

Traverse the linked list and push each node's value onto a stack
Traverse the list again and replace each node's value with the popped value

Alternatively, for creating a new reversed list:

Push all nodes onto the stack
Pop nodes and build a new list in that order

reverse-linked-list.py
Python
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
 
def reverse_linked_list_stack(head: ListNode) -> ListNode:
    """
    Reverse a linked list using a stack.
    
    This approach modifies values in-place rather than
    changing node pointers.
    
    Time Complexity: O(n) - two passes through the list
    Space Complexity: O(n) - stack holds all node values
    """
    if not head:
        return None
    
    # Phase 1: Push all values onto stack
    stack = []
    current = head
    while current:
        stack.append(current.val)
        current = current.next
    
    # Phase 2: Pop values and overwrite nodes
    current = head
    while current:
        current.val = stack.pop()
        current = current.next
    
    return head
 
 
def reverse_linked_list_new(head: ListNode) -> ListNode:
    """
    Create a new reversed linked list using a stack.
    
    This approach creates new nodes rather than modifying
    existing ones.
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    if not head:
        return None
    
    # Push all nodes onto stack
    stack = []
    current = head
    while current:
        stack.append(current)
        current = current.next
    
    # Pop nodes to build reversed list
    new_head = stack.pop()
    current = new_head
    
    while stack:
        current.next = stack.pop()
        current = current.next
    
    current.next = None  # Terminate the list
    
    return new_head
 
 
# Helper to print linked list
def print_list(head):
    values = []
    while head:
        values.append(str(head.val))
        head = head.next
    print(" -> ".join(values))
 
 
# Example: Create list 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print("Original:")
print_list(head)
 
reversed_head = reverse_linked_list_stack(head)
print("Reversed:")
print_list(reversed_head)
# Output:
# Original: 1 -> 2 -> 3 -> 4 -> 5
# Reversed: 5 -> 4 -> 3 -> 2 -> 1

Trade-off: Simplicity vs Efficiency

Real-World Applications of Stack Reversal

Stack-based reversal isn't just an academic exercise. It appears throughout software systems in practical, essential ways:

1. Undo/Redo Functionality

Every text editor, design tool, and IDE relies on stacks for undo/redo:

Undo stack: Stores operations in order they were performed
Press undo → Pop the last operation and reverse it
The LIFO order ensures you undo the most recent action first

2. Browser Navigation History

When you click "Back":

Current page is pushed to the forward stack
Previous page is popped from the back stack
The reversal of your browsing order is automatic

3. Expression Parsing and Evaluation

Converting infix to postfix notation and evaluating expressions requires reversing the order of certain tokens. The Shunting-yard algorithm uses stacks precisely because reversal is needed.

4. Path Retracing in Algorithms

Backtracking algorithms (DFS, maze solving) use stacks to:

Record the path taken
Reverse the path when returning to a decision point

Recognition Patterns for Stack Reversal

•"Reverse the order" — Any problem asking to reverse a sequence is a candidate for stacks
•"Match pairs in nesting order" — Matched pairs (parentheses, tags) require LIFO matching
•"Backtrack to previous state" — Returning to earlier positions means reversing recent moves
•"Process most recent first" — When recent items have priority, stacks provide natural ordering
•"Undo chain" — Any operation that needs undoing in reverse chronological order

Stack Reversal in Software Systems
Domain	Reversal Use Case	Why Stack?
Text Editors	Undo typed characters	Most recent keystroke undone first
Web Browsers	Navigate back through history	Most recent page popped first
Compilers	Balance and match brackets	Innermost bracket closed first
File Systems	Traverse path: /a/b/c → [c, b, a]	Deepest directory accessed first when backtracking
Game AI	Backtrack in search trees	Most recent decision reversed first
Databases	Rollback transactions	Most recent change undone first

Time and Space Complexity Analysis

Let's rigorously analyze the costs of stack-based reversal:

Time Complexity: O(n)

For a sequence of n elements:

Push phase: n push operations, each O(1) → Total: O(n)
Pop phase: n pop operations, each O(1) → Total: O(n)
Combined: O(n) + O(n) = O(2n) = O(n)

This is optimal—any reversal algorithm must at least read all elements once, which is O(n). Stack-based reversal meets this lower bound.

Space Complexity: O(n)

The stack must hold all n elements simultaneously at peak usage. This O(n) auxiliary space is the cost of using a stack.

Comparison with In-Place Reversal:

Reversal Approaches Compared
Approach	Time	Space	Code Complexity	Best For
Stack-based	O(n)	O(n)	Low	Clarity, teaching, prototyping
Two-pointer swap	O(n)	O(1)	Medium	Arrays, strings (mutable)
Pointer reversal	O(n)	O(1)	High	Linked lists in production
Recursive	O(n)	O(n) call stack	Medium	When recursion is natural

When to Choose Stack-Based Reversal

Variations and Extensions

The basic reversal pattern can be extended for more sophisticated scenarios:

Partial Reversal: Reverse only a portion of a sequence—push only the elements in the target range, then pop to reverse that section.

Conditional Reversal: Reverse only elements meeting certain criteria (e.g., reverse only the vowels in a string).

Chunked Reversal: Reverse groups of elements rather than individual ones (e.g., reverse every k elements in an array).

Nested Reversal: Reverse with awareness of nesting structures (e.g., reverse a string but keep nested parentheses balanced).

partial-reversal.py
Python
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
def reverse_vowels(s: str) -> str:
    """
    Reverse only the vowels in a string.
    
    "hello world" → "hollo werld"
    
    This demonstrates conditional/selective reversal
    using a stack.
    """
    vowels = set('aeiouAEIOU')
    stack = []
    
    # Push only vowels
    for char in s:
        if char in vowels:
            stack.append(char)
    
    # Rebuild string, replacing vowels with popped values
    result = []
    for char in s:
        if char in vowels:
            result.append(stack.pop())
        else:
            result.append(char)
    
    return ''.join(result)
 
 
# Examples
print(reverse_vowels("hello"))      # "holle"
print(reverse_vowels("leetcode"))   # "leotcede"
print(reverse_vowels("aA"))         # "Aa"

The Pattern Generalizes:

In each variation, the core insight remains: push what you want to reverse, pop to get reversed order. The stack handles the reversal; your code handles the selection criteria.

Summary: Stack Reversal Mastery

We've explored the fundamental connection between stacks and reversal operations. Here are the key insights to internalize:

Key Takeaways

•LIFO = Reversal — The Last-In, First-Out property mathematically guarantees that pushing n elements and popping them all produces the reverse sequence.
•The Pattern is Universal — Characters, words, numbers, nodes, operations—any sequence can be reversed by pushing and popping.
•Time O(n), Space O(n) — Stack reversal is time-optimal but requires auxiliary space equal to the sequence length.
•Real Applications Abound — Undo/redo, browser history, expression parsing, and backtracking all rely on stack reversal.
•Recognition is Key — When you see 'reverse order,' 'most recent first,' or 'backtrack,' think stack.
•Variations Extend the Pattern — Partial, conditional, and chunked reversals all follow the same push-then-pop paradigm.

Pattern Acquired

What's Next:

1 / 4