数据结构：顺序栈（Stack）详解

一、栈的定义

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端成为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO 结构。

栈的插入操作，叫做进栈，也称压栈，入栈。

栈的删除操作，叫做出栈，也叫做弹栈。

二、对栈的操作

由于栈本身就是一个线性表，那么我们上一章讨论的线性表的顺序存储和链式存储，对于栈来说同样适用。

InitStack (*s):初始化操作，建立一个空栈 s。

DestroyStack (*s) :若栈存在，则销毁它。

ClearStack（*s）：将栈清空。

StackEmpty（s）：若栈为空，返回 true，否则返回 false。

GetTop（s，*e）：若栈存在且非空，用 e 返回 s 的栈顶元素。

Push (*s,e) ：若栈存在，插入新元素 e 到 s 中并成为栈顶元素。

Pop（*s，*e）：删除 s 中的栈顶元素，并用 e 返回其值。

StackLength（s）：返回栈 s 的元素个数。

三、栈的顺序存储结构及实现

3.1、栈的顺序存储结构

栈的结构定义。

typedef int SElemType; //元素类型根据实际情况而定，这里假设为 int
//顺序栈结构
typedef struct{
    SElemType data[MAXSIZE];
    int top; //用于栈顶指针
}SqStack;

构造一个空栈 s。

Status InitStack(SqStack *s){
    s->data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType));
    s->top=-1;
    return OK;
}

把 s 置为空栈。

Status ClearStack(SqStack *s){
    s->top=-1;
    return OK;
}

//若栈为空栈，返回 true，否则返回 false
Status StackEmpty (SqStack s){
    if(s->top==-1){
        return true;
    }
    return false;
}

返回栈 s 的元素个数，即栈的长度

int StackLength(SqStack s){
    return s.top+1;
}

若栈不空，则用 e 返回 s 的栈顶元素，并返回 OK，否则返回 ERROR

Status GetTop(SqStack s,SElemType *e){
    if(s.top==-1){
        return ERROR;
    } else{
        *e=s.data[s->top];
        return OK;
    }
}

插入元素 e 为新的栈顶元素

Status Push(SqStack *s,SElemType e){
    if(s->top==MAXSIZE-1){ //栈满
        return ERROR;
    }
    s->top++; //栈顶指针加一
    s->data[s->top]=e; //将新插入元素赋值给栈顶空间
    return OK;
}

删除 s 的栈顶元素

//若栈不空，则删除 s 的栈顶元素，用 e 返回其值，并返回 OK，否则返回 ERROR
Status Pop(SqStack *s,SElemType *e){
    if(s->top==-1){
        return ERROR;
    }
    *e=s->data[s->top]; //将要删除的栈顶元素赋值给 e
    s->top--; //栈顶指针减一
    return OK;
}

遍历顺序栈

Status StackTraverse(SqStack s){
    int i=0;
    while(i<=s.top){
        visit(s.data[i++]);
    }
    printf("\n");
    return OK;
}

3.2、顺序栈的运用 代码示例

int main(){
    int j;
    SqStack s;
    int e;
    if(InitStack(&s)==OK){
        for(j=1;j<=10;j++){
            Push(&s,j);
        }
        printf("栈中元素依次为： ");
        StackTraverse(s);
        Pop(&s,&e);
        printf("弹出的元素 e=%d\n",e);
        printf("栈空否：%d(1 空 0 否)",StackEmpty(s));
        GetTop(s,&e);
        printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
        ClearStack(&s);
        printf("清空栈后，栈空否:%d(1 空 0 否)\n",StackEmpty(s));
    }
    return 0;
}

四、两栈共享空间

栈的顺序存储只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过有一个很大的缺陷就是：必须事先确定数组存储空间大小，非常麻烦。

对于两个相同类型的栈，我们可以用一个数组来存储，充分利用数组的内存空间。

我们的做法如下：让一个栈的栈底为数组的始端，即下标为 0 处，另一个栈为数组的末端，即下标为数组长度 n-1 处。这样，两个栈如果增加元素，就是两端点向中间延伸。

1. top1 和 top2 是栈 1 和栈 2 的栈顶指针。
2. 若栈 2 是空栈，栈 1 的 top1=n-1 时，就是栈 1 满了
3. 若栈 1 是空栈，栈 2 的 top2=0 时，就是栈 2 满了
4. 两个栈见面之时，也就是两个指针相差 1 时，即 top1+1=top2 为栈满

//两栈共享空间结构
typedef struct{
    SElemType data[MAXSIZE];
    int top1; //栈 1 栈顶指针
    int top2; //栈 2 栈顶指针
}SqDoubleStack;

Status visit(SElemType c){
    printf("%d",c);
    return OK;
}

构造一个空栈 s / 把 s 置为空栈

Status InitStack(SqDoubleStack *s){
    s->top1=-1;
    s->top2=MAXSIZE;
    return OK;
}

若 s 为空栈，返回 true，否则返回 false

Status StackEmptyStack(SqDoubleStack s){
    if(s.top1==-1&&s.top2==MAXSIZE){
        return true;
    } else{
        return false;
    }
}

返回 s 的元素个数，即栈的长度

int StackLength(SqDoubleStack s){
    return s.top1+1+(MAXSIZE-s.top2);
}

插入元素 e 为新的栈顶元素

Status Push(SqDoubleStack *s,SElemType e,int StackNumber){
    if(s->top1+1==s->top2){
        return ERROR; //栈已满，不能再 push 新元素了
    }
    if(StackNumber==1){ //栈 1 有元素进栈
        s->data[++s->top1]=e; //是栈 1 则先 top1+1 再给数组元素赋值
    } else if(StackNumber==2){ //栈 2 有元素进栈
        s->data[--s->top2]=e; //是栈 2 则先 top2-1 再给数组元素赋值
    }
    return OK;
}

删除 s 的栈顶元素，用 e 返回其值

Status Pop(SqDoubleStack *s,SElemType *e,int StackNumber){
    if(StackNumber==1){
        if(s->top1==-1){
            return ERROR; //说明栈 1 是空栈，溢出
        }
        *e=s->data[s->top1--]; //将栈 1 的栈顶元素出栈
    } else if(StackNumber==2){
        if(s->top2==MAXSIZE){
            return ERROR; //说明栈 2 是空栈，溢出
        }
        *e=s->data[s->top2++]; //将栈 2 的栈顶元素出栈
    }
    return OK;
}

遍历

Status StackTraverse(SqDoubleStack s){
    int i=0;
    while(i<=s.top1){
        visit(s.data[i++]);
    }
    i=s.top2;
    while(i<MAXSIZE){
        visit(s.data[i++]);
    }
    printf("\n");
    return OK;
}

小结：事实上，使用这样的数据结构，通常都是两个栈的空间需求有相反关系时，也就是一个栈在增长另一个栈在缩短的情况

参考资料：程杰：《大话数据结构》