設計包含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");
}