程序名：能查找栈中最小元素的栈
实现功能：
1、出栈、进栈、输出栈中最小元素的时间复杂度都是O(1);
2、新元素进栈之后，若小于原最小元素，则打印最小元素
改变信息；
#include
#include
#define datatype char
typedef struct
{
datatype Elem;
datatype Min;
}ElemType;
typedef struct
{
ElemType *StElem;
int size;
int top;
}Stack;
void Stack_Init(Stack &St , int StSize)
{
St.StElem = (ElemType *)malloc(sizeof(ElemType) * StSize);
St.top = -1;
St.size = StSize;
}
void Stack_Pop(Stack &St , datatype &E)
{
if(St.top == -1)
perror("The Stack is Empty , Pop Error !\n");
E = St.StElem[St.top].Elem;
St.top--;
printf("Pop Elem '%c' Succeed !\n",E);
}
void Stack_Push(Stack &St , datatype E)
{
if(St.top == St.size - 1)
perror("The Stack is Full , Push Error !\n");
St.top++;
St.StElem[St.top].Elem = E;
St.StElem[St.top].Min = (St.top == 0?E:St.StElem[St.top - 1].Min);
printf("Push New Elem '%c' into Stack Succeed !\n",E);
if(St.StElem[St.top].Min > E)
{
St.StElem[St.top].Min = E;
printf("The New Min Elem in the Stack is '%c'\n",E);
}
}
void Min_Find(Stack St , datatype &E)
{
if(St.top == -1)
perror("The Stack is Null , Error !\n");
E = St.StElem[St.top].Min;
}
void Stack_Free(Stack &St)
{
free(St.StElem);
St.StElem = NULL;
}
int main()
{
int sec;
datatype E;
Stack Stk;
Stack_Init(Stk,20);
Stack_Push(Stk,'A');
Stack_Push(Stk,'B');
Stack_Push(Stk,'8');
Stack_Push(Stk,'7');
Min_Find(Stk,E);
printf("The Min Elem in The Stack is '%c'\n",E);
Stack_Pop(Stk,E);
Min_Find(Stk,E);
printf("The Min Elem in The Stack is '%c'\n",E);
Stack_Pop(Stk,E);
Min_Find(Stk,E);
printf("The Min Elem in The Stack is '%c'\n",E);
return 0;
}
转载