@[toc]

本篇将讲述栈的相关知识

在之前的文章中我们学习了线性表，大家一定要掌握线性表的相关知识，这是后面内容的基础。

栈的定义

先来看看栈的定义：

栈是限定仅在表尾进行插入和删除操作的线性表。表尾一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈；从一个栈删除元素又称作出栈或退栈。

由定义可以得知，栈本质就是一个线性表，只不过栈只能在表尾进行插入和删除操作，是操作受限的线性表。
因为只能在表尾进行插入和删除，所以栈中的元素是先进后出的，也就是说，最先进栈的元素最后才出栈。

可以将栈的结构类比成子弹夹，最先压入的子弹在最底下。

下图为元素的进栈过程：
在这里插入图片描述
下图为元素的出栈过程：

对于入栈和出栈的理解一定要透彻，比如现在有三个元素1，2，3，其入栈顺序为1，2，3，则出栈顺序是怎样的呢？有以下几种情况：

让1先入栈，然后2入栈，最后3入栈；出栈顺序为：3，2，1
让1先入栈，1出栈，然后2入栈，2出栈，最后3入栈，3出栈；出栈顺序为：1，2，3
让1先入栈，然后2入栈，2出栈，1出栈，最后3入栈，3出栈；出栈顺序为：2，1，3
让1先入栈，然后2入栈，2出栈，最后3入栈，3出栈，1出栈；出栈顺序为：2，3，1
让1先入栈，1出栈，然后2入栈，最后3入栈，3出栈，2出栈；出栈顺序为：1，3，2

元素的入栈和出栈顺序比较灵活，大家可以自己画图理解一下。

栈的抽象数据类型定义

这个大家都有基础了，我直接贴出来就可以了。

ADT Stack{
   
   
    数据对象：D = {
   
   ai|ai∈ElemSet,i = 1,2,3,...,n-1,n,n>=0}
    数据关系：R1={
   
   <ai-1,ai>|ai-1,ai∈D,i=2,3,...,n-1,n}
    基本操作:
        InitStack();//初始化栈
        Push(int val);//入栈
        Pop(int *val);//出栈
        DestroyStack(&s);//销毁栈
        StackEmpty(s);//判断栈是否为空
        StackLength(s);//求栈的长度
        GetTop(s,&val);//获取栈顶元素
        ClearStack(&s);//清空栈
        ......
}ADT Stack

栈的顺序实现

对于栈的顺序存储，我们依然通过数组实现。
通过设置两个指针，一个top指针指示栈顶元素的位置；一个base指针指示栈底元素的位置。
不过为了操作方便，通常top指针指示的并不是栈顶元素的位置，而是栈顶元素之上的一个位置，如下图：
在这里插入图片描述
当top指向base，即：top == base的时候，表示栈为空。
而为了判断栈满的情况，我们设置一个stacksize，它表示栈的最大容量。倘若top - base`== stacksize，表示栈已满。

下面是对栈的结构定义：

#define Elemtype int

typedef struct{
   
   
    ElemType *top;    //栈顶指针
    ElemType *base;    //栈底指针
    int stacksize;    //栈的最大容量
}Stack,*PStack;

顺序栈的基本操作

下面介绍顺序栈的一些基本操作。

顺序栈的初始化

如何对顺序栈进行初始化呢？直接看代码：

void InitStack(PStack s){
   
   
    //分配一段内存
    s->base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    if(s->base == NULL){
   
   
        exit(-1);
    }
    //初始栈顶指针等于栈底指针
    s->top = s->base;
    s->stacksize = MAXSIZE;//最大容量
}

判断顺序栈是否为空

在顺序栈的定义中，我们就说道，如果知道一个顺序栈是否为空，判断栈顶指针的指向和栈底指针的指向是否相同，即：top == base，若条件成立，则表示顺序栈为空。
代码如下：

int StackEmpty(Stack s){
   
   
    if(s.top == s.base){
   
   
        return 1;
    }else{
   
   
        return 0;
    }
}

求顺序栈的长度

求顺序栈的长度非常简单，让栈顶指针减栈底指针即可得到长度。
代码如下：

int StackLength(Stack s){
   
   
    return s.top - s.base;
}

清空顺序栈

清空顺序栈并不是释放栈的内存，而是清除栈内的元素，不管栈内有没有有用的元素，我们此时统统认为它们是无用的，是垃圾，所以只需将栈顶指针指向栈底即可完成顺序栈的清空。
代码如下：

void ClearStack(PStack s){
   
   
    if(s->base != NULL){
   
   
        s->top = s->base;
    }
}

销毁顺序栈

销毁很简单，把栈的内存释放即可。
代码如下：

void DestroyStack(PStack s){
   
   
    if(s->base != NULL){
   
   
        free(s->base);
        s->stacksize = 0;
        s->base = s->top = NULL;
    }
}

顺序栈的入栈

上面的操作比较简单，下面来看看比较复杂的操作：入栈和出栈。
假设有下面的一个顺序栈：
在这里插入图片描述
如何对该顺序栈进行入栈操作呢？
把入栈元素值赋值给top指针指向的位置，然后top指针往上移动一位。

还得考虑栈满的情况，也就是当top - base == stacksize时，栈满，无法入栈。
代码如下：

int    Push(PStack s,int val){
   
   
    //判断栈是否满
    if(s->top - s->base == s->stacksize){
   
   
        return -1;
    }
    //将元素val入栈
    *s->top = val;//对top指针所指的区域赋值
    //栈顶指针加1
    s->top++;
    return 1;//入栈成功，返回1
}

顺序栈的出栈

假设有如下的一个顺序表：
在这里插入图片描述
如何实现出栈呢？
top指针指向的是栈顶元素的上一个位置，所以要想实现出栈操作，得先让top指针向下移动一位，然后取出元素：

当然还需要考虑栈空的情况，当栈顶指针和栈底指针指向同一个位置，即：top == base时，栈空，无法出栈。
代码如下：

int Pop(PStack s,int *val){
   
   
    //判断栈是否空
    if(StackEmpty(*s)){
   
   
        return -1;
    }
    s->top--;//将指针下移
    *val = *s->top;//元素出栈
    return 1;//出栈成功，返回1
}

初始化、入栈、出栈的操作我们都实现了，下面来测试一下：

void main(){
   
   
    Stack s,*ps;
    int val,i;
    ps = &s;
    InitStack(ps);
    Push(ps,1);
    Push(ps,2);
    Push(ps,3);

    for(i = 0;i < 3;i++){
   
   
        Pop(ps,&val);
        printf("出栈元素:%d\t",val);
    }
    getchar();
}

运行结果：

出栈元素：3    出栈元素：2    出栈元素：1

在初始化的时候，我们是通过传入一个Stack指针类型的变量ps，而ps的值是Stack类型变量s的地址，为什么要这样做呢？
因为如果直接使用变量ps，或者直接通过PStack定义出指针变量，再将该变量作为参数传入初始化函数时，程序会检测出你没有对该变量进行初始化，从而产生错误，所以必须这么做。当然，你也可以把这一步骤放到初始化函数内部进行。

栈的链式实现

下面来说一说栈的链式实现，对于链式栈，我们同样通过链表实现，对于链栈，它只能在链表头部进行操作，我们将链表头部称为栈顶，链表尾部称为栈底。
链栈的结构定义如下：

typedef struct Node{
   
   
    ElemType data;//数据域
    struct Node *next;//指针域
}Node,*Stack;

在链栈中，可以不需要头结点(增设头结点反而会使操作更复杂)，那么链表的头指针其实就是栈顶指针。

链栈的基本操作

链栈的初始化

链栈的初始化非常简单，无需创建头结点，声明头指针并设初始值为NULL即可，代码如下：

Stack InitStack(){
   
   
    //构造一个空栈
    Stack s = NULL;//s为头指针，亦为栈顶指针，初始值为NULL
    return s;
}

判断链栈是否为空

判空算法也很简单，看看栈顶指针是否为NULL就可以了，代码如下：

int StackEmpty(Stack s){
   
   
    //若栈顶指针为NULL，表明栈为空
    if(s == NULL){
   
   
        return 1;
    }else{
   
   
        return 0;
    }
}

关于其它的一些操作比较简单，写法类似于单链表，下面重点说一说入栈和出栈操作。

链栈的入栈操作

假设有下面的一个链栈：
在这里插入图片描述
如何实现入栈操作呢？
先让新结点p的指针域指向栈顶结点，即：p->next = s。

然后要让新插入的结点p成为栈顶结点，即：s = p。

此时完成入栈操作。
代码实现如下：

Stack Push(Stack s,int val){
   
   
    //创建新结点
    Stack p = (Stack) malloc(sizeof(Node));
    if(p == NULL){
   
   
        exit(-1);
    }
    p->data = val;
    //让p指向栈顶结点
    p->next = s;
    //让p成为栈顶结点
    s = p;
    return s;
}

链栈的出栈操作

假设如下的一个链栈：
在这里插入图片描述
该如何实现出栈呢？
出栈非常简单，让栈顶指针s指向下一个结点就可以了，即：s = s->next。

但此时我们就找不到被删除的结点了，所以在改变指针指向之前，我们需要定义一个结点类型变量p存储栈顶结点，然后改变指针指向，最后释放p，完成出栈操作。
代码实现如下：

Stack Pop(Stack s,int *val){
   
   
    Stack p;
    if(s == NULL){
   
   
        printf("栈为空!");
        return s;
    }
    *val = s->data;
    //保存栈顶结点
    p = s;
    //让栈顶指针指向下一个结点
    s = s->next;
    //释放结点内存
    free(p);
    return s;//出栈成功
}

下面来测试一下：

void main(){
   
   
    Stack s;
    int val = 0,i;
    s = InitStack();
    s = Push(s,1);
    s = Push(s,2);
    s = Push(s,3);

    for(i = 0;i < 3;i++){
   
   
        s = Pop(s,&val);
        printf("出栈元素值:%d\t",val);
    }
    getchar();
}