Skip to content

Stack#

A stack is a LIFO (last-in, first-out) structure: push and pop at the same end (the top). Used in DFS, parsing, undo stacks, and monotonic-stack patterns.

When to use a stack#

Scenario Example
Matching brackets / tags Valid parentheses
Reverse processing order Evaluate postfix
DFS (iterative) Explicit stack instead of recursion
Monotonic stack Next greater element, histogram area
Backtracking path Current path before undo

Complexity#

Operation List-based stack Linked-list stack
Push O(1)* O(1)
Pop O(1) O(1)
Peek O(1) O(1)
Search O(n) O(n)
Space O(n) O(n)

*Amortized for dynamic array growth on push.

In Python, list.append / list.pop() is the standard stack — no custom class needed unless demonstrating implementation.

Only the top is accessible; every push and pop touches the same end (see diagram).

Stack LIFO push and pop at the top

Monotonic stack (FAANG)#

Maintain a stack of indices (or values) that stays monotonically increasing or decreasing. Scan left to right; before pushing, pop while the top violates the property and process the popped index.

Signal Stack type Examples
Next greater/smaller element Decreasing stack of indices LC 739, 496
Largest rectangle in histogram Increasing stack LC 84
Daily temperatures Decreasing stack LC 739

Complexity: each index pushed and popped at most once → O(n) time, O(n) space. See Stack pattern.

Using List#

  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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
class StackList:
    def __init__(self):
        self.stack = []

    def push(self, item):
        """Push item onto the stack."""
        self.stack.append(item)

    def pop(self):
        """Pop item from the stack and return it."""
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        """Return the top item of the stack."""
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        """Check if the stack is empty."""
        return len(self.stack) == 0

    def size(self):
        """Return the size of the stack."""
        return len(self.stack)

    def balanced_parentheses(self, expression):
        """Evaluate balanced parentheses."""
        for char in expression:
            if char == '(':
                self.push(char)
            elif char == ')':
                if self.is_empty():
                    return False
                self.pop()
        return self.is_empty()

    def infix_to_postfix(self, expression):
        """Convert infix to postfix."""
        precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
        output = []
        for char in expression:
            if char.isalnum():  # Operand
                output.append(char)
            elif char == '(':  # Left Parenthesis
                self.push(char)
            elif char == ')':  # Right Parenthesis
                while not self.is_empty() and self.peek() != '(':
                    output.append(self.pop())
                self.pop()  # Pop '('
            else:  # Operator
                while (not self.is_empty() and self.peek() != '(' and
                       precedence[char] <= precedence.get(self.peek(), 0)):
                    output.append(self.pop())
                self.push(char)
        while not self.is_empty():
            output.append(self.pop())
        return ''.join(output)

    def evaluate_postfix(self, expression):
        """Evaluate a postfix expression."""
        for char in expression:
            if char.isdigit():  # Operand
                self.push(int(char))
            else:  # Operator
                right = self.pop()
                left = self.pop()
                if char == '+':
                    self.push(left + right)
                elif char == '-':
                    self.push(left - right)
                elif char == '*':
                    self.push(left * right)
                elif char == '/':
                    self.push(left / right)
                elif char == '^':
                    self.push(left ** right)
        return self.pop()

    def infix_to_prefix(self, expression):
        """Convert infix to prefix."""
        # Reverse the infix expression
        expression = expression[::-1]
        expression = expression.replace('(', 'temp').replace(')', '(').replace('temp', ')')
        postfix = self.infix_to_postfix(expression)
        return postfix[::-1]

    def evaluate_prefix(self, expression):
        """Evaluate a prefix expression."""
        # Reverse the expression to handle it from left to right
        expression = expression[::-1]
        for char in expression:
            if char.isdigit():  # Operand
                self.push(int(char))
            else:  # Operator
                left = self.pop()
                right = self.pop()
                if char == '+':
                    self.push(left + right)
                elif char == '-':
                    self.push(left - right)
                elif char == '*':
                    self.push(left * right)
                elif char == '/':
                    self.push(left / right)
                elif char == '^':
                    self.push(left ** right)
        return self.pop()

expression = "3 + 5 * (2 - 8)"

# Using Stack with List
stack_list = StackList()
postfix = stack_list.infix_to_postfix(expression)
print("Postfix:", postfix)  # Postfix conversion
postfix_eval = stack_list.evaluate_postfix(postfix)
print("Postfix evaluation:", postfix_eval)

prefix = stack_list.infix_to_prefix(expression)
print("Prefix:", prefix)  # Prefix conversion
prefix_eval = stack_list.evaluate_prefix(prefix)
print("Prefix evaluation:", prefix_eval)

Using Linked List#

  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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class StackLinkedList:
    def __init__(self):
        self.top = None

    def push(self, item):
        """Push item onto the stack."""
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        """Pop item from the stack and return it."""
        if self.is_empty():
            return None
        popped_node = self.top
        self.top = self.top.next
        return popped_node.data

    def peek(self):
        """Return the top item of the stack."""
        if self.is_empty():
            return None
        return self.top.data

    def is_empty(self):
        """Check if the stack is empty."""
        return self.top is None

    def size(self):
        """Return the size of the stack."""
        current = self.top
        count = 0
        while current:
            count += 1
            current = current.next
        return count

    def balanced_parentheses(self, expression):
        """Evaluate balanced parentheses."""
        for char in expression:
            if char == '(':
                self.push(char)
            elif char == ')':
                if self.is_empty():
                    return False
                self.pop()
        return self.is_empty()

    def infix_to_postfix(self, expression):
        """Convert infix to postfix."""
        precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
        output = []
        for char in expression:
            if char.isalnum():  # Operand
                output.append(char)
            elif char == '(':  # Left Parenthesis
                self.push(char)
            elif char == ')':  # Right Parenthesis
                while not self.is_empty() and self.peek() != '(':
                    output.append(self.pop())
                self.pop()  # Pop '('
            else:  # Operator
                while (not self.is_empty() and self.peek() != '(' and
                       precedence[char] <= precedence.get(self.peek(), 0)):
                    output.append(self.pop())
                self.push(char)
        while not self.is_empty():
            output.append(self.pop())
        return ''.join(output)

    def evaluate_postfix(self, expression):
        """Evaluate a postfix expression."""
        for char in expression:
            if char.isdigit():  # Operand
                self.push(int(char))
            else:  # Operator
                right = self.pop()
                left = self.pop()
                if char == '+':
                    self.push(left + right)
                elif char == '-':
                    self.push(left - right)
                elif char == '*':
                    self.push(left * right)
                elif char == '/':
                    self.push(left / right)
                elif char == '^':
                    self.push(left ** right)
        return self.pop()

    def infix_to_prefix(self, expression):
        """Convert infix to prefix."""
        # Reverse the infix expression
        expression = expression[::-1]
        expression = expression.replace('(', 'temp').replace(')', '(').replace('temp', ')')
        postfix = self.infix_to_postfix(expression)
        return postfix[::-1]

    def evaluate_prefix(self, expression):
        """Evaluate a prefix expression."""
        # Reverse the expression to handle it from left to right
        expression = expression[::-1]
        for char in expression:
            if char.isdigit():  # Operand
                self.push(int(char))
            else:  # Operator
                left = self.pop()
                right = self.pop()
                if char == '+':
                    self.push(left + right)
                elif char == '-':
                    self.push(left - right)
                elif char == '*':
                    self.push(left * right)
                elif char == '/':
                    self.push(left / right)
                elif char == '^':
                    self.push(left ** right)
        return self.pop()

expression = "3 + 5 * (2 - 8)"

# Using Stack with Linked List
stack_linked_list = StackLinkedList()
postfix = stack_linked_list.infix_to_postfix(expression)
print("Postfix:", postfix)  # Postfix conversion
postfix_eval = stack_linked_list.evaluate_postfix(postfix)
print("Postfix evaluation:", postfix_eval)

prefix = stack_linked_list.infix_to_prefix(expression)
print("Prefix:", prefix)  # Prefix conversion
prefix_eval = stack_linked_list.evaluate_prefix(prefix)
print("Prefix evaluation:", prefix_eval)