/*
    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 编辑 ]