队列
基本概念
队列是最常见的概念，日常生活经常需要排队，仔细观察队列会发现，队列是一种逻辑结构，是一 种特殊的线性表。特殊在：
- 只能在固定的两端操作线性表
只要满足上述条件，那么这种特殊的线性表就会呈现一种“先进先出”的逻辑，这种逻辑就被称为队列。
- 队头：可以删除节点的一端
- 队尾：可以插入节点的一端
- 入队：将节点插入到队尾之后
- 出队：将队头节点从队列中剔除
由于这种固定两端操作的简单约定，队列获得了“ 先进先出”的基本特性，如下图所示：
顺序存储的队列：循环队列
与其他的逻辑结构类似，队列可以采用顺序存储形成循环队列，也可以采用链式存储形成链式队 列。顺序存储的队列之所以被称为循环队列，是因为可以利用更新队头队尾的下标信息，来循环地 利用整个数组，出队入队时也不必移动当中的数据。循环队列示意图如下所示：
从上述动图中可以观察到，需要牺牲至少数组中的一个存储位置，来区分循环队列中的满队和空 队。满队和空队的约定如下：
- 当head（队头元素下标）与tail（队尾元素下标）相等时，队列为空
- 当tail循环加一与head相等时，队列为满
与其他数据结构一样，管理循环队列除了需要一块连续的内存之外，还需要记录队列的总容量、当 前队列的元素个数、当前队头、队尾元素位置，如果有多线程还需要配互斥锁和信号量等信息，为 了便于管理，通常将这些信息统一于在一个管理结构体之中：
typedef int DATA;
typedef struct{DATA *pData; // 队列入口
int size; // 队列总容量
int head; // 队列队头元素下标
int tail; // 队列队尾元素下标}SQueue;
- 循环队列的基本操作
分析
squeue.h
#ifndef __SQUEUE_H
#define __SQUEUE_Htypedef int DATA;typedef struct{DATA *pData; // 队列入口int size; // 队列总容量int head; // 队列队头元素下标int tail; // 队列队尾元素下标
}SQueue;// 初始化队列
int SQ_init(SQueue *q, int num);// 判断队列是否已满
int SQ_isfull(SQueue *q);// 判断队列是否为空
int SQ_isempty(SQueue *q);// 入队
int SQ_push(SQueue *q,DATA data);// 出队
int SQ_pop(SQueue *q,DATA *data);// 回收队
int SQ_free(SQueue *q);#endif
这段代码定义了一个带有以下功能的队列数据结构SQueue：
数据类型DATA为int类型
结构体SQueue包含了队列的基本信息，包括指向队列数据的指针pData、队列总容量size、队头元素下标head和队尾元素下标tail
函数SQ_init用于初始化队列，传入参数为队列指针和队列容量，返回值为int类型
函数SQ_isfull用于判断队列是否已满，传入参数为队列指针，返回值为int类型
函数SQ_isempty用于判断队列是否为空，传入参数为队列指针，返回值为int类型
函数SQ_push用于将元素入队，传入参数为队列指针和要入队的元素，返回值为int类型
函数SQ_pop用于将元素出队，传入参数为队列指针和接收出队元素的指针，返回值为int类型
函数SQ_free用于回收队列内存，传入参数为队列指针，返回值为int类型
此外，代码使用了条件编译，防止头文件被重复包含。
squeue.c
#include <stdlib.h>#include "squeue.h"// 初始化队列
int SQ_init(SQueue* q,int num){q -> pData = (DATA*)calloc(sizeof(DATA),num);if(q -> pData == NULL)return -1;q -> size = num ;q -> head = q -> tail = 0;return 0;}// 判断队列是否已满
int SQ_isfull(SQueue *q){return (q -> tail + 1) % q -> size == q -> head;}
// 判断队列是否为空
int SQ_isempty(SQueue *q){return q -> tail == q -> head;}// 出队
int SQ_push(SQueue *st,DATA data){if(SQ_isfull(st))return -1;st -> pData[st -> tail] = data;st -> tail = (st -> tail+1) % st -> size;return 0;}// 入队
int SQ_pop(SQueue *st,DATA *data){if(SQ_isempty(st))return -1;*data = st -> pData[st -> head];st -> head = (st -> head+1) % st -> size;return 0;}// 回收队列
int SQ_free(SQueue *st){if(st -> pData){free(st->pData);st -> pData = NULL;}st -> head = st -> tail = 0;
}
这段代码实现了一个顺序队列（squeue），包括初始化队列、判断队列是否已满、判断队列是否为空、入队、出队和回收队列的操作。
SQ_init函数用于初始化队列，参数包括队列指针和队列的最大容量。函数中使用calloc函数动态分配了一块内存作为队列的数据存储空间，如果分配失败则返回-1，否则将队列的大小和队列头尾指针初始化为0，并返回0表示初始化成功。
SQ_isfull函数用于判断队列是否已满。当队列的尾指针加1取模队列大小等于队列的头指针时，表示队列已满，返回1；否则返回0。
SQ_isempty函数用于判断队列是否为空。当队列的头指针等于尾指针时，表示队列为空，返回1；否则返回0。
SQ_push函数用于入队操作，将给定的数据data插入队列中。首先判断队列是否已满，如果已满则返回-1表示入队失败；否则将data插入队列的尾部，并更新尾指针，然后返回0表示入队成功。
SQ_pop函数用于出队操作，将队列中的数据弹出并赋值给给定的data。首先判断队列是否为空，如果为空则返回-1表示出队失败；否则将队列头部的数据赋值给data，并更新头指针，然后返回0表示出队成功。
SQ_free函数用于回收队列，释放队列的数据存储空间。首先判断队列的数据存储空间是否已分配，如果已分配则使用free函数释放内存，并将指针置为NULL；然后将队列的头尾指针重置为0。
注意：
循环队列中，需要牺牲一个存储位置来区分空队和满队
练习 3 」
构建一个顺序存储的循环队列，当用户输入数字时，将数字入队，当用户输入字母时，将队头元素 出队。每次操作队列之后，将队列中的元素显示出来。
解析： 构建循环队列要注意空队和满队的区别，比如可以让head和tail相等的时候代表空队，当tail+1再对 队列容量求余后等于head时代表满队。当然，这些逻辑都是人为规定的，我们完全可以将上述空队 和满队的判断条件对调。 使用顺序存储来实现循环队列，可以这么设计队列的管理结构体：
typedef struct{int *data; // 顺序存储内存空间int size; // 循环队列总容量int head; // 循环队列的头元素所在位置int tail; // 循环队列的尾元素所在位置
}circular_queue;
参考代码：
#include <stdio.h>#include <unistd.h>#include <stdlib.h>#include <stdbool.h>typedef struct{int *data; // 顺序存储内存空间int size; // 循环队列总容量int head; // 循环队列的头元素所在位置int tail; // 循环队列的尾元素所在位置
}circular_queue;circular_queue * init_queue(int size){circular_queue *q = malloc(sizeof(circular_queue));if(q != NULL){q->data = malloc(sizeof(int) * size);if(q->data == NULL){free(q);return NULL;}q->size = size;q->head = q->tail = 0;}printf("初始化完毕\n");return q;}bool is_empty(circular_queue *q){return q->head == q->tail;}bool is_full(circular_queue *q){return (q->tail+1)%q->size == q->head;}bool out_queue(circular_queue *q, int *loc){if(is_empty(q))return false;*loc = q->data[q->head];q->head = (q->head + 1) % q->size;return true;}bool en_queue(circular_queue *q, int data){if(is_full(q)) return false;q->data[q->tail] = data;q->tail = (q->tail + 1) % q->size;return true;}void show(circular_queue *q){if(is_empty(q))return;int i;for(i=q->head; i!=q->tail; i=(i+1)%q->size){if(i==q->head)printf("【队头】");printf("%d", q->data[i]);if((i+1)%q->size == q->tail)printf("【队尾】");printf("\t");}printf("\n");}int main(void){circular_queue *q = init_queue(10);int n, data;while(1){// 如果输入数字，则入队if(scanf("%d", &n) == 1){if(!en_queue(q, n)){printf("队列已满，入队失败.\n");continue;}}// 如果输入非数字，则出队并清空缓冲区else{while(getchar() != '\n');if(!out_queue(q, &data)){printf("队列已空，出队失败.\n");continue;}printf("【%d】已出队\n", data);}show(q);}return 0;}
这段代码是用C语言实现循环队列的操作，包括初始化队列、判断队列是否为空或满、入队和出队操作以及展示队列元素。 首先，定义了一个循环队列的结构体circular_queue，包含顺序存储内存空间data、循环队列总容量size、头元素所在位置head和尾元素所在位置tail。 接着，通过init_queue函数进行队列的初始化操作，包括动态分配内存空间和设置头尾位置。 is_empty函数和is_full函数分别判断队列是否为空和满，为空时头尾相等，满时尾的下一个位置为头。 out_queue函数实现出队操作，将头位置的元素赋值给指定变量，并将头位置后移一位。 en_queue函数实现入队操作，将元素存储在尾位置，并将尾位置后移一位。 最后，通过show函数展示队列中的元素。在循环中，如果输入是数字，则将其入队；如果是非数字，则将队列中的元素依次出队并打印。每次操作后，通过show函数展示队列当前的元素。 需要注意的是，代码中没有进行内存的释放操作，应该在程序结束时释放动态分配的内存空间。
)
