数据结构与算法

Lesson05 - 操作受限的线性表02 - 队列

👉 我是喜欢编程，喜欢动漫，喜欢健身的吴小哲同学 👉 👉 欢迎您阅读我的博客 👉 👉 您的一键三连是对我最大的鼓励和帮助~ 👉

文章目录

• 数据结构与算法
• 前言
• 1 队列
• • 1.1 基本概念
• 2 队列的存储
• • 2.1 队列的顺序存储
  • • 2.1.1 循环队列
  • 2.2 队列的链式存储
• 3 链队列的实现（C语言版，无伪代码）
• • 3.1 创建队列
  • 3.2 初始化（Init）
  • 3.3 入队（Push）
  • 3.4 出队（Pop）
  • 3.5 获取队头元素（GetFront）
  • 3.6 获取队尾元素（GetBack）
  • 3.7 获取队列中有效元素的个数（QueueSize）
  • 3.8 判空（IsEmpty）
  • 3.9 销毁队列（QueueDestroy）
• // 后记

前言

💘 Lesson04和Lesson05 主要讲解数据结构中两个操作受限的线性表 - 栈和队列
💘 重点讲解栈和队列的基本概念和特点
💘 然后用C语言模拟实现栈和队列
💘 本篇文章没有伪代码，帮助大家在理解的前提下，自己动手用C语言实现栈和队列

1 队列

1.1 基本概念

🏃 队列与栈一样，都是操作受限的线性表
🏃 栈只允许在一端进行插入和删除操作，而队列是允许在一端进行插入，在另一端进行删除

🏃 其中进行删除操作的一端称为 - 队头
🏃 另一端进行插入操作称为 - 队尾
🏃 队列的插入操作称为 - 入队（Push）
🏃 队列的删除操作称为 - 出队（Pop）

💘 结构图如下：

🏃 由上图可以看出，先入队的元素先出队
🏃 因此，队列有一个特性，也是原则 - 先进先出 FIFO（First In First Out）

2 队列的存储

🏃 结合我们在线性表学到的知识：线性表的实现可以用顺序表（数组）或者链表
🏃 因此队列也可以用顺序表或者链表来存储

2.1 队列的顺序存储

🏃 分配一块连续的存储单元来存放队列的数据元素
🏃 由于我们是在两端进行操作，因此设置两个变量（head）（tail）来记录队头和队尾

💘 但是，这种存储情况会出现如下图的问题

🏃 当 A B C D E F 出队后，队头和队尾相遇，此时的状态是一种队满的状态
🏃 但是，由上图我们可以看到，依旧有6个位置可以存储数据，这种情况我们称为 “假溢出”
🏃 但是，我们可以将这个数组想象成一个环，上图情况我们可以继续在 A B C D E F 位置存储数据，由此引出循环队列的概念

2.1.1 循环队列

🏃 把队列存储的表从逻辑上视为一个环，称为循环队列

🏃 为了区分队空和队满，我们会牺牲一个存储单元
🏃 队空：head == tail
🏃 队满：（tail+1）% maxsize == head（由于本质是一个数组，当tail + 1 大于数组大小时，需要重置为 0 ，所以需要 % 上数组的大小）

2.2 队列的链式存储

🏃 用链表来存储队列称为链队列，是一个带有队头指针和队尾指针的单链表

🏃 那么在队列中进行的操作，就跟在单链表中进行的操作大体一致，只不过要注意只能在队头删除元素，在队尾插入元素

3 链队列的实现（C语言版，无伪代码）

3.1 创建队列

🏃 定义一个队列的结点，并且在 main 函数里创建一个队列的开始位置

typedef int QDataType;//定义单个队列的结点typedef struct QNode{struct QNode* next;//指向下一个结点的指针 - 指针域QDataType val;//结点存储的数据 - 数据域}QNode;//定义一个队列，队列有头指针和尾指针两个指针typedef struct Queue{QNode* head;QNode* tail;}Queue;int main(){Queue q;//创建一个队列return 0;}

3.2 初始化（Init）

🏃 将队列的头指针和尾指针置为空即可

//队列的初始化void QueueInit(Queue* q){q->head = NULL;q->tail = NULL;}

3.3 入队（Push）

🏃 入队的时候注意讨论队列是非为空队列的情况

🏃 空队列入队，将队列里的 head 和 tail 指针全部指向新创建的结点
🏃 非空队列入队，相当于之前讲的单链表的尾插操作

//入队void QueuePush(Queue* q, QDataType x){//创建一个新结点QNode* tmp = (QNode*)malloc(sizeof(QNode));if (tmp == NULL){perror("QueuePush::malloc");}tmp->val = x;//处理空队列的情况if (q->head == NULL){q->head = tmp;q->tail = tmp;}//如果非空，直接尾插即可q->tail->next = tmp;q->tail = tmp; //注意尾插过后修改tail的位置}

3.4 出队（Pop）

🏃 如果队列为空，无需出队。如果队列不为空，出队操作相当于单链表的头删

//出队void QueuePop(Queue* q){if (q->head == NULL) return;//先记录队头的下一个结点QNode* next = q->head->next;free(q->head);//删除队头元素q->head = next;//修改队头指针}

3.5 获取队头元素（GetFront）

🏃 返回 head 指针指向结点的 val 值即可

//获取队头元素QDataType GetQueneFront(Queue* q){return q->head->val;}

3.6 获取队尾元素（GetBack）

🏃 返回 tail 指针指向结点的 val 值即可

//获取队尾元素QDataType GetQueneBack(Queue* q){return q->tail->val;}

3.7 获取队列中有效元素的个数（QueueSize）

🏃 遍历整个队列，直到遍历到尾结点位置

//队列有效元素的个数int QueueSize(Queue* q){int count = 0;//从队头位置开始遍历队列QNode* cur = q->head;//结束标志为cur == q->tailwhile (cur != q->tail){count++;cur = cur->next;}return count；}

3.8 判空（IsEmpty）

🏃 如果头指针指向NULL即为空

//判空bool IsEmpty(Queue* q){return q->head == NULL;}

3.9 销毁队列（QueueDestroy）

🏃 开辟的所有结点都需要释放

//销毁队列void QueueDestroy(Queue* q){QNode* cur = q->head;while (cur != NULL){//先记录待销毁结点的下一个结点QNode* next = cur->next;free(cur);//释放当前结点cur = next;//转到下一个结点}q->head = NULL;q->tail = NULL;}

💘 以上就是队列的重点内容，其实在我们学完链表后，只要注意插入和删除操作的位置，自主实现队列不成问题

// 后记

🏃 以后每周会更新两到三篇学习数据结构的笔记，用来记录自己的学习历程，复习巩固所学的知识。
🏃 文中概念或者代码有任何错误的地方，希望大佬们在评论区指出，本人会虚心接受并且改正。

全民K歌