Min Stack - C Solution

1. Introduction

This blog post delves into a classic problem in data structures using C programming: designing a 'Min Stack' that supports push, pop, top, and retrieving the minimum element operations in constant time. This problem is a great exercise in understanding stack data structure and optimizing for specific operations.

Problem

The task is to implement a MinStack class that supports the following operations with O(1) time complexity:

- MinStack(): Initializes the stack object.

- void push(int val): Pushes the element val onto the stack.

- void pop(): Removes the element on the top of the stack.

- int top(): Gets the top element of the stack.

- int getMin(): Retrieves the minimum element in the stack.

2. Solution Steps

1. Use two stacks: one to store all elements and another to store the minimum elements.

2. For each push operation, add the element to the main stack and update the minimum stack.

3. For pop operations, pop from both stacks if the top elements are the same.

4. Implement top and getMin to return the top elements from the respective stacks.

3. Code Program

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000

// MinStack structure definition
typedef struct {
    int data[MAX_SIZE];    // Stack to store all elements
    int minData[MAX_SIZE]; // Stack to store minimum elements
    int top;               // Top pointer for the main stack
    int minTop;            // Top pointer for the minimum stack
} MinStack;

// Function to initialize the MinStack
MinStack* minStackCreate() {
    MinStack* stack = (MinStack*)malloc(sizeof(MinStack));
    stack->top = -1;
    stack->minTop = -1;
    return stack;
}

// Function to push an element onto the stack
void minStackPush(MinStack* obj, int val) {
    obj->data[++(obj->top)] = val; // Push element onto the main stack
    // Push element onto the minimum stack if it's smaller than the current minimum
    if (obj->minTop == -1 || val <= obj->minData[obj->minTop]) {
        obj->minData[++(obj->minTop)] = val;
    }
}

// Function to pop an element from the stack
void minStackPop(MinStack* obj) {
    if (obj->top != -1) {
        // Pop from minimum stack if the top elements are the same
        if (obj->data[obj->top] == obj->minData[obj->minTop]) {
            obj->minTop--;
        }
        obj->top--; // Pop from the main stack
    }
}

// Function to get the top element of the stack
int minStackTop(MinStack* obj) {
    return obj->data[obj->top];
}

// Function to retrieve the minimum element from the stack
int minStackGetMin(MinStack* obj) {
    return obj->minData[obj->minTop];
}

// Function to free the MinStack
void minStackFree(MinStack* obj) {
    free(obj);
}

// Main function to demonstrate MinStack operations
int main() {
    MinStack* minStack = minStackCreate();
    minStackPush(minStack, -2);
    minStackPush(minStack, 0);
    minStackPush(minStack, -3);
    printf("Min: %d\n", minStackGetMin(minStack)); // getMin() -> return -3
    minStackPop(minStack);
    printf("Top: %d\n", minStackTop(minStack));    // top() -> return 0
    printf("Min: %d\n", minStackGetMin(minStack)); // getMin() -> return -2
    minStackFree(minStack);

    return 0;
}

Output:

Min: -3
Top: 0
Min: -2

Explanation:

The program implements a MinStack, supporting operations in O(1) time. The stack maintains two arrays: one for storing all the elements (data) and another for storing the minimum elements (minData).

 The push method adds elements to both stacks, ensuring minData always contains the current minimum. 

The pop method removes elements from both stacks if they are equal. 

The getMin method retrieves the top element of the minData stack, which is the current minimum. 

In the example, after pushing -2, 0, and -3, the minimum is -3. 

After popping, the top element is 0 and the minimum is -2, demonstrating the stack's functionality.