【数据结构】栈和链表基本方法的实现
小编主页详情<-请点击
小编gitee代码仓库<-请点击
本文主要介绍了数据结构的栈和链表，内容全由作者原创（无AI），同时深度解析了栈和链表基本方法的实现，并带有配图帮助博友们更好的理解，点个关注不迷路，下面进入正文~~
目录
1.栈
1.1栈的概念及结构
1.2栈结构的定义
1.3栈需要实现的基本功能
1.4栈基本方法的实现
1.4.1初始化和销毁
1.4.2 入栈和出栈
1.4.3取栈顶数据
1.4.4判空
1.4.5获取数据个数
2.队列
2.1队列的概念及结构
2.2队列的实现
2.3队列实现的前期准备
2.4队列需要实现的基本功能
2.5队列基本方法的实现
2.5.1初始化和销毁
2.5.2队列的插入
2.5.3删除数据
2.5.4取队头和队尾的数据
2.5.5获取数据个数和判空
结语：
1.栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
我们可以形象的将栈比作一个弹夹，先装进去的子弹就先射出去。
也可以比作我们上电梯的时的先后顺序，最后进电梯的人往往最先出去。
1.2栈结构的定义
栈的实现一般可以使用数组或链表实现，那么我们具体要怎么选择呢？
这里我们首先排除双向链表，因为用单链表就足以实现栈，用双向链表会额外占用空间。
单链表和数组其实在栈的实现上区别不大，相对而言数组的结构实现更有一点，因为数组在尾上插入数据的代价比较小。这里我们就使用数组实现栈。、
typedef int SLDataTtpe; typedef struct Stact { SLDataTtpe* a; int top; int capacity; }ST;这里的top其实就是顺序表的size，从下标上看，top表示即将要插入数据的位置。
1.3栈需要实现的基本功能
栈相对与顺序表的实现要简单不少，因为栈有限制出数据和入数据的方向，需要实现的方法也相对较少，常用的方法有如下几种，如图所示。
// 初始化和销毁 void STInit(ST* pst); void STDestroy(ST* pst); // 入栈 出栈 void STPush(ST* pst,SLDataTtpe x); void STPop(ST* pst); // 取栈顶数据 SLDataType STTop(ST* pst); // 判空 bool STEmpty(ST* pst); // 获取数据个数 int STSize(ST* pst);1.4栈基本方法的实现
1.4.1初始化和销毁
这里的实现比较简单，不过多赘述
// 初始化和销毁 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->capacity = pst->top = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capacity = pst->top = 0; }1.4.2入栈和出栈
入栈最需要注意的地方就是扩容的时候先先判断capacity是否为零，为零就先赋值，不为零就翻倍。这里用三目操作符可以很好的实现
出栈的实现方法也比较简单，直接让栈顶向前走一位即可，前提是栈里面要有数据。
// 入栈 出栈 void STPush(ST* pst, SLDataType x) { assert(pst); if (pst->capacity == pst->top) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; ST* tmp = (ST*)realloc(pst->a, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { perror("STpush"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; }1.4.3取栈顶数据
需要注意的是，这里的top指的是下一个需要插入数据的位置，因此我们要找的位置应该是top的上一个位置，在访问数组时下标应是top-1。
// 取栈顶数据 SLDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; }1.4.4判空
这里用if判断top是否为可能会更好理解。为了更方便和简洁，我们可以直接返回pst->top == 0，如果为真返回1，即为true，数组为空；如果为假返回0，即为false，数组不为空
// 判空 bool STEmpty(ST* pst) { assert(pst); /*if (pst->top == 0) { return true; } return false;*/ return pst->top == 0; }1.4.5获取数据个数
top指的是下一个需要插入数据的位置，同时也是数组元素的个数，直接返回top即可。
// 获取数据个数 int STSize(ST* pst) { assert(pst); return pst->top; }2.队列
2.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
形象的说，我们在排队吃饭取号的时候，都是先取号的先用餐，队列也是如此。
2.2队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType val; }QNode;2.3队列实现的前期准备
// 队尾插入 void QueuePush(QNode** pphead, QNode** pptail, QDataType x); // 队头删除 void QueuePop(QNode** pphead, QNode** pptail);如果我们这样实现有两个很麻烦的点，一个是要使用二级指针，逻辑会比较绕。另一个是每次找最后一个节点都要遍历整个数据，这样的实现并不是很好
为了解决这个问题，我们可以重新定义一个结构体Queue储存队列的各种信息
typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue;这里额外定义了size，无需反复遍历数组，方便后续功能的实现
2.4队列需要实现的基本功能
void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); // 取队头和队尾的数据 QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq);2.5队列基本方法的实现
2.5.1初始化和销毁
这里的实现比较简单，不过多赘述
void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }2.5.2队列的插入
这里用尾插实现插入。需要分两种情况，当队列没有数据时，直接让头指针和尾指针都指向新节点。当队列有数据时，再尾插数据。
最后别忘了size++，下面是详细的代码：
void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (Queue*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("QueuePush"); return; } newnode->val = x; newnode->next = NULL; if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; }2.5.3删除数据
常规的思路释放头节点再将头节点移动到下一个节点。
可这样做存在一个特殊情况，当队列只剩一个数据时，phead指向NULL，可是ptail却仍指向那个已经被删除的节点，这样做会让ptail成为野指针，存在很大的风险。最好的解决办法也是对列只剩一个数据单独讨论，让ptail和phead都指向NULL。
最后别忘了size--哦，具体代码如下：
void QueuePop(Queue* pq) { assert(pq); assert(pq->size != 0); if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; }2.5.4取队头和队尾的数据
断言后，直接返回ptail和phead指向的数据即可。
// 取队头和队尾的数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; } QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->ptail); return pq->ptail->val; }2.5.5获取数据个数和判空
根据size大小做出对应指令即可
int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; }结语：
这篇文章全文由作者手写，图片由画图软件所制，无AI制作，希望各位博友能有所收获
欢迎各位博友的讨论，觉得不错的小伙伴，别忘了点赞关注哦~