This program demonstrates a stack that supports not only push and pop operations but also retrieving the minimum element in constant time. The structure of this specialized stack includes an auxiliary stack that keeps track of the minimum values.

Program Structure

The stack is implemented using two lists:

• The main stack that holds all the elements.
• An auxiliary stack that holds the minimums.

Each time an element is added, the program checks if it should update the current minimum. Every time an element is removed, it also updates the minimum by popping from the auxiliary stack if necessary.

Python Code

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

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        x = self.stack.pop()
        if x == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self):
        return self.stack[-1]

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

# Example Usage
min_stack = MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
print("Minimum element:", min_stack.getMin())  # Returns -3
min_stack.pop()
print("Top element:", min_stack.top())         # Returns 0
print("Minimum element:", min_stack.getMin())  # Returns -2

Explanation of the Code

• __init__: Initializes two stacks; one for all elements and another for the minimums.
• push: Adds an element to the main stack and, if it’s smaller than or equal to the current minimum, also pushes it onto the min stack.
• pop: Removes the top element from the main stack and, if it’s the current minimum, also pops from the min stack.
• top: Returns the top element of the main stack without removing it.
• getMin: Returns the current minimum element, which is the top of the min stack.

Usage

This min stack can be used in scenarios where it’s crucial to frequently retrieve the minimum element of a stack efficiently, such as in algorithm optimizations, data stream processing, and more.