包含min函数的栈
这道题的题目可以描述为:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数,在该栈中,调用min,push以及pop的时间复杂度都是O(1)。
本文有有关栈的结构体以及接口定义代码如下:
typedef int DataType;
#define MAXSIZE (100)
typedef struct{
DataType array[MAXSIZE];
int top;//起了个别名,含义还是size
}Stack;
void StackInit(Stack *ps)
{
ps->top = 0;
}
void StackDestory(Stack *ps)
{
ps->top = 0;
}
//栈中入放一个元素
void StackPush(Stack *ps, DataType data)
{
assert(ps->top < MAXSIZE);
ps->array[ps->top++] = data;
}
//栈中弹出一个元素
void StackPop(Stack *ps)
{
assert(ps->top>0);
ps->top--;
}
//弹出栈顶元素
DataType StackTop(const Stack *ps)
{
assert(ps->top > 0);
return ps->array[ps->top - 1];
}
//返回栈的大小
int StackSize(const Stack *ps)
{
return ps->top;
}
//返回栈是否为空
int StackEmpty(const Stack *ps)
{
return ps->top == 0 ? 1 : 0;
}
这道题的思路分为以下三步:
(1)首先定义一个大栈MinStack,其中又包含两个小栈m和s,其中s存放普通元素,m存放最小元素;
(2)入栈操作:每次同步进行,第一次压入data时,s一定压入data,当m栈为空时才压入data。从第二次开始,首先s压入data,当data<top(m)时才将data压入m) ;
(3)出栈操作:每次同步进行,data首先从s中弹出,当data==top(m)时,data才从m中弹出;
代码如下:
typedef struct{
Stack s;//普通的栈
Stack m;//存最小数据的栈
} MinStack;
void MinStackInit(MinStack *pms)
{
StackInit(&pms->m);
StackInit(&pms->s);
}
void MinStackDestory(MinStack *pms)
{
StackDestory(&pms->m);
StackDestory(&pms->s);
}
void MinStackPush(MinStack *pms, DataType data)
{
#if 0
StackPush(&pms->s, data);
if ((StackEmpty(&pms->m) || data < StackTop(&pms->m)))
StackPush(&pms->m, data);
else
StackPush(&pms->m, StackTop(&pms->m));
#endif
StackPush(&pms->s, data);
if ((StackEmpty(&pms->m) || data < StackTop(&pms->m)))
StackPush(&pms->m, data);
}
void MinStackPop(MinStack *pms)
{
#if 0
StackPop(&pms->s);
StackPop(&pms->m);
#endif
DataType data = StackTop(&pms->s);
StackPop(&pms->s);
if (data == StackTop(&pms->m))
{
StackPop(&pms->m);
}
}
DataType MinStackTop(MinStack *pms)
{
return StackTop(&pms->s);
}
DataType MinStackMin(MinStack *pms)
{
return StackTop(&pms->m);
}