【封神演绎、十五分钟让你彻底学会栈的使用！！！】数据结构

文章目录

前言
一、栈的概念及结构
二、栈的实现
三、链式栈的实现
总结

前言本篇文章将真正的做到事无巨细，为您讲解关于栈的有关知识，这其中分为顺序栈和链式栈，其中牵扯到了一些单链表和顺序表的内容，本片文章将一一为您从零基础开始讲解，这次的一篇文章就让您把指针、链表、顺序表、栈甚至队列的部分内容全部掌握！
提示：以下是本篇文章正文内容，下面案例可供参考
一、栈的概念及结构 1.栈的定义
一种特殊的线性表，其只允许在固定的一端进行插入和删除操作，这一点实栈和队列的一个最大的区别，队列只允许在一端进行插入操作，并且在另一端进行删除操作；而在栈中进行数据的插入和删除的被称为栈顶，另一端成为栈底，栈中的数据元素遵守后进先出的原则。
2.栈的操作
压栈：栈的插入操作叫做压栈/入栈、进栈，入数据在栈顶。
出栈：栈的删除叫做出栈，出数据也在栈顶。

后进先出：
进栈

栈顶

栈底

注意：栈顶并不是指栈的顶端，而是指栈中存放的最后一个元素的位置，所以栈顶的位置是不确定的。
出栈

栈顶

栈底

【【封神演绎、十五分钟让你彻底学会栈的使用！！！】】总结：
其实数据结构当中的栈就相当于我们日常生活当中所使用的喝水杯，如果按照一定的顺序向水杯当中加入小圆盘，而且在放进去的时候我们是从被扣放进去的，拿出来的时候也是从杯口拿出来的，那么当我们要将圆盘取出的时候是不是与放进去的顺序正好相反，这就是栈。

二、顺序栈的实现 1.顺序栈的声明：

#pragma once #include #include #includetypedef int DataType; typedef struct Stack { DataType* arr; int capacity; int top; }Stack;

说明：

a:
typedef这里相当于重命名的作用、相当于将int类型定义为DataType，此时只要代当中出现DataType就相当于int的功能，这是因为如果想将int类型的数据改成其他类型，只需要对DataType进行修改即可，否则将对全部的代码进行修改；

b:
对于结构体当中的元素的声明，这里采用了动态开辟内存，所以这里没用直接使用数组，而是使用了数组的地址，如果直接定义数组，数组一定有一个限定的大小，那么具体开辟多少会很不方便，还容易造成开辟的空间不足或是空间的浪费。使用数组的地址是动态内存分配，系统会根据所需自动分配内存大小，不会有以上的问题出现。

c:
capacity代表着栈的容量大小，如果容量不足会自动开辟空间，top是指向栈的最后一个元素的下标，注意这里不是指针，我们现在讲解的是顺序栈，之所以是顺序栈就是用数组来实现的，或者说是用顺序表来实现的。

d:
注意指针就是地址，再重复一遍指针就是地址，指针就是地址！！！我们平常所说的指针是指针变量，指针变量其实很好理解吗，请问int是整形变量，char是字符型变量，那么指针变量你能理解吗？

e:
这其中的*代表着解引用的意思，就是根据指针变量所指向的地址，找到这个地址所存放的内容，其实就是把外层皮拨开，*p当中p就是指针变量，*p就是把p所指向的东西取出来。

f:
还有int* p和*p并不是一回事，第一个里面的* 仅仅是为了告诉你p是一个指针变量，而第二个里面的*是解引用的意思，根据地址对这个地址的内存空间进行访问。

struct Stack { DataType* arr; int capacity; int top; };

通常定义一个结构体都是像上面这样的，这样子做会有什么不好的呢？那么我们可以再主函数当中定义一类结构体，看看二者的效果如何。

int main() { //1. struct Stack* s; //2. Stack* s; return 0; }

其实很简单，如果对结构体进行重命名，我们在使用它的时候会非常方便。

2.顺序栈的常见接口：
说明：

其实这里也能看出来使用重命名的好处，在对结构体传参的时候会非常容易。

void StackInit(Stack* s); void StackDestroy(Stack* s); void StackPush(Stack* s,DataType x); void StackPop(Stack* s); DataType StackTop(Stack* s); bool StackEmpty(Stack* s); int StackSize(Stack* s);

3.顺序栈接口的实现：
1）初始化顺序栈：
说明：

这里的top的初始值有-1和0两种，如果定义为-1的话入栈或出栈的时候需要先让top++再进行操作，整个操作结束的时候top指向最后一个元素，但是如果初始值定义为-1，则在进行入栈或出栈的时候需要先进行操作再令top++，最后整个操作流程走完以后top再栈顶的最后一个元素的下一个位置，这时候要取栈顶元素的话需要将top-1才可以。
简单地说就是如果top==0，top（这里为了方便用指向来表达，但希望读者了解这只是一种口语表达，并不是指针的意思）指向栈中最后一个元素的下一个位置，如果是top==-1则指向最后一个元素本身的位置。

void StackInit(Stack* s) { assert(s); s->arr = NULL; s->capacity = 0; s->top = 0; }

2）销毁顺序栈：
说明：

其实就是将顺序表销毁，使栈无法再进行一系列的操作。
这里的assert代表断言，就是认为***必须正确，否则无法继续执行，s这个地址必须真实存在，在传参的时候不可以传递一个空地址。

void StackDestroy(Stack* s) { assert(s); free(s->arr); s->arr = NULL; s->capacity = 0; s->top = 0; }

3）入栈：
说明：

当top和capacity相等的时候就是数组满容量的时候，需要系统对其进行自动扩容，这里涉及到一个三目表达式，三目表达式最后的结果赋值给newcapacity，那么这个三目表达式的作用是什么呢？s->capacity==0？是指这个表达式是否成立，如果成立将4赋值给三目表达式，如果不是就将容量*2赋值给表达式，最后表达式的结果会最终赋值给newcapacity，这就是它的作用。
tmp是对arr的一个补充，malloc是动态内存分配函数，对arr进行扩容，tmp是一个数组的地址。最后将扩容好的空间重新再赋值给原来的数组和内存。
由于我在这里设置的top值为1，所以top始终指向最后一个元素的下一个位置，所以不需要top-1操作可以直接操作，插入完成后再令top++。

void StackPush(Stack* s, DataType x) { assert(s); if (s->capacity == s->top) { int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2; DataType* tmp = (DataType*)malloc(sizeof(DataType)*newcapacity); if (tmp == NULL) { printf("realloc is fail\n"); exit(-1); } s->capacity = newcapacity; s->arr = tmp; } s->arr[s->top] = x; s->top++; }

4）出栈：
说明：

出栈直接对其的top--即可，把最后一个元素直接舍弃。

void StackPop(Stack* s) { assert(s); assert(!StackEmpty(s)); s->top--; }

5）取栈顶元素：
说明：

由于这里top==0，所以栈顶元素是在top-1这个下标的位置。

DataType StackTop(Stack* s) { assert(s); assert(!StackEmpty(s)); return s->arr[s->top - 1]; }

6）判断栈是否为空：
说明：

如果top==-1，则判断条件为return top==-1；

bool StackEmpty(Stack* s) { assert(s); return s->top == 0; }

7）求栈中的元素个数
说明：

可能会有小伙伴感到疑惑，这里的top不是在最后一个元素的后一个位置吗？为什么不是返回top-1？你可能忘了top本身就是下标，下标意味着什么，意味着从零开始，你明白了吗？

int StackSize(Stack* s) { assert(s); return s->top; }

三、链式栈 1.链式栈的声明

#pragma once #include #include #includetypedef int DataType; typedef struct Stack { struct Stack* next; DataType data; }Stack;

2.链式栈接口的实现
1）初始化栈
说明：

这里用单链表来实现，但是这里再初始化的时候先分配一个带头结点（哨兵卫结点），这个可以有效地避免在传参的时候使用二级指针，这个如果有不明白的话请参考我的另一篇文展《线性表（二、三）——单双链表》。

void InitStack(Stack* s) { s = (Stack*)malloc(sizeof(Stack)); s->next = NULL; }

2）销毁栈
说明：

s在这里是哨兵卫结点，不参与增删改查操作，所以这里找到首结点（头结点之后），再逐个删除，最后会剩下剩下一个结点，所以要在进行一次操作。

void DestroyStack(Stack* s) { assert(s); Stack* cur = s->next; while (cur) { free(s); s = cur; cur = cur->next; } free(s); }

3）入栈
说明：

在这里首先要开辟以一个新的结点，对节点进行头插法，要牢记栈与队列不同，你在哪里插入就要在哪里进行删除，这里相当于单链表的头插法。

void StackPush(Stack* s, DataType x) { assert(s); Stack* newnode = (Stack*)malloc(sizeof(DataType)); if (newnode == NULL) { printf("malloc is fail\n"); exit(-1); } newnode->next = s->next; s->next = newnode; }

4）出栈
说明：