Introduction

Stacks are a fundamental data structure used extensively in algorithms and application design. The standard stack operations include `push` and `pop`, both providing efficient constant-time execution $O(1)$. However, additional operations like finding the minimum or maximum value in the stack often incur higher computational costs, potentially up to $O(n)$, where $n$ is the number of elements in the stack. This article explores techniques to enhance these operations to be more efficient than $O(n)$.

Fundamentals of Stack Operations

A stack is characterized by its Last-In-First-Out (LIFO) nature. Here's a quick recap on standard stack operations: • Push: Add an element to the top of the stack. • Pop: Remove the element from the top of the stack. • Peek: View the top element without removing it.

Extending Stack: Efficient Find-Min/Find-Max Operations

The naive approach to finding the minimum or maximum in a stack requires examining all elements, yielding a time complexity of $O(n)$. However, by augmenting the stack with additional data structures, you can achieve constant-time $O(1)$ for these operations.

Technique 1: Using an Auxiliary Stack

This approach involves maintaining an auxiliary stack alongside the primary stack. Each auxiliary stack helps track the running minimum or maximum.

• Find-Min using an Auxiliary Stack: • Push: When pushing an element onto the main stack, also push onto the auxiliary stack only if the auxiliary stack is empty or the current element is less than or equal to the top of the auxiliary stack. • Pop: When popping from the main stack, also pop from the auxiliary stack if the popped value is equal to the top of the auxiliary stack. • Get-Min: Simply return the top of the auxiliary stack.

• Find-Max: A similar process can be used, except in this case, you maintain the maximum on the auxiliary stack instead of the minimum.

• Push: Store a tuple with the item and the minimum (or maximum) seen so far. • Pop: Simply pop off the stacks. • Get-Min/Max: Return the min (or max) value stored in the top element of the tuple.

• The table illustrates that both the auxiliary stack and pair elements approaches offer $O(1)$ complexity for Min/Max operations compared to $O(n)$ for naive methods.