Min Stack Design in DSA C - Build from Scratch

Min Stack Design

📖 Scenario: Imagine you are building a special stack for a calculator app. This stack not only stores numbers but also quickly tells you the smallest number currently in the stack. This helps the app show the minimum value instantly without searching every time.

🎯 Goal: Build a MinStack in C that supports push, pop, top, and getMin operations all in constant time.

📋 What You'll Learn

Create a struct called MinStack with two integer arrays: stack and minStack, and an integer top for the current index.

Add a variable maxSize to set the maximum size of the stack.

Implement push to add a number to stack and update minStack with the current minimum.

Implement pop to remove the top element from both stack and minStack.

Implement top to return the top element of stack.

Implement getMin to return the current minimum from minStack.

Print the results of top and getMin after operations.

💡 Why This Matters

🌍 Real World

Min stacks are used in calculators, stock price trackers, and algorithms that need quick access to minimum values.

💼 Career

Understanding min stack design helps in coding interviews and building efficient data structures for real-time applications.

1

Create the MinStack struct

Create a struct called MinStack with three members: an integer array stack of size 100, an integer array minStack of size 100, and an integer top initialized to -1.

DSA C

struct MinStack {
    // Your code here
};

Hint

Think of stack as the main stack and minStack as a helper stack to keep track of minimum values.

2

Initialize the MinStack

Write a function void initMinStack(struct MinStack *s) that sets s->top to -1 to initialize the stack as empty.

DSA C

struct MinStack {
    int stack[100];
    int minStack[100];
    int top;
};

// Your code here

Hint

Setting top to -1 means the stack is empty.

3

Implement push operation

Write a function void push(struct MinStack *s, int x) that increases s->top by 1, stores x in s->stack[s->top], and updates s->minStack[s->top] with the minimum between x and the previous minimum (or x if stack was empty).

DSA C

struct MinStack {
    int stack[100];
    int minStack[100];
    int top;
};

void initMinStack(struct MinStack *s) {
    s->top = -1;
}

// Your code here

Hint

Remember to update minStack with the smaller value between the new element and the current minimum.

4

Implement pop, top, getMin and print results

Write functions void pop(struct MinStack *s) to decrease s->top, int top(struct MinStack *s) to return s->stack[s->top], and int getMin(struct MinStack *s) to return s->minStack[s->top]. Then create a main function that initializes a MinStack, pushes 3, 5, 2, 1, pops once, and prints the results of top and getMin after each operation as shown.

DSA C

struct MinStack {
    int stack[100];
    int minStack[100];
    int top;
};

void initMinStack(struct MinStack *s) {
    s->top = -1;
}

void push(struct MinStack *s, int x) {
    s->top++;
    s->stack[s->top] = x;
    if (s->top == 0) {
        s->minStack[s->top] = x;
    } else {
        int prevMin = s->minStack[s->top - 1];
        s->minStack[s->top] = (x < prevMin) ? x : prevMin;
    }
}

// Your code here

Hint

Use pop to remove the top element and then print the current top and minimum values.