数据结构:第三章 - 队列 573次阅读 数据结构 2022-07-20 目录 [TOC] ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 一、基本概念 队列简称队,是一种操作受限的线性表,仅允许在表的一端(即队尾 rear)进行插入,在表的另一端(即队头 front)进行删除。特点是先进先出。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit3/DS.Unit3.%281_1%29.png) 队列存储结构的实现有以下两种方式: * 顺序队列:在顺序表的基础上实现的队列结构。 * 链队列:在链表的基础上实现的队列结构。 > 两者的区别仅是顺序表和链表的区别,即在实际的物理空间中,数据集中存储的队列是顺序队列,分散存储的队列是链队列。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 二、顺序队列(循环队列) ## (一)基础知识 在顺序队中,通常让队尾指针 rear 指向刚进队的元素位置,让队首指针 front 指向刚出队的元素位置。 因此, * 元素进队的时候,rear 要向后移动。 * 元素出队的时候,front 也要向后移动。 这样经过一系列的出队和进队操作以后,两个指针最终会达到数组末端 maxSize-1 处。 虽然队中已经没有元素,但仍然无法让元素进队,这就是所谓的“假溢出”。 要解决这个问题,可以把数组弄成一个环,让 rear 和 front 沿着环走,这样就永远不会出现两者来到数组尽头无法继续往下走的情况,这样就产生了循环队列。循环队列是改进的顺序队列。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit3/DS.Unit3.%282.1_1%29.png) ### 1、顺序队列定义 ```c typedef struct { int data[maxsize];//存放数据域 int front;//队首指针 int rear;//队尾指针 }SqQueue;//顺序队列类型定义 ``` ### 2、状态 循环队列必须损失一个存储空间,否则无法判断队满对空。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit3/DS.Unit3.%282.1.2_1%29.png) #### (1)队空 ```c qu.rear == qu.front ``` #### (2)队满 ```c (qu.rear+1)%maxsize == qu.front ``` ### 3、初始化 ```c void initQueue(SqQueue &qu) { qu.front=qu.rear=0;//队首、队尾指针重合,并指向0 } ``` ## (二)进队(移动队尾指针) ```c qu.rear=(qu.rear+1)%maxsize;//(若队未满)移动队尾指针 qu.data[qu.rear]=x;//元素进队 int enQueue(SqQueue &qu,int x) { if((qu.rear+1)%maxsize==qu.front)//队满的判断条件,队满则不能入队 return 0; qu.rear=(qu.rear+1)%maxsize;//若队未满,则先移动指针 qu.data[qu.rear]=x;//再存入元素 return 1; } ``` ## (三)出队(移动队首指针) ```c qu.front=(qu.front+1)%maxsize;//(若队不空)移动队首指针 x=qu.data[qu.front];//元素出队 int deQueue(SqQueue &qu,int &x) { if(qu.front==qu.rear) return 0; qu.front=(qu.front+1)%maxsize;//若队不空,则先移动指针 x=qu.data[qu.front];//再取出元素 return 1; } ``` ## (四)判断队空 ```c int isQueueEmpty(SqQueue &qu) { if(qu.front==qu.rear)//无论队首尾指针指向数组那个位置,只要两者重合,即队空 return 1; else return 0; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 三、链队列 ## (一)基本知识 链式队列的实现思想同顺序队列类似,只需创建两个指针(命名为 front 和 rear )分别指向链表中队列的队头元素和队尾元素。 ### 1、队结点类型定义 ```c typedef struct { int data;//数据域 struct QNode *next;//指针域 }QNode;//队结点类型定义 ``` ### 2、链队类型定义 ```c typedef struct { QNode *front;//队头指针 QNode *rear;//队尾指针 }LiQueue;//链队类型定义 ``` ### 3、状态 #### (1)队空状态 ```c lqu->rear==NULL; 或 lqu->front==NULL; ``` #### (2)队满状态 不存在队满状态(假设内存无限大的情况) ### 4、两种操作 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit3/DS.Unit3.%283.1.4_1%29.png) ## (二)进队 ```c lqu->rear->next=p; lqu->rear=p; ``` ## (三)出队 ```c p=lqu->front; lqu->front=p->next; x=p->data; free(p); ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 四、配置问题 一般说是循环队列。 ## (一)正常配置 1. 队空:front == rear 为真。 2. 队满:front == (rear + 1) % maxSize 为真。 3. ⼊队:rear = (rear + 1) % maxSize; queue[rear] = x。 4. 出队:front = (front + 1)%maxSize; x = queue[front]。 5. 队中元素个数:(rear - front + maxSize) % maxSize。 * 当 rear > front 时,有 rear - front 个。 * 当 rear < front 时,有 rear - front + maxSize 个。 ## (二)非正常配置 1. **队空:front == rear 为真。** 2. **队满:front == (rear + 1)%maxSize 为真。** 3. **⼊队:queue[rear] = x; rear = (rear + 1)%maxSize。** 4. **出队:x = queue[front]; front == (front + 1)%maxSize。** 5. **队中元素个数:(rear - front + 1 + maxSize) % maxSize。** * **当 rear > front 时,有 rear - front 个。** * **当 rear < front 时,有 rear - front + 1 + maxSize 个。** ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 五、双端队列 双端队列是一种插入、删除操作在两端均可进行的线性表。需设立两个指针 end1 和 end2,分别指向队列中两端的元素。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 六、为什么说栈和队列是线性存储结构? 线性结构,即用于存储逻辑关系为"一对一" 数据的存储结构,例如顺序存储结构和链式存储结构。 栈结构中存储的也是逻辑关系为"一对一" 的数据,只不过该结构对数据的存储顺序有额外的要求,即数据进栈和出栈要满足"先进后出" 的要求。因此可以这么说,栈是一种特殊的线性存储结构。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit3/DS.Unit3.%286_1%29.png) 队列存储结构它存储的也是逻辑关系为"一对一" 的数据,但它对数据入队和出队的要求是"先进先出"。所以说,队列也是一种特殊的线性存储结构。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit3/DS.Unit3.%286_2%29.png) 栈和队列,除了都是线性结构外,还有一个共同点,那就是数据的进出,只能在栈和队列的端点处进行。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 参考资料 > **版权声明**:个人学习记录,本博客所有文章均采用 CC-BY-NC-SA 许可协议。转载请注明出处!若有侵权,请留言联系! > > * 2022 天勤计算机考研高分笔记-数据结构 > * 2022 王道计算机考研复习指导-数据结构 > * 解学武数据结构与算法教程(C 语言版):http://data.biancheng.net/ 如果您觉得文章对您有帮助,请点击文章正下方的小**红心**一下。您的鼓励是博主的最大动力! 3 最后一次更新于2022-10-23 数据结构
0 条评论