设计包含min函数的栈

设计包含min函数的栈

定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。
要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。
代码思路：
1）push与pop操作不难，本题难点在与时间复杂度。
2）构造栈，和栈结点两个结构体。栈结点中设置一指针变量，说明当前节点时指向的最小元素。为了减少时间复杂度，增加空间复杂度是必要的。
C语言参考代码：
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
typedef int element;
typedef struct stacknode
{
element date;
struct stacknode *front;
struct stacknode *min;
}node;
typedef struct minstack
{
int size;
struct stacknode *top;
}mstack;
mstack *init()
{
mstack *S = (mstack *)malloc(sizeof(mstack));
S->top = NULL;
S->size = 0;
return S;
}
mstack *push(mstack *S,int value)
{
if (S->top == NULL)
{
S->top = (node *)malloc(sizeof(node));
S->top->date = value;
S->top->front = NULL;
S->top->min = S->top;
S->size = S->size + 1;
}
else
{
node *tmp = NULL;
tmp = S->top;
S->top = (node *)malloc(sizeof(node));
S->top->date = value;
S->top->front = tmp;
if (tmp->min->date > S->top->date)
{
S->top->min = S->top;
}
else
{
S->top->min = tmp->min;
}
S->size = S->size + 1;
}
return S;
}
mstack *pop(mstack *S)
{
if (S->top == NULL)
{
printf("栈已经为空，删除失败\n");
}
else
{
node *p;
p = S->top;
S->top = S->top->front;
free(p);
S->size = S->size - 1;
}
return S;
}
int Min(mstack *S)
{
return S->top->min->date;
}
mstack *delete(mstack *S)
{
while (S->top != NULL)
{
node *p = S->top;
S->top = S->top->front;
free(p);
S->size = S->size - 1;
}
free(S);
return S;
}
void main()
{
srand((unsigned)time(NULL));
mstack *S;
S = init();
for (int i = 0; i < 10; i++)
{
int num = rand() / 100;
printf("进栈：%d  ", num);
push(S, num);
}
printf("\n");
for (int i = 0; i < 10; i++)
{
printf("栈中最小元素：%d ", Min(S));
printf("出栈：%d\n", S->top->date);
pop(S);
}
system("pause");
}

本文永久更新链接地址：