设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。\n\npush(x) —— 将元素 x 推入栈中。\npop() —— 删除栈顶的元素。\ntop() —— 获取栈顶元素。\ngetMin() —— 检索栈中的最小元素。C语言设计

为了设计一个支持上述操作并且能在常数时间内检索最小元素的栈，我们可以采用一种叫做“双端队列”（Deque，即Double Ended Queue）的数据结构，同时维护一个指向当前最小元素的指针。这里我们可以使用C语言的`struct`来实现这个数据结构：

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

// 定义 MinStack 结构体
typedef struct {
    int* elements; // 栈数组
    size_t top;     // 栈顶元素下标
    int min_index;  // 最小值的下标
    size_t size;    // 存储容量
} MinStack;

// 初始化堆栈，分配内存空间
void init(MinStack* stack, size_t capacity) {
    stack->elements = malloc(capacity * sizeof(int));
    stack->top = -1;
    stack->min_index = -1;
    stack->size = capacity;
}

// 向堆栈顶部推入元素x
void push(MinStack* stack, int x) {
    if (stack->top == stack->size - 1) {
        printf("Stack is full.\n");
        return;
    }
    
    stack->top++;
    stack->elements[stack->top] = x;
    
    // 如果这是第一个元素或新元素比当前最小值还小，则更新最小值
    if (stack->min_index == -1 || x <= stack->elements[stack->min_index]) {
        stack->min_index = stack->top;
    }
}

// 从堆栈顶部弹出并返回元素
int pop(MinStack* stack) {
    if (stack->top == -1) {
        printf("Stack is empty.\n");
        return -1;
    }

    int x = stack->elements[stack->top];
    stack->top--;

    // 如果删除的是最小元素，更新最小值指针
    if (stack->top == stack->min_index) {
        stack->min_index = stack->elements[stack->min_index] > stack->elements[stack->top + 1] ? stack->top : stack->top + 1;
    }

    return x;
}

// 返回堆栈顶部元素
int top(MinStack* stack) {
    if (stack->top == -1) {
        printf("Stack is empty.\n");
        return -1;
    }
    return stack->elements[stack->top];
}

// 返回堆栈中的最小元素
int getMin(MinStack* stack) {
    if (stack->min_index == -1) {
        printf("Stack is empty or all elements are equal.\n");
        return -1;
    }
    return stack->elements[stack->min_index];
}

// 清理堆栈释放内存
void destroy(MinStack* stack) {
    free(stack->elements);
    stack->elements = NULL;
    stack->top = -1;
    stack->min_index = -1;
    stack->size = 0;
}

int main() {
    MinStack s;
    init(&s, 5); // 初始化一个大小为5的堆栈

    // 使用堆栈和获取最小元素示例
    push(&s, 4);
    push(&s, 2);
    push(&s, 1);
    printf("Top element: %d, Minimum: %d\n", top(&s), getMin(&s)); // 输出: Top element: 1, Minimum: 1
    
    pop(&s);
    printf("After pop: Top element: %d, Minimum: %d\n", top(&s), getMin(&s)); // 输出: After pop: Top element: 2, Minimum: 1

    destroy(&s);
    return 0;
}

这个实现允许在常数时间内完成`push`、`pop`、`top`和`getMin`操作，因为查找最小值只需要访问栈顶指针`stack->min_index`即可。当`pop`操作移除最小元素时，我们只需检查下一个元素是否成为新的最小值即可更新`min_index`。