Write a Python function to find the maximum element in a stack.
SamPetr
Posted by SamPetr
Last Updated: August 29, 2024
Python Stack
Finding the Maximum Element in a Stack Using Python
Stacks are often used in programming for their Last In, First Out (LIFO) nature. However, a common requirement is to not only perform standard operations like push and pop, but also efficiently retrieve the maximum element in the stack. Below is a Python implementation that achieves this using an auxiliary stack.
Implementation Details
The approach involves maintaining a secondary stack that keeps track of the maximum values. Each time an element is pushed onto the main stack, a comparison is made with the current maximum, which is then pushed onto the auxiliary stack. When popping an element, the corresponding maximum is also popped from the auxiliary stack to ensure we always have access to the current maximum. Here is the implementation: 
class Stack:
    def init(self):
        self.stack = []
        self.max_stack = []
    
    def push(self, value):
        # Push the value onto the main stack
        self.stack.append(value)
        
        # Push the new maximum onto the max stack
        if not self.max_stack or value >= self.max_stack[-1]:
            self.max_stack.append(value)
    
    def pop(self):
        if not self.stack:
            return None
        
        # Pop the value from the main stack
        value = self.stack.pop()
        
        # If the popped value is the current maximum, pop it from the max stack as well
        if value == self.max_stack[-1]:
            self.max_stack.pop()
        
        return value
    
    def get_max(self):
        if not self.max_stack:
            return None
        
        # The maximum value is at the top of the max stack
        return self.max_stack[-1]
    
    def is_empty(self):
        return len(self.stack) == 0

# Example Usage
if name == "main":
    stack = Stack()
    stack.push(3)
    stack.push(5)
    print(stack.get_max())  # Output: 5
    stack.push(2)
    stack.push(1)
    print(stack.get_max())  # Output: 5
    stack.pop()
    print(stack.get_max())  # Output: 5
    stack.pop()
    print(stack.get_max())  # Output: 5
    stack.pop()
    print(stack.get_max())  # Output: 3
    stack.pop()
    print(stack.get_max())  # Output: None
Explanation of Functions
- __init__: Initializes the main stack and the auxiliary max stack. - push(value): Adds an element to the main stack and updates the max stack if the new value is greater than or equal to the current maximum. - pop(): Removes the top element from the main stack and, if it is the current maximum, also removes it from the max stack. - get_max(): Returns the top element of the max stack, which represents the current maximum in the main stack. - is_empty(): Checks if the main stack is empty.
Performance
This implementation allows for O(1) time complexity for push, pop, and get_max operations, making it an efficient solution for maintaining the maximum element in a stack. With this structure, users can easily manage their stack while efficiently querying the maximum value at any point.
Default Image