This program implements a stack that supports the standard stack operations like push and pop, along with an additional feature to retrieve the minimum element in the stack in constant time. The key challenge is to design the stack in such a way that we can access the minimum element without traversing the entire stack after each push or pop.

Program Explanation

To solve this problem efficiently, we maintain two stacks:

• Main stack: Stores all the elements in the stack.
• Min stack: Tracks the minimum elements. Each time an element is pushed, if it is smaller than or equal to the current minimum, it is also pushed onto the min stack.

C Program Code

#include <stdio.h>
#include <stdlib.h>

#define MAX 100  // Define maximum size of the stack

// Stack structure
struct Stack {
    int arr[MAX];
    int top;
};

// Initialize the stack
void initStack(struct Stack *s) {
    s->top = -1;
}

// Check if the stack is empty
int isEmpty(struct Stack *s) {
    return s->top == -1;
}

// Check if the stack is full
int isFull(struct Stack *s) {
    return s->top == MAX - 1;
}

// Push an element onto the stack
void push(struct Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->arr[++(s->top)] = value;
}

// Pop an element from the stack
int pop(struct Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

// Peek the top element of the stack
int peek(struct Stack *s) {
    if (isEmpty(s)) {
        return -1;
    }
    return s->arr[s->top];
}

// Structure to maintain stack with minimum element support
struct MinStack {
    struct Stack mainStack;  // Main stack to store elements
    struct Stack minStack;   // Auxiliary stack to track minimum elements
};

// Initialize the MinStack
void initMinStack(struct MinStack *ms) {
    initStack(&ms->mainStack);
    initStack(&ms->minStack);
}

// Push an element onto the MinStack
void pushMin(struct MinStack *ms, int value) {
    push(&ms->mainStack, value);  // Push the element onto the main stack

    // If the minStack is empty or the new value is less than or equal to the current minimum, push it onto the minStack
    if (isEmpty(&ms->minStack) || value <= peek(&ms->minStack)) {
        push(&ms->minStack, value);
    }

    printf("Pushed %d, Minimum: %d\n", value, peek(&ms->minStack));
}

// Pop an element from the MinStack
int popMin(struct MinStack *ms) {
    int poppedValue = pop(&ms->mainStack);

    // If the popped element is the current minimum, pop it from the minStack as well
    if (poppedValue == peek(&ms->minStack)) {
        pop(&ms->minStack);
    }

    if (!isEmpty(&ms->minStack)) {
        printf("Popped %d, New Minimum: %d\n", poppedValue, peek(&ms->minStack));
    } else {
        printf("Popped %d, Stack is now empty\n", poppedValue);
    }

    return poppedValue;
}

// Retrieve the minimum element from the MinStack
int getMin(struct MinStack *ms) {
    if (isEmpty(&ms->minStack)) {
        printf("Stack is empty, no minimum\n");
        return -1;
    }

    return peek(&ms->minStack);
}

// Main driver function
int main() {
    struct MinStack ms;
    initMinStack(&ms);

    pushMin(&ms, 10);  // Push 10
    pushMin(&ms, 20);  // Push 20
    pushMin(&ms, 5);   // Push 5 (new minimum)
    pushMin(&ms, 30);  // Push 30
    pushMin(&ms, 2);   // Push 2 (new minimum)

    printf("Current minimum: %d\n", getMin(&ms));  // Retrieve the minimum element

    popMin(&ms);  // Pop top element (2)
    popMin(&ms);  // Pop top element (30)
    
    printf("Current minimum: %d\n", getMin(&ms));  // Retrieve the minimum element after popping
    
    popMin(&ms);  // Pop top element (5, which was the minimum)

    printf("Current minimum: %d\n", getMin(&ms));  // Retrieve the minimum element after popping

    return 0;
}
    

Code Explanation

1. Stack Structure: The stack is represented using an array of fixed size MAX, and an integer top keeps track of the index of the top element in the stack. Basic operations like push(), pop(), and peek() are implemented to handle stack operations.

2. MinStack Structure: The MinStack structure maintains two stacks: one is the main stack (mainStack), and the other is the minStack, which tracks the minimum elements.

3. Push Operation: The pushMin() function pushes elements onto the main stack and updates the minStack if the pushed element is smaller than or equal to the current minimum.

4. Pop Operation: The popMin() function pops elements from both the main stack and the minStack if the popped element is the current minimum.

5. Get Minimum: The getMin() function retrieves the current minimum element from the minStack.

Sample Output

Pushed 10, Minimum: 10
Pushed 20, Minimum: 10
Pushed 5, Minimum: 5
Pushed 30, Minimum: 5
Pushed 2, Minimum: 2
Current minimum: 2
Popped 2, New Minimum: 5
Popped 30, New Minimum: 5
Current minimum: 5
Popped 5, New Minimum: 10
Current minimum: 10
    

Conclusion

This C program demonstrates how to implement a stack that supports standard stack operations like push and pop, while also allowing efficient retrieval of the minimum element in constant time. By maintaining an auxiliary stack that tracks the minimum elements, we ensure that the getMin() operation runs in O(1) time.