【数据结构】带你深入理解栈

布满荆棘的人生 2024-04-25 20:03 62阅读 0赞

![dc9f68be7af3d039ebde123556a3d696.gif][]

### 一. 栈的基本概念? ###

栈是一种特殊的线性表。其只允许在固定的一端进行插入和删除元素的操作，进行数据的插入和删除的一端称作栈顶，另外一端称作栈底。栈不支持随机访问，栈的数据元素遵循后进先出的原则，即LIFO（Late In First Out）。

也许有人曾经听说过压栈和入栈的术语，以下是它们的定义：

> **压栈：**栈的插入操作叫做进栈/压栈/入栈，插入数据是在栈顶   
> **出栈：**栈的删除操作叫做出栈/弹栈，删除数据也是在栈顶

我们结合动图来理解栈的后进先出：

![4a3678ef329cc8a3625b62d8651e4adc.gif][]

### 二. 栈实现方法的分析与选择? ###

#### 2.1 引入 ####

我们可以使用顺序存储结构或者链式存储结构来实现栈。换句话来说，我们可以使用之前学习过的顺序表或者链表来实现栈，它们各自有自己的优缺点，下面我们就来分析分析。

#### 2.2 用顺序表来实现 ####

以下是动态顺序表实现栈的结构体声明和图示：

typedef struct StackList
    {
        STDataType* a; //指向动态开辟的空间
        int top; //栈顶所在下标，相当于元素个数
        int capacity;//顺序表容量
    }ST;

![5bc4495acb1b475cabbceb0d465abcf8.png][]

> **优点：**由于栈的插入和删除数据符合 后进先出的原则，我们 把顺序表末端当作栈顶，则插入数据和删除数据就是 尾插和 尾删 。而前面我们知道 顺序表的尾插和尾删效率非常高 ，时间复杂度为O（1）。  
>   
> **缺点：** 存在容量限制，当容量不足是需要扩容，扩容需要成本。

#### 2.3 用链表来实现 ####

##### 2.3.1 单链表实现(尾为栈顶) #####

typedef struct StackNode
    {
        STDataType x;//数据域
        StackNode* nest;//指针域，指向下一结点
    }ST;
    struct Stack
    {
        ST* phead;//指向第一个结点
        ST* tail;//指向尾结点
    }

![e86a1a2983ef490e9bc94caea5a5944f.png][]

假如我们使用链表尾当作栈顶，则对应的插入删除就是尾插和尾删。我们知道单链表的尾插和尾删要先找到链表尾，时间复杂度是O(N)。可能有人会想，那我定义一个尾指针来记录链表尾部，想法很好，但是这样虽然解决了尾插效率低的问题，但是尾删除了要找到最后一个结点，还要找到其前面的结点，由于链表单向，最终还是要遍历链表，没有什么意义。

--------------------

##### 2.3.2 单链表实现(头为栈顶) #####

我们知道，和顺序表相反，单链表头插和头删效率较高，时间复杂度为O（1）。我们就可以将链表头当作栈顶，这样插入就相当于头插，删除就相当于头删，如下：

![c075f1c594700f4b67f8f966ccba933e.gif][]

##### 2.3.3 双向链表实现 #####

如果一定要使用链表以及把链表尾当作栈顶，为了解决删除需要找到尾结点的前驱结点时间效率低的问题，我们可以用双向链表来实现栈。双向链表除了后继指针还增加了前驱指针来指向上一个结点，利用这个结构可以直接得到上一个结点，无需再遍历链表，时间复杂度为O（1）。

typedef struct StackNode
    {
        STDataType x;//数据域
        StackNode* nest;//后继指针域，指向下一结点
        StackNode* prev;//前驱指针域，指向上一结点
    }ST;
    struct Stack
    {
        ST* phead;//指向第一个结点
        ST* tail;//指向尾结点
    }

![45edc011c97a4cd5a526c94b4b5636f0.png][]

##### 2.3.4 总结 #####

> 如果 没有要求栈顶的位置，则我们还是使用 单链表来实现，将头作为栈顶。这是因为 双向链表比单链表的结点多占用了一个前驱指针的空间，虽然现代计算机空间已然构不成太大问题，但是能省则省，大伙们懂的 ?。  
> 如果题目要求栈顶在链表尾的话，那还是老老实实用 双向链表实现吧。  
> 使用链表的缺点就是每次插入都要malloc新结点，会消耗一定的时间成本。

#### 2.4 选择 ####

> 我们推荐采用 顺序表来实现对栈的操作，原因如下：  
> **1.** 栈的特性完美利用了顺序表尾插尾删效率高的特性，虽然需要扩容，但是链表创建结点也同样需要成本，而 顺序表扩容频率不像链表一样如此频繁。  
> **2.**  我们知道CPU与主存速度上存在巨大差距，为了提高效率，CPU和主存之间还存在着 cache高速缓存。 CPU访问cache的速度是快于主存的。每次CPU取数据时会访问cache看看存不存在所需的数据，如果不存在才会访问主存，然后将数据所在的内存块加载到cache中。由于顺序表空间是连续的，根据cache的 空间局部性原理，采用顺序表 cache的命中率会高于链表，效率高。

### 三. 接口的实现✈ ###

#### 3.1 栈的声明 ####

> 本文我们采用动态顺序表来实现栈，结构体的声明如下：

typedef int STDataType;
    typedef struct StackList
    {
        STDataType* a;//指向动态开辟的空间
        int top; //栈顶所在下标，相当于元素个数
        int capacity;//栈的容量
    }ST;

和前面链表顺序表一样，我们不直接指定数据的类型，而是将类型重定义为STDataType，这样做有利于提高代码的可维护性。

#### 3.2 初始化和销毁 ####

和其他数据结构一样，当我们使用栈结构之前需要对其进行初始化，当我们不再使用它是要对它进行销毁，具体代码如下：

//初始化栈
    void StackInit(ST* ps)  //需要改变实参，传指针
    {
        assert(ps);//确保传入的指针不为空
        ps->a = (STDataType*)malloc(4 * sizeof(STDataType));//起初先分配四个字节空间
        ps->capacity = 4;
        ps->top = 0;
    }
    
    //销毁栈
    void StackDestroy(ST* ps)
    {
        assert(ps);
        free(ps->a);//将栈空间释放掉
        //将栈结构中的信息清空
        ps->capacity = 0;
        ps->top = 0;
        ps->a = NULL;
    }

#### 3.3 入栈 ####

由于栈只允许在固定的一端插入，我们又将末端当作栈顶，因此入栈就是尾插。而顺序表的尾插我们已经很清楚了，往栈顶所在下标放入数据，然后栈顶下标加1即可。效果和代码如下：

![d9268f35ee59e039a12be71efca90690.gif][]

//入栈
    void StackPush(ST* ps, STDataType x)
    {
        assert(ps);
        if (ps->top == ps->capacity) //元素个数等于容量，栈满了，先扩容
        {
            STDataType* temp = (STDataType*)realloc(ps->a, 2 * ps->capacity*sizeof(STDataType));
            if (temp == NULL)//失败则退出程序
            {
                printf("扩容失败\n");
                exit(-1);
            }
            else
            {
                ps->a = temp;
                ps->capacity *= 2;
                temp = NULL;
            }
        }
        (ps->a)[ps->top] = x;//入栈
        (ps->top)++;//更新栈顶位置
    }

#### 3.4 出栈 ####

和入栈一样，出栈也只在固定的一端进行。入栈是尾插，则出栈就是尾删。而我们用顺序表来实现栈，因此尾删只需要将栈顶退后一位即可。

> 这里有人可能会将栈顶的元素置0然后再将栈顶位置后退一位。实际上这种方法并不可取，有以下两种原因：  
> **1.**  如果栈顶的元素本身就是0，那我们的行为就失去了意义。  
> **2.**  栈的元素类型不一定是整形，如果是浮点型或者结构体，我们赋值为0显然是不妥的。

![d1b260e97f162fbd4d5eb47d7256ebcc.gif][]

//出栈
    void StackPop(ST* ps)
    {
        assert(ps);//确保传入指针不为空
        assert(ps->top);//确保栈存在元素
        (ps->top)--;//更新栈顶
    }

#### 3.5 求栈顶元素 ####

很简单，我们可以直接根据栈顶所在的下标得到栈顶元素，如下：

![680fafb68d7f443b8ebca66df8d7005a.png][]

//求栈顶元素
    STDataType StackTop(ST* ps)
    {
        assert(ps);
        assert(ps->top);//确保栈中存在元素
        return ps->a[ps->top - 1];//栈顶元素所在下标即为top-1
    }

#### 3.6 判空 ####

在我们设计的栈结构中，top实际上就等价于元素个数，通过判断top是否为0就可以知道栈是否为空。我们使用了C语言stdbool.h头文件中的bool类型，其只能用来存放true(1)和false(0)两个值，分别代表真和假。代码如下：

//判空
    bool StackEmpty(ST* ps)
    {
        assert(ps);
        return ps->top;//top为0则返回false，不为零返回true
    }

#### 3.7 求栈的元素个数 ####

根据我们构造的栈结构体，栈顶top的值就是栈的元素个数，直接返回即可：

//求栈的元素个数
    int StackSize(ST* ps)
    {
        assert(ps);
        return ps->top;
    }

#### 3.8 思考 ####

> 会不会有人会有以下思考：  
> **1.** 求栈顶元素，判空，求元素个数都是用一行直接返回，这些接口会不会有些许多余，直接访问结构体相应成员不就好了？  
> **2.** 为什么没有实现查找，打印，修改等接口？

下面我们来分析一下：

*  我们要知道，数据结构的实现方式多种多样，在本文我们将栈元素个数作为栈顶的下标，那可不可以将最后一个元素的下标作为栈顶下标呢？实际上完全可以。那么就会出现一个问题，如果我们使用别人已经封装好的栈，我们要怎么知道栈顶元素下标是top还是top-1呢？我们要怎么知道是top=0为空还是top=-1为空呢？我们要怎么知道元素个数是top还是top+1呢？我们完全不知道，只有设计者才知道，因此设计者往往会将这些功能再封装成函数，供我们直接调用。

*  这是因为栈是一种限制型数据结构，其不支持随机访问，只允许在固定的一端(栈顶)进行插入和删除操作，不允许在其他的位置进行任何操作。因此，栈不存在查找，打印，修改等对除栈顶之外的位置进行操作的接口，否则会破坏栈的特性。为了遵循栈的特性，我们就不实现这些接口。

### 四. 完整代码及效果展示? ###

按照以往惯例，我们采用多文件编写的形式，将上述接口的定义实现放在Stack.c文件中，然后将接口的声明和结构体的定义放于Stack.h头文件中，以达到封装的效果。这样我们如果需要使用栈，就只需要在文件中包含对应的头文件Stack.h就可以使用我们上面定义的各种接口。以下为本文实现的栈完整代码以及效果展示：

//Stack.h文件，用于声明接口函数，定义结构体
    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<stdbool.h>
    
    typedef int STDataType;
    typedef struct StackList
    {
        STDataType* a;//指向动态开辟的空间
        int top; //栈顶所在下标，相当于元素个数
        int capacity;//栈的容量
    }ST;
    
    //初始化
    void StackInit(ST* ps);
    //销毁
    void StackDestroy(ST* ps);
    //出栈
    void StackPop(ST* ps);
    //入栈
    void StackPush(ST* ps, STDataType x);
    //求栈顶元素
    STDataType StackTop(ST* ps);
    //求栈元素个数
    int StackSize(ST* ps);
    //判空
    bool StackEmpty(ST* ps);

//Stack.c文件，用于定义接口函数
    #include"Stack.h"
    
    //初始化栈
    void StackInit(ST* ps)  //需要改变实参，传指针
    {
        assert(ps);//确保传入的指针不为空
        ps->a = (STDataType*)malloc(4 * sizeof(STDataType));//起初先分配四个字节空间
        ps->capacity = 4;
        ps->top = 0;
    }
    
    //入栈
    void StackPush(ST* ps, STDataType x)
    {
        assert(ps);
        if (ps->top == ps->capacity) //元素个数等于容量，栈满了，先扩容
        {
            STDataType* temp = (STDataType*)realloc(ps->a, 2 * ps->capacity * sizeof(STDataType));
            if (temp == NULL)//失败则退出程序
            {
                printf("扩容失败\n");
                exit(-1);
            }
            else
            {
                ps->a = temp;
                ps->capacity *= 2;
                temp = NULL;
            }
        }
        (ps->a)[ps->top] = x;//入栈
        (ps->top)++;//更新栈顶位置
    }
    
    
    //出栈
    void StackPop(ST* ps)
    {
        assert(ps);//确保传入指针不为空
        assert(ps->top);//确保栈存在元素
        (ps->top)--;//更新栈顶
    }
    
    //求栈顶元素
    STDataType StackTop(ST* ps)
    {
        assert(ps);
        assert(ps->top);//确保栈中存在元素
        return ps->a[ps->top - 1];//栈顶元素所在下标即为top-1
    }
    
    //求栈的元素个数
    int StackSize(ST* ps)
    {
        assert(ps);
        return ps->top;
    }
    
    
    //判空
    bool StackEmpty(ST* ps)
    {
        assert(ps);
        return ps->top;//top为0则返回false，不为零返回true
    }
    
    //销毁栈
    void StackDestroy(ST* ps)
    {
        assert(ps);
        free(ps->a);//将栈空间释放掉
        //将栈结构中的信息清空
        ps->capacity = 0;
        ps->top = 0;
        ps->a = NULL;
    }

最后， 我们在tesst.c文件调用栈各个接口进行测试，如下：

//test.c文件，用于测试
    #include"Stack.h"
    
    void test01()
    {
        ST s1;
        //初始化
        StackInit(&s1);
        //求元素个数
        printf("入栈前栈的元素个数为:%d\n", StackSize(&s1));
        //入栈
        StackPush(&s1,1);
        StackPush(&s1, 2);
        StackPush(&s1, 3);
        StackPush(&s1, 4);
        printf("入栈后栈的元素个数为:%d\n", StackSize(&s1));
        //由于无法遍历打印，我们就交替使用 求栈顶元素-出栈 来显示栈中元素
        printf("栈中元素:> ");
        while (StackEmpty(&s1))//栈不为空则继续
        {
            //求栈顶元素
            printf("%d ", StackTop(&s1));
            //出栈
            StackPop(&s1);
        }
        //全部出栈
        printf("\n全部出栈后栈的元素个数为:%d\n", StackSize(&s1));
        //销毁
        StackDestroy(&s1);
    }
    
    int main()
    {
        test01();
        return 0;
    }

以下是测试的最终效果：

![4610d33863694068a14e4c81e8639c5c.png][]

--------------------

***以上，就是本期的全部内容啦***?

***制作不易，能否点个赞再走呢***?

[dc9f68be7af3d039ebde123556a3d696.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/5ffbf52965c64c5bad2c61f392a5e5fb.gif
[4a3678ef329cc8a3625b62d8651e4adc.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e88a82baa7e64fb2a66c71c41e10bfb6.gif
[5bc4495acb1b475cabbceb0d465abcf8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/336539b1970b4a8fa2e5b2e8a8a0e01c.png
[e86a1a2983ef490e9bc94caea5a5944f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/4a0564ad1b3d4d20bafeb428fe85f9b6.png
[c075f1c594700f4b67f8f966ccba933e.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/42ae438f6e294c5e97af2f5ff5f72e81.gif
[45edc011c97a4cd5a526c94b4b5636f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e27800940bb24f2fb638a94c37e13ed0.png
[d9268f35ee59e039a12be71efca90690.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/b5a0eedf69414d059a8d5d8cd8ab34c2.gif
[d1b260e97f162fbd4d5eb47d7256ebcc.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/904558c6b8b24a5f837502f099433db7.gif
[680fafb68d7f443b8ebca66df8d7005a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/0dbdca09498c4c579a5fae1eddd06e91.png
[4610d33863694068a14e4c81e8639c5c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/3054a9d15c3a472b89b53e9735e0145f.png