探索数据结构：链式队与循环队列的模拟、实现与应用-Toy模板网

这篇具有很好参考价值的文章主要介绍了探索数据结构：链式队与循环队列的模拟、实现与应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 队列的定义

队列（queue）是一种只允许在一端进行插入操作，而在另一端进行删除操作的线性表。其严格遵循先进先出（First In First Out）的规则，简称FIFO。

探索数据结构：链式队与循环队列的模拟、实现与应用,数据结构与算法：C/C++全解析,数据结构,c语言,循环队列,链式队列,队列的应用,学习

队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。

2. 队列的分类

队列与栈类似，实现方式有两种。一种是以数组的方式实现，另一种以单链表来实现。这两种实现方式各有优劣，并且都有细节需要处理。

基于单链表实现：我们可以将链表的头节点与尾节点分别作为队列的队首与队尾，这样我们就能用两个指针来对其进行操作。如下图：

探索数据结构：链式队与循环队列的模拟、实现与应用,数据结构与算法：C/C++全解析,数据结构,c语言,循环队列,链式队列,队列的应用,学习

基于数组实现：我们同样可以通过两个下标分别指向数组的起始与结束，但这时我们就可能发现两个问题：

问题一：在不断出队与进队得到过程中，起始下标与末尾下标都在向后移动，当两个下标同时指向数组末尾时就无法再移动了，并且**浪费前面大量空间，**如图1
问题二：为了解决上述问题，我们将数组首尾相接变为循环数组。但这时又会出现一个问题，那便是当队首与队尾下标指向同一个节点时，这个队列到底是空还是满呢？这时我们有三个解决方法
第一种：牺牲一个单元来区分队空和队满，这时若队列不为空，让队尾下标指向队尾的下一个位置。约定以队头指针在队尾指针的下一位置作为队满的标志，即Q->rear+1==Q->front。如图二。
第二种：增设表示元素个数的数据成员 size 。这样，队空的条件为 Q->size==0；队满的条件为 Q->size==MaxSize。
第三种：增加表示队满的数据成员flag。将flag初始化为0，当队满时将其置为1。

探索数据结构：链式队与循环队列的模拟、实现与应用,数据结构与算法：C/C++全解析,数据结构,c语言,循环队列,链式队列,队列的应用,学习

3. 队列的功能

队列的初始化。

判断队列是否为空。

判断队列是否满了。

返回队头与队尾的元素。

返回队列的大小。

入队与出队。

打印队列的元素。

销毁队列。

4. 队列的声明

4.1. 链式队

链式队的声明十分简单，参照上面图我们就可以直接实现了。

typedef int QDataType;
typedef struct QueueNode 
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue 
{
	QNode* front;
	QNode* rear;
	size_t size;
}Queue;

4.2. 循环队

根据上述分析，我们采用一个数组来实现队列，其声明如下

typedef int QDataType;
#define MAXSIZE 50  //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct {
    QDataType *data;
    int front;  //头指针
    int rear;   //尾指针
}Queue;

5. 队列的初始化

对队列声明的数据进行初始化，防止随机值。

5.1. 链式队

void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

5.2. 循环队

void QueueInit(Queue* q) 
{
    q->data = (QDataType*)malloc(sizeof(QDataType )* MAXSIZE);
	if (q->data == NULL)
	{
		perror("malloc fail:");
		return;
	}
    q->front = 0;
    q->rear = 0;
}

5.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：链式队空间是一个固定大小，空间复杂度为O(1)。而需要开辟整个队列的大小，空间复杂度为O(N)。

6. 判断队列是否为空

判断队列是否为空十分简单，这里就不在赘述。

6.1. 链式队

bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->front == NULL) && (q->rear == NULL);
}

6.2. 循环队

bool QueueEmpty(Queue*q)
{
    assert(q);
    return q->front == q->rear;
}

6.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

7. 判断队列是否为满

7.1. 链式队

链式队不需要判断是否为满的情况。

7.2. 循环队

为了完成循环操作，需要对其进行取模操作，防止越界。

bool QueueFull(Queue*q)
{
    assert(q);
    return q->front == (q->rear+1)%MAXSIZE;
}

7.3. 复杂度分析

时间复杂度：循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

8. 返回队头与队尾元素

因为定义了头指针与尾指针，所以访问数据也十分方便。

8.1. 链式队

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}

8.2. 循环队

rear下标可能指向下标0，这时贸然减一就可能出现越界的情况。为了解决这个问题我们可以加上MAXSIZE再对其取模。

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[q->front];
}
QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[(q->rear-1+MAXSIZE)%MAXSIZE];
}

8.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

9. 队列的大小

9.1. 链式队

size_t QueueSize(Queue* q)
{
	return q->size;
}

9.2. 循环队

求循环队列的大小，我们很容易想到用Q->rear-Q->front得出队列元素个数。但是我们要考虑到一种特殊情况：当队列先删除元素再添加元素时，末尾下标**rear**可能循环重置，如下图。

探索数据结构：链式队与循环队列的模拟、实现与应用,数据结构与算法：C/C++全解析,数据结构,c语言,循环队列,链式队列,队列的应用,学习

那到底该如何解决这个问题呢？其实我们只需要在原来基础上加上一个MAXSIZE就行了，为了使图一情况也适用我们仍需模上一个MAXSIZE。

size_t QueueSize(Queue*q) 
{
    assert(q);
    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}

9.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

10. 入队

10.1. 链式队

链式队列入队时需要判断队列是否为空的特殊情况，如果是则还需要将尾指针也指向这个节点。

void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	if (q->front == NULL)
	{
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}

10.2. 循环队

为了使循环队列在插入数据时实现循环操作，我们可以每次进行取模操作。并且每次入队之前要检查循环队是否已满。

void QueuePush(Queue* q, QDataType x) 
{
    assert(q);
    if(QueueFull)
    {
        printf("队列已满\n");
        return ;
    }
    q->data[q->rear] = x;   
    q->rear = (q->rear + 1) % MAXSIZE;  //rear指针向后移一位置，若到最后则转到数组头部
}

10.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

11. 出队

11.1. 链式队

同样考虑特殊情况，防止队列为空。并且当队列只有一个节点时需要将头指针与尾指针都置为空。

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	//1.只有一个结点
	if (q->front == q->rear)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	//2.有多个结点
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
		del = NULL;
	}
	q->size--;
}

11.2. 循环队

同样为了实现循环，我们可以进行取模操作。

 void QueuePop(Queue* q)
 {
     assert(q);
     assert(!QueueEmpty(q));
    q->front = (q->front + 1) % MAXSIZE;    //front指针向后移一位置，若到最后则转到数组头部
 }

11.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

12. 打印队列

12.1. 链式队

void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	QNode* tail = q->rear;
	printf("队头->");
	while (cur != tail->next)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("队尾\n");
}

12.2. 循环队

 void QueuePrint(Queue* q)
 {
     assert(q);
     int cur = q->front;
     printf("队头->");
     while (cur != q->rear)
     {
         printf("%d->", q->data[cur]);
         cur = (cur + 1) % MAXSIZE;
     }
     printf("队尾\n");
 }

12.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

13. 销毁队列

13.1. 链式队

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	q->front = q->rear = NULL;
}

13.2. 循环队

void QueueDestroy(Deque* q)//销毁队列
{
	assert(q);
	free(q->data);
	q->data = NULL;
	q->front = q->rear = 0;
}

13.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

14. 链式队与循环队列的对比与应用

14.1. 对比

对比项	链式队	循环队列
时间效率	因为存在头指针与尾指针，所以链式队的出队与入队的时间都相对较小。	循环队列是基于数组实现的，支持下标的随机访问，所以时间消耗也并不大
空间效率	链式队每次入队都需固定创造一个新的节点，空间利用率较高，较稳定。	循环队列的空间是固定的，可能会造成空间的浪费。

14.2. 应用

队列的应用与栈一样，十分广泛文章来源地址https://www.toymoban.com/news/detail-844261.html

当我们去食堂扫码订餐时，你的订单就会加入一个队列中。

在操作系统中，队列可以用来管理任务进度与进程切换。

15. 完整代码

15.1. 链式队

15.1.1. Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode 
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue 
{
	QNode* front;
	QNode* rear;
	size_t size;
}Queue;
void QueueInit(Queue* q);//初始化队列
bool QueueEmpty(Queue* q);//判断是否为空
QDataType QueueFront(Queue* q);//获取队头元素
QDataType QueueBack(Queue* q);//或许队尾元素
size_t QueueSize(Queue* q);//或许队列长度
void QueuePush(Queue* q, QDataType x);//入队
void QueuePop(Queue* q);//出队
void QueuePrint(Queue* q);//打印队列元素
void QueueDestroy(Queue* q);//销毁队列

15.1.2. Queue.c

#include"Queue.h"
void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->front == NULL) && (q->rear == NULL);
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}
size_t QueueSize(Queue* q)
{
	return q->size;
}
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	if (q->front == NULL)
	{
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	//1.只有一个结点
	if (q->front == q->rear)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	//2.有多个结点
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
		del = NULL;
	}
	q->size--;
}
void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	QNode* tail = q->rear;
	printf("队头->");
	while (cur != tail->next)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("队尾\n");
}
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	q->front = q->rear = NULL;
}

15.2. 循环队列

15.2.1. Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
#define MAXSIZE 50  //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct {
    QDataType *data;
    int front;  //头指针
    int rear;   //尾指针
}Queue;

void QueueInit(Queue* q);//初始化队列
bool QueueEmpty(Queue* q);//判断是否为空
bool QueueFull(Queue*q);//判断队列是否满
QDataType QueueFront(Queue* q);//获取队头元素
QDataType QueueBack(Queue* q);//或许队尾元素
size_t QueueSize(Queue* q);//或许队列长度
void QueuePush(Queue* q, QDataType x);//入队
void QueuePop(Queue* q);//出队
void QueuePrint(Queue* q);//打印队列元素

15.2.2. Queue.c

void QueueInit(Queue* q) 
{
    q->data = (QDataType*)malloc(sizeof(QDataType )* MAXSIZE);
	if (q->data == NULL)
	{
		perror("malloc fail:");
		return;
	}
    q->front = 0;
    q->rear = 0;
}
bool QueueEmpty(Queue*q)
{
    assert(q);
    return q->front == q->rear;
}
bool QueueFull(Queue*q)
{
    assert(q);
    return q->front == (q->rear+1)%MAXSIZE;
}
QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[q->front];
}
QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[(q->rear-1+MAXSIZE)%MAXSIZE];
}
size_t QueueSize(Queue*q) 
{
    assert(q);
    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
void QueuePush(Queue* q, QDataType x) 
{
    assert(q);
    if(QueueFull)//判断队列是否满了
    {
        printf("队列已满\n");
        return ;
    }
    q->data[q->rear] = x;   
    q->rear = (q->rear + 1) % MAXSIZE;  //rear指针向后移一位置，若到最后则转到数组头部
}
 void QueuePop(Queue* q)
 {
     assert(q);
     assert(!QueueEmpty(q));
    q->front = (q->front + 1) % MAXSIZE;    //front指针向后移一位置，若到最后则转到数组头部
 }
 void QueuePrint(Queue* q)
 {
     assert(q);
     int cur = q->front;
     printf("队头->");
     while (cur != q->rear)
     {
         printf("%d->", q->data[cur]);
         cur = (cur + 1) % MAXSIZE;
     }
     printf("队尾\n");
 }
void QueueDestroy(Deque* q)//销毁队列
{
	assert(q);
	free(q->data);
	q->data = NULL;
	q->front = q->rear = 0;
}

到了这里，关于探索数据结构：链式队与循环队列的模拟、实现与应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

探索数据结构：链式队与循环队列的模拟、实现与应用

1. 队列的定义

2. 队列的分类

3. 队列的功能

4. 队列的声明

4.1. 链式队

4.2. 循环队

5. 队列的初始化

5.1. 链式队

5.2. 循环队

5.3. 复杂度分析

6. 判断队列是否为空

6.1. 链式队

6.2. 循环队

6.3. 复杂度分析

7. 判断队列是否为满

7.1. 链式队

7.2. 循环队

7.3. 复杂度分析

8. 返回队头与队尾元素

8.1. 链式队

8.2. 循环队

8.3. 复杂度分析

9. 队列的大小

9.1. 链式队

9.2. 循环队

9.3. 复杂度分析

10. 入队

10.1. 链式队

10.2. 循环队

10.3. 复杂度分析

11. 出队

11.1. 链式队

11.2. 循环队

11.3. 复杂度分析

12. 打印队列

12.1. 链式队

12.2. 循环队

12.3. 复杂度分析

13. 销毁队列

13.1. 链式队

13.2. 循环队

13.3. 复杂度分析

14. 链式队与循环队列的对比与应用

14.1. 对比

14.2. 应用

15. 完整代码

15.1. 链式队

15.1.1. Queue.h

15.1.2. Queue.c

15.2. 循环队列

15.2.1. Queue.h

15.2.2. Queue.c

相关文章

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

支付宝扫一扫打赏

微信扫一扫打赏

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

二维码1

二维码2