C 語言進階：設計支援 O(1) 取最小值的堆疊

編輯：關於C語言

題目要求

實作堆疊，支援 push、pop、min 三個操作，時間複雜度均為 O(1)。

核心洞見：輔助堆疊記錄歷史最小值

主堆疊正常存資料。輔助堆疊（minStack）僅在「新值 ≤ 當前最小值」時推入。因為堆疊是先進後出，當最小值被彈出時，輔助堆疊同步彈出，新堆頂即為下一個最小值。

演算法邏輯

push(x):
    main.push(x)
    if minStack.empty() or x <= minStack.top():
        minStack.push(x)

pop():
    if main.empty(): return
    x = main.pop()
    if x == minStack.top():
        minStack.pop()

min():
    return minStack.top()

C 語言完整實作（結構體封裝）

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

#define MAX_SIZE 1000

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void stack_init(Stack *s) { s->top = -1; }
bool stack_empty(const Stack *s) { return s->top == -1; }
bool stack_full(const Stack *s) { return s->top == MAX_SIZE - 1; }

bool stack_push(Stack *s, int x) {
    if (stack_full(s)) return false;
    s->data[++s->top] = x;
    return true;
}

bool stack_pop(Stack *s, int *out) {
    if (stack_empty(s)) return false;
    *out = s->data[s->top--];
    return true;
}

int stack_top(const Stack *s) { return s->data[s->top]; }

// --- MinStack 封裝 ---
typedef struct {
    Stack main;
    Stack min_stack;
} MinStack;

void minstack_init(MinStack *ms) {
    stack_init(&ms->main);
    stack_init(&ms->min_stack);
}

void minstack_push(MinStack *ms, int x) {
    stack_push(&ms->main, x);
    if (stack_empty(&ms->min_stack) || x <= stack_top(&ms->min_stack))
        stack_push(&ms->min_stack, x);
}

bool minstack_pop(MinStack *ms, int *out) {
    if (stack_empty(&ms->main)) return false;
    int x;
    stack_pop(&ms->main, &x);
    if (x == stack_top(&ms->min_stack))
        stack_pop(&ms->min_stack, out); // out 可忽略
    if (out) *out = x;
    return true;
}

int minstack_min(const MinStack *ms) {
    return stack_top(&ms->min_stack);
}

// --- 測試 ---
int main(void) {
    MinStack ms; minstack_init(&ms);
    int vals[] = {5, 2, 4, 1, 1, 3};
    for (int i = 0; i < 6; ++i) {
        minstack_push(&ms, vals[i]);
        printf("push %d, min=%d\n", vals[i], minstack_min(&ms));
    }
    printf("\nPop 過程:\n");
    int x;
    while (!stack_empty(&ms.main)) {
        minstack_pop(&ms, &x);
        printf("pop %d, min=%d\n", x, stack_empty(&ms.min_stack) ? -1 : minstack_min(&ms));
    }
    return 0;
}

執行結果

push 5, min=5
push 2, min=2
push 4, min=2
push 1, min=1
push 1, min=1
push 3, min=1

Pop 過程:
pop 3, min=1
pop 1, min=1
pop 1, min=2
pop 4, min=2
pop 2, min=5
pop 5, min=-1