Common Stack Operations

Beyond the basic push and pop, there are several important patterns when working with stacks.

Traversing a Stack

To process all elements while preserving the original stack:

def traverse_stack(stack):
    temp = []

    # Process and transfer to temp
    while not stack.is_empty():
        item = stack.pop()
        print(item)
        temp.append(item)

    # Restore original stack
    while temp:
        stack.push(temp.pop())

Reversing a Stack

def reverse_stack(stack):
    temp = []
    while not stack.is_empty():
        temp.append(stack.pop())

    for item in temp:
        stack.push(item)

    return stack

Finding Min/Max in O(1)

A powerful pattern is maintaining a second stack to track minimums:

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        # Push current minimum
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))

    def pop(self):
        self.min_stack.pop()
        return self.stack.pop()

    def get_min(self):
        return self.min_stack[-1]

Stack with Constant Time Retrieval

class StackWithMax:
    def __init__(self):
        self.stack = []
        self.max_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.max_stack or val >= self.max_stack[-1]:
            self.max_stack.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.max_stack[-1]:
            self.max_stack.pop()
        return val

    def get_max(self):
        return self.max_stack[-1] if self.max_stack else None

Practice Pattern: Two Stack Problems

Many problems require managing two stacks simultaneously:

• Implementing a queue with two stacks
• Checking balanced expressions
• Evaluating postfix expressions

Time Complexity Summary