C语言 队列（循环队列和链队初始化进出队等基本操作）

目录

一、队列的定义

二、循环队列

1、循环队列的储存结构

2、初始化

3、输出队列元素

4、入队

5、出队

6、取队头元素

7、求队列长度

8、源代码

三、链式队列

1、队列的链式存储结构表示

2、初始化

3.输出队列元素

4.入队

5.出队

6.取队头元素

7. 源代码

总结

---

一、队列的定义

队列（Queue）是一种先进先出（FIFO，First-In-First-Out）的线性表。

在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。这和日常生活中的排队时一致的，最早进入队列的元素最早离开。

常见队列有三种：循环队列、链式队列、双端队列。

双端队列又名double ended queue，简称deque，是队列的一种变形，双端队列没有队列和栈这样的限制级，它允许两端进行入队和出队操作，也就是说元素可以从队头出队和入队，也可以从队尾出队和入队

队列基本操作有：

• 初始化队列：InitQueue（Q）
• 判断队列是否为空：IsEmpty（Q）
• 判断队列是否已满：IsFull（Q）
• 入队操作：EnterQueue（Q，data）
• 出队操作：DeleteQueue（Q，&data）
• 取队首元素：GetHead（Q，&data）
• 清空队列：ClearQueue(&Q)

二、循环队列

循环队列其实就是将数组的首尾相连，组成的一个特殊结构。头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1″的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。

1、循环队列的储存结构

typedef struct {int* base;//储存空间的基地址int front;//头指针int rear;//尾指针int maxsize;//队列最大长度}SqQueue;

2、初始化

动态分配一个大小为size的数组空间，base指向数组空间首地址。

SqQueue* InitQueue(int size) {SqQueue* Q = malloc(sizeof(SqQueue));//先创建队列结构体指针Q->base = (int*)malloc(sizeof(int) * size);//为队列分配一个最大容量为size的数组空间//队列最大长度置为size，头指针尾指针置为0，队列为空Q->maxsize = size;Q->front = 0;Q->rear = 0;return Q;}

3、输出队列元素

void print(SqQueue* Q) {printf("(front) ");int i;//跟遍历数组差不多，就是要通过模运算防止越界for (i = Q->front; i != Q->rear; i = (i + 1) % Q->maxsize) {printf("%d ", Q->base[i]);}printf("(rear)\n");}

4、入队

入队指在队尾插入一个新元素。

bool EnQueue(SqQueue* Q, int e) {//插入e作为新队尾元素if ((Q->rear + 1) % Q->maxsize == Q->front)return false;//尾指针在循环意义上加1后等于头指针说明队满Q->base[Q->rear] = e;//将元素e插入队尾Q->rear = (Q->rear + 1) % Q->maxsize;//尾指针加1return true;}

示例

初始化一个最大长度为5的队列，用循环将四个元素入队 ，最后输出。

5、出队

出队指将队头元素删除

bool DeQueue(SqQueue* Q, int* e) {//删除队头元素，用e返回其值if (Q->front == Q->rear)return false;//队空*e = Q->base[Q->front];//用e保存队头元素Q->front = (Q->front + 1) % Q->maxsize;//头指针加1return true;}

示例

接着入队示例，出队三个元素，再入队两个元素，最后输出。

6、取队头元素

bool GetHead(SqQueue* Q, int* e) {//返回队头元素，不修改头指针if (Q->front == Q->rear)return false;//队空*e = Q->base[Q->front];return true;}

7、求队列长度

对于非循环队列，尾指针与头指针的差值就是队列长度；但是循环队列差值可能为负数，所以需要将差值加上maxsize再与maxsize求余。

int QueueLength(SqQueue* Q) {//返回队列元素个数return (Q->rear - Q->front + Q->maxsize) % Q->maxsize;}

8、源代码

#define _CRT_SECURE_NO_WARNINGS 1#include #include #include typedef struct {int* base;//储存空间的基地址int front;//头指针int rear;//尾指针int maxsize;//队列最大长度}SqQueue;//初始化SqQueue* InitQueue(int size) {SqQueue* Q = malloc(sizeof(SqQueue));//先创建队列结构体指针Q->base = (int*)malloc(sizeof(int) * size);//为队列分配一个最大容量为size的数组空间//队列最大长度置为size，头指针尾指针置为0，队列为空Q->maxsize = size;Q->front = 0;Q->rear = 0;return Q;}//输出void print(SqQueue* Q) {printf("(front) ");int i;//跟遍历数组差不多，就是要通过模运算防止越界for (i = Q->front; i != Q->rear; i = (i + 1) % Q->maxsize) {printf("%d ", Q->base[i]);}printf("(rear)\n");}//入队bool EnQueue(SqQueue* Q, int e) {//插入e作为新队尾元素if ((Q->rear + 1) % Q->maxsize == Q->front)return false;//尾指针在循环意义上加1后等于头指针说明队满Q->base[Q->rear] = e;//将元素e插入队尾Q->rear = (Q->rear + 1) % Q->maxsize;//尾指针加1return true;}//出队bool DeQueue(SqQueue* Q, int* e) {//删除队头元素，用e返回其值if (Q->front == Q->rear)return false;//队空*e = Q->base[Q->front];//用e保存队头元素Q->front = (Q->front + 1) % Q->maxsize;//头指针加1return true;}//取队头元素bool GetHead(SqQueue* Q, int* e) {//返回队头元素，不修改头指针if (Q->front == Q->rear)return false;//队空*e = Q->base[Q->front];return true;}//求队列长度int QueueLength(SqQueue* Q) {//返回队列元素个数return (Q->rear - Q->front + Q->maxsize) % Q->maxsize;}int main() {int i, n, e;SqQueue* Q = InitQueue(5);for (scanf("%d", &n), i = 0; i < n; i++) {scanf("%d", &e);EnQueue(Q, e);}print(Q);DeQueue(Q, &e);printf("e=%d\n", e);DeQueue(Q, &e);printf("e=%d\n", e);DeQueue(Q, &e);printf("e=%d\n", e);for (scanf("%d", &n), i = 0; i < n; i++) {scanf("%d", &e);EnQueue(Q, e);}print(Q);}

三、链式队列

链队列是指采用链式存储结构实现的队列。通常链队列用单链表来表示。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队列添加一个头结点，并令头指针始终指向头结点。

当然也有用单向循环链表表示的队列,与单链表不同的是尾节点指向了头结点，所以只需

一个指针指向尾结点就可以实现基本操作。

1、队列的链式存储结构表示

typedef struct {int data;struct QNode* next;}QNode;typedef struct {QNode* front;//队头指针QNode* rear;//队尾指针}LinkQueue;

2、初始化

链队的初始化操作就是构造一个只有一个头结点的空队。

LinkQueue* InitQueue() {LinkQueue* Q = malloc(sizeof(LinkQueue));//生成队头队尾指针Q->front = (QNode*)malloc(sizeof(QNode));//生成新结点作为头结点，队头队尾指针指向该结点Q->rear = Q->front;Q->front->next = NULL;//头结点指针域置空return Q;}

3.输出队列元素

跟遍历链表一样，就是要判断队是否为空。

void print(LinkQueue *Q) {//前提为队不为空printf("(front) ");if (Q->front != Q->rear) {QNode* p = Q->front->next;while (p != NULL) {printf("%d ", p->data);p = p->next;}}printf("(rear)\n");}

4.入队

链队入队不需要判断队满，只需为入队元素动态分配一个结点空间。

void EnQueue(LinkQueue* Q, int e) {QNode* p = malloc(sizeof(QNode));//生成新结点p->data = e;//新结点数据域置为e，指针域置空p->next = NULL;Q->rear->next = p;//新结点插入队尾Q->rear = p;//修改队尾指针}

示例

用循环将5个元素入队，最后输出队列。

运行结果如下

5.出队

需要判断队是否为空，出队后可释放队头元素空间。

bool DeQueue(LinkQueue* Q, int* e) {//删除队头元素，用e返回其值if (Q->front == Q->rear)return false;//判断队列是否为空QNode* p = Q->front->next;//p指向队头元素*e = p->data;//e保存队头元素Q->front->next = p->next;//修改头结点指针域if (Q->rear == p)Q->rear = Q->front;//最后一个元素被删，队尾指针指向头结点free(p);//释放队头元素空间return true;}

示例

接着入队示例，出队一个元素并输出，最后输出队列

运行结果如下

6.取队头元素

bool GetHead(LinkQueue* Q, int* e) {//返回队头元素，不修改队头指针if (Q->front == Q->rear)return false;//判断队列是否为空QNode* p = Q->front->next;*e =p->data;//用e返回队头元素值return true;}

7. 源代码

#define _CRT_SECURE_NO_WARNINGS 1#include #include #include typedef struct {int data;struct QNode* next;}QNode;typedef struct {QNode* front;//队头指针QNode* rear;//队尾指针}LinkQueue;//初始化LinkQueue* InitQueue() {LinkQueue* Q = malloc(sizeof(LinkQueue));//生成队头队尾指针Q->front = (QNode*)malloc(sizeof(QNode));//生成新结点作为头结点，队头队尾指针指向该结点Q->rear = Q->front;Q->front->next = NULL;//头结点指针域置空return Q;}//入队void EnQueue(LinkQueue* Q, int e) {QNode* p = malloc(sizeof(QNode));//生成新结点p->data = e;//新结点数据域置为e，指针域置空p->next = NULL;Q->rear->next = p;//新结点插入队尾Q->rear = p;//修改队尾指针}//出队bool DeQueue(LinkQueue* Q, int* e) {//删除队头元素，用e返回其值if (Q->front == Q->rear)return false;//判断队列是否为空QNode* p = Q->front->next;//p指向队头元素*e = p->data;//e保存队头元素Q->front->next = p->next;//修改头结点指针域if (Q->rear == p)Q->rear = Q->front;//最后一个元素被删，队尾指针指向头结点free(p);//释放队头元素空间return true;}//取队头元素bool GetHead(LinkQueue* Q, int* e) {//返回队头元素，不修改队头指针if (Q->front == Q->rear)return false;//判断队列是否为空QNode* p = Q->front->next;*e = p->data;//用e返回队头元素值return true;}//输出void print(LinkQueue* Q) {//前提为队不为空printf("(front) ");if (Q->front != Q->rear) {QNode* p = Q->front->next;while (p != NULL) {printf("%d ", p->data);p = p->next;}}printf("(rear)\n");}int main() {LinkQueue* Q = InitQueue();int i, n, e;scanf("%d", &n);for (i = 0; i < n; i++) {scanf("%d", &e);EnQueue(Q, e);}print(Q);DeQueue(Q, &e);printf("%d\n", e);print(Q);return 0;}

总结