c - 堆栈中的最小值

Question

我正在尝试获取堆栈中的最小值，其中 StackMin、Pop 和 Push 都是Θ(1). 我的代码不起作用......这是我的尝试：

typedef struct{
    int top;
    int entry[1000];
    int small;
} Stack;

void Pop(int *e,Stack *ps){
    *e=ps->entry[--ps->top];
}

void Push(int e,Stack *ps){
    ps->entry[ps->top++]=e;
}

int StackMin(Stack *ps){
    ps->small=ps->entry[ps->top];
    while(!StackEmpty(ps)){
        int *e;
        *e=ps->entry[--ps->top];
        if(ps->small >= *e){
            ps->small = *e;
        }
    }
    return ps->small;
}

Answer 1

这些行中不需要指针：

int *e; 
*e=ps->entry[--ps->top]; 
if(ps->small >= *e){ 
    ps->small = *e; 
} 

将它们更改为：

int e = ps->entry[--ps->top]; 
if(ps->small >= e){ 
    ps->small = e; 
} 

Answer 2

您需要有两个堆栈才能执行此操作。一个堆栈的顺序可以有最小值，每次调用最小值时都会更新此堆栈。尝试自己找出算法。

Answer 3

“不起作用”的描述不是那么有用......但无论如何，这看起来有问题：

int *e;
*e=ps->entry[--ps->top];
if(ps->small >= *e){
    ps->small = *e;
}

问题是，您已经声明了一个指针（它目前没有指向任何东西 - 它未初始化），然后您将一个值写入它指向的（无效）位置。

如果碰巧代码没有崩溃，而您的问题是关于算法的，那么另一个用户已经发布了一个答案。