一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。C语言
时间: 2024-10-09 12:06:35 浏览: 6
这种特殊的栈被称为带最小值栈(Min Stack)。它是一个数据结构,除了标准的压入(push)、弹出(pop)操作外,还支持在O(1)的时间复杂度内获取当前栈中的最小元素。这通常是通过额外维护一个指针,指向当前最小元素的位置来实现的。
在C语言中,可以这样做:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义 MinStack 结构体
typedef struct {
int *arr; // 数组用于存储元素
int top; // 栈顶指针
int min_top; // 最小值顶部指针
int size; // 当前大小
} MinStack;
// 初始化 MinStack
void init_MinStack(MinStack *stack) {
stack->arr = (int*)malloc(sizeof(int));
stack->top = -1;
stack->min_top = -1;
stack->size = 0;
}
// 向栈中压入元素
void push(MinStack *stack, int x) {
if (stack- 1) {
stack->size *= 2;
stack->arr = (int*)realloc(stack->arr, sizeof(int) * stack->size);
}
stack->arr[++stack->top] = x;
if (stack->min_top == -1 || x <= stack->arr[stack->min_top]) {
stack->min_top = stack->top;
}
}
// 弹出栈顶元素并返回最小值
int pop_and_min(MinStack *stack) {
if (stack->top == -1) {
return -1; // 空栈
}
int val = stack->arr[stack->top--];
if (val == stack->arr[stack->min_top]) {
stack->min_top--;
}
return val;
}
// 获取栈中的最小值
int getMin(MinStack *stack) {
if (stack->min_top == -1) {
return -1; // 空栈或从未插入过元素
}
return stack->arr[stack->min_top];
}
// 清空栈
void clear_MinStack(MinStack *stack) {
free(stack-1;
stack->size = 0;
}
// 示例
int main() {
MinStack s;
init_MinStack(&s);
push(&s, 5); // [5]
push(&s, 7); // [5, 7], min = 5
printf("getMin(): %d\n", getMin(&s)); // 输出 5
push(&s, 4); // [5, 7, 4], min = 4
printf("pop_and_min(): %d\n", pop_and_min(&s)); // 输出 4, min保持不变仍为4
clear_MinStack(&s);
return 0;
}
```