最小栈抽象数据类型（使用数组实现）
/*Name: 最小栈抽象数据类型（使用数组实现）
Copyright:
Author: 巧若拙
Date:13-09-14 18:28
Description: 最小栈除了能实现普通栈的操作外，还能以O(1)的时间复杂度返回和更新栈中的最小值。
算法说明：
Status Push(minStack *S, ElemType e);//在栈S中插入新元素e
其实存储到栈中的不是e的值，而是 e - S->min 的值，即 S->data[++S->top] = e - S->min;
如果S->data[S->top] < 0，即新入栈的e值比原来的min小，则更新min，即 S->min = e; 否则min不变。
Status Pop(minStack *S, ElemType *e);//删除栈S的栈顶元素，并将该元素值赋给e
与入栈操作对应，出栈操作也需要一些变化。
如果 S->data[S->top] > 0，则输出 S->data[S->top] + S->min;
否则输出 S->min;此种情况下由于最小值已经出栈了，必须更新min，即 S->min -= S->data[S->top];
其他操作的算法都很简单，就不一一解释了，需要注意的是输出所有元素时，一定要按照栈后进先出的特征进行输出，否则min得不到正确更新。
此外，我们还可以模仿最小栈的实现方法，去实现一个最大栈，基本思路是一样的，就是公式有所变化。
即入栈时，S->data[++S->top] = S->max - e; 若S->data[S->top] < 0， S->max = e;
出栈时，如果 S->data[S->top] > 0，则输出 S->max - S->data[S->top];
否则输出 S->max;并更新max，即 S->max += S->data[S->top];
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等
typedef struct minStack{
ElemType data[MAXSIZE];//数组存储栈元素
int top;//栈顶指针
ElemType min; //栈中的最小值
} minStack;
Status InitStack(minStack *S);//建立一个空的栈S
Status DisplayStack(minStack S);//输出栈S的所有元素
Status GetTop(minStack *S, ElemType *e);//用e返回栈S的栈顶元素
Status Push(minStack *S, ElemType e);//在栈S中插入新元素e
Status Pop(minStack *S, ElemType *e);//删除栈S的栈顶元素，并将该元素值赋给e
ElemType MinOfStack(minStack *S);//返回栈的最小值
int main(void)
{
minStack a;
ElemType *p, e = 0;
int i;
InitStack(&a);//建立一个空的栈
for (i=0; i<MAXSIZE; i++)
{
Push(&a, rand()%10+1);//在栈S中插入新元素e
}
DisplayStack(a);
printf("最小值： %d\n", MinOfStack(&a));
while (a.top >= 3)
{
Pop(&a, &e);//删除栈S的栈顶元素，并将该元素值赋给e
}
DisplayStack(a);
printf("最小值： %d\n", MinOfStack(&a));
return 0;
}
ElemType MinOfStack(minStack *S)//返回栈的最小值
{
return S->min;
}
Status InitStack(minStack *S)//建立一个空的栈S
{
S->top = -1;
return OK;
}
Status GetTop(minStack *S, ElemType *e)//用e返回栈S的栈顶元素
{
if (S->top == -1)
{
return ERROR;
}
if (S->data[S->top] > 0)
*e = S->data[S->top] + S->min;
else
*e = S->min;
return OK;
}
Status Push(minStack *S, ElemType e)//在栈S中插入新元素e
{
if (S->top == MAXSIZE - 1)
{
return ERROR;
}
if (S->top == -1)
{
S->min = e;
S->data[++S->top] = 0;
}
else
{
S->data[++S->top] = e - S->min;
if (S->data[S->top] < 0)
S->min = e;
}
return OK;
}
Status Pop(minStack *S, ElemType *e)//删除栈S的栈顶元素，并将该元素值赋给e
{
if (S->top == -1)
{
return ERROR;
}
if (S->data[S->top] > 0)
*e = S->data[S->top] + S->min;
else
{
*e = S->min;
S->min -= S->data[S->top];
}
S->top--;
return OK;
}
Status DisplayStack(minStack S)//输出栈S的所有元素
{
int i;
if (S.top == -1)
{
printf("none!\n");
return ERROR;
}
for (i=S.top; i>=0; i--)
{
if (S.data[i] > 0)
printf("data[%d] = %d\t", i, S.data[i] + S.min);
else
{
printf("data[%d] = %d\t", i, S.min);
S.min -= S.data[i];
}
}
printf("\n");
return OK;
}
[ 本帖最后由 巧若拙 于 2014-12-7 20:32 编辑 ]
