Write a Python function to find the minimum element in a stack.
EveClark
Posted by EveClark
Last Updated: August 08, 2024
Python Stack
## Finding the Minimum Element in a Stack In Python, a stack can be represented using a list. To efficiently find the minimum element in a stack, it is beneficial to maintain an auxiliary stack that tracks the minimum values. This allows the minimum element to be accessed in constant time. Below is a Python function that implements a stack with the capability to return the minimum element.
Implementation
class MinStack:
    def init(self):
        self.stack = []          # Main stack to store elements
        self.min_stack = []      # Auxiliary stack to store minimums

    def push(self, value):
        self.stack.append(value)  # Push the value onto the main stack
        # Push onto min_stack if it is empty or the new value is less than or equal to the current minimum
        if not self.min_stack or value <= self.min_stack[-1]:
            self.min_stack.append(value)

    def pop(self):
        if not self.stack:
            raise IndexError("pop from empty stack")
        value = self.stack.pop()  # Pop the value from the main stack
        if value == self.min_stack[-1]:  # Check if it is the minimum
            self.min_stack.pop()  # Remove it from the min_stack as well
        return value

    def top(self):
        if not self.stack:
            raise IndexError("top from empty stack")
        return self.stack[-1]  # Return the top value of the main stack

    def get_min(self):
        if not self.min_stack:
            raise IndexError("get_min from empty stack")
        return self.min_stack[-1]  # Return the current minimum
Explanation
1. Class Initialization: - The class MinStack initializes two lists: stack for storing the actual stack elements and min_stack for tracking the minimum values. 2. Push Operation: - The push method adds a new value to the main stack. It also checks if the new value is less than or equal to the current minimum (the top of min_stack). If so, the new value is also pushed onto min_stack. 3. Pop Operation: - The pop method removes the top value from the main stack. If this value equals the current minimum (the top of min_stack), it is also removed from min_stack. 4. Top Operation: - The top method returns the most recently added item in the main stack without removing it. 5. Get Minimum Operation: - The get_min method provides the current minimum value in constant time by returning the top of the min_stack.
Usage
Here is how you can use the MinStack class: 
my_stack = MinStack()
my_stack.push(3)
my_stack.push(5)
print(my_stack.get_min())  # Output: 3
my_stack.push(2)
my_stack.push(1)
print(my_stack.get_min())  # Output: 1
my_stack.pop()
print(my_stack.get_min())  # Output: 2
my_stack.pop()
print(my_stack.top())       # Output: 5
print(my_stack.get_min())   # Output: 3
Conclusion
The MinStack class efficiently supports basic stack operations while enabling quick retrieval of the minimum element at any time. The use of an auxiliary stack ensures that both push and pop operations maintain O(1) time complexity, making it suitable for various applications where a minimum value is frequently required.
Default Image