实现一个特殊的栈返回栈中最小元素,c语言
时间: 2024-10-18 13:17:12 浏览: 2
要实现一个特殊的栈,返回栈中最小元素,可以使用两个栈来实现。第一个栈用来保存当前栈中的元素,第二个栈用来保存每一步的最小值。具体实现方法如下:
1. 定义两个栈,一个是data栈,一个是min栈。
2. push操作:将元素压入data栈中,然后判断min栈是否为空。如果为空,则将该元素也压入min栈中;如果不为空,则比较该元素和min栈顶元素哪一个更小。如果该元素更小或者二者相等,则将该元素也压入min栈中;如果min栈顶元素更小,则不将该元素压入min栈中。
3. pop操作:从data栈中弹出元素,并判断该元素是否为min栈顶元素。如果是,则也从min栈中弹出该元素。
4. getMin操作:直接返回min栈顶元素即可。
下面是C语言的代码实现:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int top;
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
int isEmpty(Stack *s) {
return s->top == -1;
}
int isFull(Stack *s) {
return s->top == MAXSIZE - 1;
}
void push(Stack *s, int x) {
if (isFull(s)) {
printf("Stack is full.\n");
exit(1);
}
s->data[++s->top] = x;
}
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top--];
}
int getTop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top];
}
typedef struct {
Stack dataStack;
Stack minStack;
} MinStack;
void initMinStack(MinStack *s) {
initStack(&s->dataStack);
initStack(&s->minStack);
}
void pushMin(MinStack *s, int x) {
push(&s->dataStack, x);
if (isEmpty(&s->minStack) || x <= getTop(&s->minStack)) {
push(&s->minStack, x);
}
}
int popMin(MinStack *s) {
int x = pop(&s->dataStack);
if (x == getTop(&s->minStack)) {
pop(&s->minStack);
}
return x;
}
int getMin(MinStack *s) {
return getTop(&s->minStack);
}
int main() {
MinStack s;
initMinStack(&s);
pushMin(&s, 3);
pushMin(&s, 2);
pushMin(&s, 5);
pushMin(&s, 1);
printf("Min element: %d\n", getMin(&s));
popMin(&s);
printf("Min element: %d\n", getMin(&s));
return 0;
}
```
阅读全文