巢湖建设网站,wordpress自定义注册,网站建设综合技术,博物馆网站建设必要✨✨ 欢迎大家来到贝蒂大讲堂✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;数据结构与算法 贝蒂的主页#xff1a;Betty’s blog 1. 队列的定义
队列#xff08;queue#xff09;是一种只允许在一端进… ✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 养成好习惯先赞后看哦~ 所属专栏数据结构与算法 贝蒂的主页Betty’s blog 1. 队列的定义
队列queue是一种只允许在一端进行插入操作而在另一端进行删除操作的线性表。其严格遵循先进先出First In First Out的规则简称FIFO。 队头Front允许删除的一端又称队首。队尾Rear允许插入的一端。
2. 队列的分类
队列与栈类似实现方式有两种。一种是以数组的方式实现另一种以单链表来实现。这两种实现方式各有优劣并且都有细节需要处理。
基于单链表实现我们可以将链表的头节点与尾节点分别作为队列的队首与队尾这样我们就能用两个指针来对其进行操作。如下图 基于数组实现我们同样可以通过两个下标分别指向数组的起始与结束但这时我们就可能发现两个问题 问题一在不断出队与进队得到过程中起始下标与末尾下标都在向后移动当两个下标同时指向数组末尾时就无法再移动了并且**浪费前面大量空间**如图1 问题二为了解决上述问题我们将数组首尾相接变为循环数组。但这时又会出现一个问题那便是当队首与队尾下标指向同一个节点时这个队列到底是空还是满呢这时我们有三个解决方法 第一种牺牲一个单元来区分队空和队满这时若队列不为空让队尾下标指向队尾的下一个位置。约定以队头指针在队尾指针的下一位置作为队满的标志即Q-rear1Q-front。如图二。 第二种增设表示元素个数的数据成员 size 。这样队空的条件为 Q-size0队满的条件为 Q-sizeMaxSize。 第三种增加表示队满的数据成员flag。将flag初始化为0当队满时将其置为1。 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. 循环队
根据上述分析我们采用一个数组来实现队列其声明如下
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int QDataType;
#define MAXSIZE 50 //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct {QDataType data[MAXSIZE];int front; //头指针int rear; //尾指针
}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);//打印队列元素5. 队列的初始化
对队列声明的数据进行初始化防止随机值。
5.1. 链式队
void QueueInit(Queue* q)
{q-front NULL;q-rear NULL;q-size 0;
}5.2. 循环队
void QueueInit(Queue* q)
{q-front 0;q-rear 0;
}5.3. 复杂度分析
时间复杂度无论是链式队还是循环队列花费时间都是一个常数所以时间复杂度为O(1)。空间复杂度无论是链式队还是循环队列花费空间都是一个固定大小所以空间复杂度为O(1)。
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. 链式队
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;
}7.2. 循环队
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];
}7.3. 复杂度分析
时间复杂度无论是链式队还是循环队列花费时间都是一个常数所以时间复杂度为O(1)。空间复杂度无论是链式队还是循环队列花费空间都是一个固定大小所以空间复杂度为O(1)。
8. 队列的大小
8.1. 链式队
size_t QueueSize(Queue* q)
{return q-size;
}8.2. 循环队
求循环队列的大小我们很容易想到用Q-rear-Q-front得出队列元素个数。但是我们要考虑到一种特殊情况当队列先删除元素再添加元素时末尾下标**rear**可能循环重置如下图。 那到底该如何解决这个问题呢其实我们只需要在原来基础上加上一个MAXSIZE就行了为了使图一情况也适用我们仍需模上一个MAXSIZE。
size_t QueueSize(Queue*q)
{assert(q);return (q-rear - q-front MAXSIZE) % MAXSIZE;
}8.3. 复杂度分析
时间复杂度无论是链式队还是循环队列花费时间都是一个常数所以时间复杂度为O(1)。空间复杂度无论是链式队还是循环队列花费空间都是一个固定大小所以空间复杂度为O(1)。
9. 入队
9.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;
}9.2. 循环队
为了使循环队列在插入数据时实现循环操作我们可以每次进行取模操作。
void QueuePush(Queue* q, QDataType x)
{assert(q);q-data[q-rear] x; q-rear (q-rear 1) % MAXSIZE; //rear指针向后移一位置若到最后则转到数组头部
}9.3. 复杂度分析
时间复杂度无论是链式队还是循环队列花费时间都是一个常数所以时间复杂度为O(1)。空间复杂度无论是链式队还是循环队列花费空间都是一个固定大小所以空间复杂度为O(1)。
10. 出队
10.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--;
}10.2. 循环队
同样为了实现循环我们可以进行取模操作。 void QueuePop(Queue* q){assert(q);assert(!QueueEmpty(q));q-front (q-front 1) % MAXSIZE; //front指针向后移一位置若到最后则转到数组头部}10.3. 复杂度分析
时间复杂度无论是链式队还是循环队列花费时间都是一个常数所以时间复杂度为O(1)。空间复杂度无论是链式队还是循环队列花费空间都是一个固定大小所以空间复杂度为O(1)。
11. 打印队列
11.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);
}11.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);}11.3. 复杂度分析
时间复杂度无论是链式队还是循环队列花费时间都是一个常数所以时间复杂度为O(1)。空间复杂度无论是链式队还是循环队列花费空间都是一个固定大小所以空间复杂度为O(1)。
12. 销毁队列
12.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;
}12.2. 循环队
循环队列是以数组作为存储空间并不是动态内存开辟的空间所以并不需要手动释放空间。
12.3. 复杂度分析
时间复杂度无论是链式队还是循环队列花费时间都是一个常数所以时间复杂度为O(1)。空间复杂度链式队花费空间都是一个固定大小所以空间复杂度为O(1)。
13. 链式队与循环队列的对比与应用
13.1. 对比
对比项链式队循环队列时间效率因为存在头指针与尾指针所以链式队的出队与入队的时间都相对较小。循环队列是基于数组实现的支持下标的随机访问所以时间消耗也并不大空间效率链式队每次入队都需固定创造一个新的节点空间利用率较高较稳定。循环队列的空间是固定的可能会造成空间的浪费。
13.2. 应用
队列的应用与栈一样十分广泛 当我们去食堂扫码订餐时你的订单就会加入一个队列中。在操作系统中队列可以用来管理任务进度与进程切换。 14. 完整代码
14.1. 链式队
14.1.1. Queue.h
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.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);//销毁队列14.1.2. Queue.c
#includeQueue.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;
}14.2. 循环队列
14.2.1. Queue.h
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int QDataType;
#define MAXSIZE 50 //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct {QDataType data[MAXSIZE];int front; //头指针int rear; //尾指针
}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);//打印队列元素14.2.2. Queue.c
void QueueInit(Queue* q)
{q-front 0;q-rear 0;
}
bool QueueEmpty(Queue*q)
{assert(q);return q-front q-rear;
}
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];
}
size_t QueueSize(Queue*q)
{assert(q);return (q-rear - q-front MAXSIZE) % MAXSIZE;
}
void QueuePush(Queue* q, QDataType x)
{assert(q);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);}
