…

本文已收录至：数据结构 | C语言
更多知识尽在此专栏中!

文章目录

  • 前言
  • 正文
    • 栈
      • 结构
      • 初始化
      • 销毁
      • 入栈、出栈
      • 查看栈顶元素
      • 查看栈内有效元素
      • 判断栈是否为空
    • 队列
      • 结构
      • 初始化
      • 销毁
      • 入队、出队
      • 查看队头、队尾元素
      • 查看队内有效元素
      • 判断队是否为空
    • 源码区
      • 栈
      • 队列
    • 相关OJ试题推荐
  • 总结

前言

栈（Stack）又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。队列（Queue）也是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的后端（Rear）进行插入操作，和栈一样，队列 的部分操作也会受到限制。栈 的特点是 先进后出（FILO），队列 则是 先进先出（FIFO），本文将会通过顺序存储的方式模拟实现 栈，以及链式存储的方式模拟实现 队列，两种数据结构都比较简单，一起来看看吧！

正文

栈

首先介绍 栈 的实现，栈 非常适合通过 顺序表 来模拟实现，因为 顺序表 尾插、尾删的复杂度是O(1)，并且 栈 的插入、删除都是在 栈顶 完成的，因此我们可以去除 顺序表 的部分功能，这样就可以得到一个 栈

有人将栈形象的比作弹匣，装弹是在入栈，而将子弹射出则是在出栈，显然最先进入弹匣的子弹，将会在最后才被射出，准备的动图发不出来，可以自行百度查看

结构

既然可以通过 顺序表 实现 栈 ，那么 栈 的结构自然就和 顺序表 差不多了，都有一个 负责指向存储数据的指针 ，一个 下标(栈顶) 和 容量 ，因为 顺序表要求空间必须是连续的，因此后续需要进行动态内存开辟，而容量是不能少的

typedef int STDataType;//栈的元素类型typedef struct StackInfo{STDataType* data;//数据int top;//栈顶int capacity;//容量}Stack;

初始化

初始化需要把 指针 data 置空，栈顶值 top 和 容量值 capacity 归0

  • 当然这里的栈顶也可以置为-1，当我们取栈顶元素时，取的就是当前栈顶处的元素
  • 如果是归0，那么取的就是栈顶-1处的元素
  • 推荐归0，因为在后续操作中比较省事
void StackDestroy(Stack* ps)//栈的销毁{assert(ps);//只有为栈开辟空间了，才能正常销毁if (ps->data){free(ps->data);ps->data = NULL;ps->top = ps->capacity = 0;}}

销毁

销毁 栈 需要明白一点：是否可以销毁 ，因为可能会出现不插入元素的情况下，结束程序，此时如果继续执行销毁，就会发生空指针的解引用情况

void StackDestroy(Stack* ps)//栈的销毁{assert(ps);//只有为栈开辟空间了，才能正常销毁if (ps->data){free(ps->data);ps->data = NULL;ps->top = ps->capacity = 0;}}

入栈、出栈

顺序 栈 的 入栈、出栈 很简单，可以放一起介绍

  • 入栈
    • 确保有空间可以使用，因此需要借助扩容程序段
    • 直接将目标值插入到栈顶处
    • 最后栈顶+1，此时的栈顶代表着 栈 中的有效元素个数
void StackPush(Stack* ps, STDataType x)//入栈{assert(ps);//判断栈是否满if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 " />
 
 
  • 出栈   
    • 出栈需要确保 栈 内有元素可出
    • 如果 栈 为空，是不能执行出栈的
    • 出栈不需要将元素抹掉，直接栈顶-1，无法访问到此元素就行了
     
 
void StackPop(Stack* ps)//出栈{assert(ps);assert(ps->top > 0);//有元素才能出栈//出栈，直接栈顶-1ps->top--;}
查看栈顶元素
前面说过，栈顶值 top-1 代表的就是当前栈顶元素，前提是有元素存在，因此这个函数就很简单了，直接先判断 栈 是否为空，如果不为空，返回 栈顶-1 处的元素值就行了
STDataType StackTop(Stack* ps)//查看栈顶元素{assert(ps);assert(ps->top > 0);//有元素才能看//栈顶元素，在栈顶-1处，因为栈顶是从0开始的return ps->data[ps->top - 1];}
查看栈内有效元素
所谓栈内有效元素，就是顺序 栈 的长度，也就是 栈顶值 top ，此时就体现出 栈顶值 从0开始的好处了，做什么都很方便，比如这里，直接返回 栈顶值 就行了
int StackSize(Stack* ps)//查看栈的有效元素个数{assert(ps);//栈的大小就是当前栈的有效元素个数return ps->top;}
判断栈是否为空
判断栈是否为空，太简单了，一行代码解决
  • 返回的是布尔值，需要引头文件 stdbool.h
  • 因为判断式返回值是布尔类型
    • 如果栈顶值为0，说明栈空，判断式为真，返回 true
    • 否则说明栈不空。判断式为假，返回 false
bool StackEmpty(Stack* ps)//判断栈是否为空{assert(ps);//栈顶为0.说明栈空return ps->top == 0;}
顺序 栈 也就这点东西，我愿称之为顺序表青春版，所有源码放在gitee上了，可以跳转到源码区传送过去
下面是程序运行图(测试的时候手速太快了，所以有的地方可能看不太清楚)
 这是一张动图，时长56秒
 
队列
队列 的特点是先进先出，主要功能是头部删除和尾部插入，因为队列比较特殊，如果采用 顺序表 的形式实现的话，容易出现 假溢出 问题（后续解决 循环队列 问题会用 顺序表 模拟实现），因此我们这里采取 链表 的形式模拟实现 队列
分析得出队列的 需求 如下
  • 单链表就足够了，多加一个队尾指针，可以有效避免效率问题
  • 哨兵位（可要可不要），因为待会实现时，是结构体嵌套结构体的形式
  • 使用非循环的链表，没必要使用双向带头循环链表（小题大做）
结论
  • 最简单的单链表就可以实现
  • 因为有队头、队尾两个指针，因此需要使用结构体嵌套的方式
     
结构
单链表 最大的缺陷就是不好找尾，为此我们直接通过结构体嵌套定义的方式，定义 队头指针 front 、队尾指针 rear 和 队列长度 size，这样一来，所有涉及队列的操作，都是在以 O(1) 效率执行，灰常高效，就是比较难理解
帮助理解
  • 假设队列中的节点是一个个链接的小球
  • 存在一个大外壳装着这些小球
  • 并且有两个警卫分别守着球头和球尾，还有一个秘书帮忙记录球数
  • 当然它们的作用是为了更好的管理小球
  • 显然，front 和 rear 就是两个警卫，而 size 是秘书
typedef int QListDataType;//队列的数据类型//这是队列中，单个节点的信息typedef struct QListNode{QListDataType data;struct QListNode* next;}QNode;//这是整个队列的信息，包含了队头和队尾两个指针typedef struct QueueNode{QNode* front;//队头指针QNode* rear;//队尾指针size_t size;//队列长度}Queue;
初始化
队列 的初始化很直接，把 队尾、队头指针 置空，长度 置0就行了
void QueueInit(Queue* pq)//队列的初始化{assert(pq);//初始化状态：队头、队尾指针都指向空，队列大小为0pq->front = pq->rear = NULL;pq->size = 0;}
销毁
队列 销毁原理，和 单链表 的销毁差不多，需要借助一个 临时指针 cur ，指向当前队头，然后 队头指针 front 移向下一个位置，销毁 临时指针 cur ，如此循环，直到 临时指针 cur 指向 NULL ，此时整个 队列 都会被销毁
  • 队列 不需要像 栈 那样做特殊处理，因为当队空时，cur 一开始就为空，循环是进不去的
  • 当然销毁后，两个指针都要置空，size 也要归零
void QueueDestroy(Queue* pq)//队列的销毁{assert(pq);//销毁思路：利用临时指针进行销毁QNode* cur = pq->front;while (cur){QNode* tmp = cur->next;free(cur);cur = tmp;}pq->front = pq->rear = NULL;pq->size = 0;}
入队、出队
有了 队头、队尾 两个指针，入队、出队就很简单了，直接易如反掌
入队
  • 即单链表的尾插
  • 买一个新节点，存放目标值，将 队尾指针 与新节点链接起来
    • 注意：如果是第一次入队，直接赋值，而不是链接
  • 更新 队尾指针 ，队尾指针 变成了新节点
  • 队列长度 + 1
void QueuePush(Queue* pq, QListDataType x)//入队{assert(pq);//先买一个节点QNode* newnode = buyNode(x);//分情况：如果队头为空，说明队空，此时直接将新节点赋值给队头、队尾if (pq->front == NULL){pq->front = pq->rear = newnode;pq->size++;}else{//否则就是将新节点，链接到队尾，然后更新队尾pq->rear->next = newnode;//链接pq->rear = newnode;//更新队尾pq->size++;}}
出队
  • 即单链表的头删
  • 利用临时指针，存储当前 队头指针 的信息
  • 队头向后移动，即更新 队头指针
  • 释放临时指针
  • 队列长度 - 1
void QueuePop(Queue* pq)//出队{assert(pq);assert(!QueueEmpty(pq));//如果队空，是不能出队的//出队思想：有元素才能出队，更新队头，销毁原队头QNode* cur = pq->front;pq->front = pq->front->next;//更新队头指针free(cur);cur = NULL;pq->size--;}
查看队头、队尾元素
这两个都是甜品函数，直接一行代码解决
查看队头
  • 判断队列是否为空
  • 不为空才能查看，队头元素为 队头指针 的指向值
QListDataType QueueFront(Queue* pq)//查看队头元素{assert(pq);assert(!QueueEmpty(pq));return pq->front->data;}
查看队尾
  • 同样需要判断队列是否为空
  • 不为空才能查看，队尾元素为 队尾指针 的指向值
QListDataType QueueRear(Queue* pq)//查看队尾元素{assert(pq);assert(!QueueEmpty(pq));return pq->rear->data;}
查看队内有效元素
队列中的有效元素数，就是之前一直默默工作的 队列长度 size，直接返回它的值就好了，没什么技巧
至于为何不通过遍历的方式确定有效元素数
  • 时间成本太高，如果队列中有10w个元素，那么在调用此函数时，会很浪费时间
  • 结构设计时 size 的加入，能很好的避免这个问题，因为 size 在改变时，总是伴随着入队或出队，默默记录，效率是很高
int QueueSize(Queue* pq)//当前队列的有效元素数{assert(pq);return pq->size;//直接返回就行了}
判断队是否为空
此时判断队列是否为空，有多种方法
  • 通过 size 判断，为0，说明队列为空
  • 通过 队头指针 或 队尾指针 判断，为空说明队空
这里使用第二种方法，通过 队头指针 进行判断
 当然，返回值是 布尔值 ，同样是利用了判断式的返回值
bool QueueEmpty(Queue* pq)//判断当前队空情况{assert(pq);return pq->front == NULL;}
至此，队列 结束，结构体嵌套 也就是个纸老虎，实际还没有 二级指针 复杂，可以把 链队列 看作 单链表 的青春版
下面是程序运行图，同样是动图，可以耐心看完
 
源码区
注意：为了避免文章过长，现采取 Gitee 仓库分享代码的形式，秉持开源精神，所有代码都可参考!
栈
这是属于栈的文件夹
队列
这是属于队列的文件夹
相关OJ试题推荐
一如既往的OJ试题推荐环节，这次是 栈和队列 专场
  • 20.有效的括号
  • 225.用队列实现栈
  • 232.用栈实现队列
  • 622.设计循环队列(中等)
总结
栈和队列 是两种比较特殊的数据结构，在实际中往往很少单独去使用，都是用来配合实现其他数据结构，比如 二叉树 的 层序遍历 中会用到 队列 ，很多OJ试题也会爱考这两种数据结构，因此学好它们还是很重要的
如果你觉得本文写的还不错的话，期待留下一个小小的赞，你的支持是我分享的最大动力！
如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正
…
 相关文章推荐
 数据结构 | 顺序表
 数据结构 | 时间复杂度与空间复杂度
 数据结构 | 单链表