Implement Min Stack Using Stack and Queue: Efficient Algorithm Explained

The Min Stack is an advanced stack variation that supports retrieving the minimum element in constant time O(1) while maintaining standard stack operations (push, pop, and top). This is crucial in applications where efficient minimum retrieval is required.

In this blog, we will explore:
✅ What is a Min Stack?
✅ How to implement a Min Stack using Stack and Queue
✅ Efficient algorithm for O(1) minimum retrieval
✅ Python implementation with step-by-step code
✅ Real-world applications and FAQs

By the end, you’ll have a solid understanding of how to design and implement a Min Stack using Stack and Queue efficiently.

What is a Min Stack?

A Min Stack is a modified stack that allows:

• Push(x): Inserts an element into the stack.
• Pop(): Removes the top element from the stack.
• Top(): Retrieves the top element without removing it.
• GetMin(): Retrieves the minimum element in the stack in O(1) time.

Also Read: Top Free SQL Download Options for Developers

Example of Min Stack Operations

Operation	Stack	Min Stack
Push(5)	[5]	[5]
Push(3)	[5,3]	[5,3]
Push(7)	[5,3,7]	[5,3,3]
Pop()	[5,3]	[5,3]
GetMin()	3	3

---

Why Use Stack and Queue for Min Stack?

Using Stack and Queue, we can efficiently implement a Min Stack:

Stack Approach for Min Stack

🔹 Uses two stacks (one for values, one for minimums).
🔹 Push operation inserts the minimum value at that point.
🔹 Pop operation removes both value and corresponding minimum.

Queue Approach for Min Stack

🔹 Maintains minimums in a queue for O(1) retrieval.
🔹 Uses monotonic queues to store the minimum values dynamically.

Also Read: DevOps vs Software Engineer: Key Differences, Skills, and Career Insights

Min Stack Implementation Using Two Stacks

A two-stack approach maintains a main stack (stack) and a min stack (min_stack).

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):
        if self.stack:
            if self.stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            return self.stack.pop()

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

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

# Example Usage
min_stack = MinStack()
min_stack.push(5)
min_stack.push(3)
min_stack.push(7)
print(min_stack.getMin())  # Output: 3
min_stack.pop()
print(min_stack.getMin())  # Output: 3

🔹 Time Complexity: O(1) for push, pop, and getMin operations.
🔹 Space Complexity: O(n), as an extra stack is used.

Min Stack Implementation Using Queue

A monotonic queue ensures we always retrieve the minimum in O(1) time.

from collections import deque

class MinQueue:
    def __init__(self):
        self.queue = deque()
        self.min_queue = deque()

    def enqueue(self, x):
        self.queue.append(x)
        while self.min_queue and self.min_queue[-1] > x:
            self.min_queue.pop()
        self.min_queue.append(x)

    def dequeue(self):
        if self.queue:
            if self.queue[0] == self.min_queue[0]:
                self.min_queue.popleft()
            return self.queue.popleft()
        return None

    def getMin(self):
        return self.min_queue[0] if self.min_queue else None

# Example Usage
min_queue = MinQueue()
min_queue.enqueue(5)
min_queue.enqueue(3)
min_queue.enqueue(7)
print(min_queue.getMin())  # Output: 3
min_queue.dequeue()
print(min_queue.getMin())  # Output: 3

🔹 Time Complexity: O(1) for enqueue, dequeue, and getMin operations.
🔹 Space Complexity: O(n), as two queues are used.

Also Read: 2 Simple Approaches to Circular Linked List Splitting

Stack vs Queue for Min Stack

Feature	Stack Approach	Queue Approach
Data Structure Used	Two Stacks	Monotonic Queue
Space Complexity	O(n)	O(n)
Min Retrieval Time	O(1)	O(1)
Best For	Sequential Processing	Sliding Window Minimum

Stack is better for maintaining a LIFO structure, whereas Queue is useful for real-time processing.

Real-World Applications of Min Stack

✅ Stock Price Monitoring – Track the minimum stock price over time.
✅ Temperature Analysis – Find the coldest temperature in a dataset.
✅ Competitive Programming – Optimized solution for LeetCode, CodeChef, and HackerRank.
✅ Memory Allocation – Manage memory efficiently in OS design.
✅ Sliding Window Minimum – Used in real-time analytics and finance.

Common Mistakes and How to Avoid Them

❌ Forgetting to maintain min_stack – Always push values into both stacks.
❌ Not checking for empty stack before popping – Use if conditions before popping.
❌ Using a single stack for min tracking – This will not work efficiently.
❌ Ignoring duplicate minimum values – Ensure all minimums are stored.

FAQs

Conclusion

The Min Stack is an essential data structure that efficiently retrieves the minimum value in a stack in O(1) time. Using Stack and Queue, we can implement an optimized Min Stack suitable for real-world applications.

🚀 Key Takeaways:
✅ Use a secondary min stack for fast retrieval.
✅ Monotonic queues provide an alternative approach.
✅ Time Complexity is O(1) for all operations.
✅ Applications in finance, scheduling, and data analysis.

Start implementing your Min Stack today and optimize your coding performance!