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

这篇具有很好参考价值的文章主要介绍了C语言队列（循环队列和链队初始化进出队等基本操作）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

一、队列的定义

二、循环队列

1、循环队列的储存结构

2、初始化

3、输出队列元素

4、入队

5、出队

6、取队头元素

7、求队列长度

8、源代码

三、链式队列

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

2、初始化

3.输出队列元素

4.入队

5.出队

6.取队头元素

7. 源代码

总结

一、队列的定义

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

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

链队列的入队和出队,数据结构与算法,c语言,数据结构

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

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

队列基本操作有：

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

二、循环队列

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

链队列的入队和出队,数据结构与算法,c语言,数据结构

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;//尾指针加1
	return true;
}

示例

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

链队列的入队和出队,数据结构与算法,c语言,数据结构

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;//头指针加1
	return true;
}

示例

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

链队列的入队和出队,数据结构与算法,c语言,数据结构

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 <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
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;//尾指针加1
	return 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;//头指针加1
	return 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);
}

三、链式队列

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

链队列的入队和出队,数据结构与算法,c语言,数据结构

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

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

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个元素入队，最后输出队列。

运行结果如下

链队列的入队和出队,数据结构与算法,c语言,数据结构

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;
}

示例

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

运行结果如下

链队列的入队和出队,数据结构与算法,c语言,数据结构

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 <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
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;
}

总结

链队列的入队和出队,数据结构与算法,c语言,数据结构文章来源地址https://www.toymoban.com/news/detail-734501.html

到了这里，关于C语言队列（循环队列和链队初始化进出队等基本操作）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

一、队列的定义

二、循环队列

1、循环队列的储存结构

2、初始化

3、输出队列元素

4、入队

5、出队

6、取队头元素

7、求队列长度

8、源代码

三、链式队列

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

2、初始化

3.输出队列元素

4.入队

5.出队

6.取队头元素

7. 源代码

总结

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

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

一、队列的定义

二、循环队列

1、 循环队列的储存结构

2、初始化

3、输出队列元素

4、入队

5、出队

6、取队头元素

7、求队列长度

8、源代码

三、链式队列

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

2、初始化

3.输出队列元素

4.入队

5.出队

6.取队头元素

7. 源代码

总结

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

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

1、循环队列的储存结构