要实现栈的基本操作,并且在O(1)的时间复杂度内获取栈中最小元素,可以借助辅助栈来实现。
首先,我们创建两个栈:原始栈和辅助栈。原始栈用于存储所有的元素,辅助栈用于存储当前最小元素。
在插入元素时:
- 将元素同时压入原始栈和辅助栈。
- 如果插入的元素小于等于辅助栈顶部元素,则将该元素也压入辅助栈。否则,不进行任何操作。
在删除元素时:
- 从原始栈弹出一个元素。
- 如果该元素等于辅助栈顶部的元素,则同时从辅助栈中弹出一个元素。
这样,每次操作后,辅助栈的顶部元素就是当前最小值。
以下是C语言代码示例:
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
typedef struct Node {
int value;
struct Node* next;
} Node;
// 定义堆栈结构
typedef struct Stack {
Node* top;
} Stack;
// 初始化堆栈
void initStack(Stack* stack) {
stack->top = NULL;
}
// 压入堆栈
void push(Stack* stack, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = value;
// 将节点插入堆栈顶部
newNode->next = stack->top;
stack->top = newNode;
}
// 弹出堆栈
int pop(Stack* stack) {
if (stack->top == NULL) {
printf("Stack is empty.\n");
return -1; // 返回一个非法值作为错误标志
}
Node* topNode = stack->top;
int value = topNode->value;
// 更新堆栈顶部指针并释放节点内存
stack->top = topNode->next;
free(topNode);
return value;
}
// 获取栈中最小元素(O(1)复杂度)
int getMin(Stack* stack) {
if (stack->top == NULL) {
printf("Stack is empty.\n");
return -1; // 返回一个非法值作为错误标志
}
return stack->top->value; // 辅助栈的顶部元素即为当前最小值
}
int main() {
Stack originalStack, auxiliaryStack;
// 初始化两个栈
initStack(&originalStack);
initStack(&auxiliaryStack);
// 向原始栈中压入一些元素(示例)
push(&originalStack, 5);
push(&originalStack, 2);
push(&originalStack, 7);
push(&originalStack, 4);
// 遍历原始栈,将辅助栈更新为当前最小值的序列
Node* currentNode = originalStack.top;
while (currentNode != NULL) {
int value = currentNode->value;
// 如果当前值小于等于辅助栈顶部的值,则将其压入辅助栈
if (auxiliaryStack.top == NULL || value <= auxiliaryStack.top->value) {
push(&auxiliaryStack, value);
}
currentNode = currentNode->next;
}
// 打印栈中最小元素
printf("The minimum element in the stack is: %d\n", getMin(&auxiliaryStack));
return 0;
}
这个示例代码展示了如何通过辅助栈实现获取栈中最小元素的操作,并保证了O(1)的时间复杂度。你可以根据需要自定义其他栈操作和测试样例。
内容由零声教学AI助手提供,问题来源于学员提问