盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

队列结构详解（顺序/链式队列、循环队列、优先队列、高并发WEB服务队列）（C/C++）_链式排队器的优先级

作者：盐析白兔 | 2024-05-08 00:02:03

踩

链式排队器的优先级

3.5高并发WEB服务器队列的应用

一、队列的原理精讲

队列是一种受限的线性表， (Queue)，它是一种运算受限的线性表,先进先出(FIFO First In First Out)

队列是一种受限的线性结构
它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
生活中队列场景随处可见: 比如在电影院, 商场, 或者厕所排队.......

二、队列算法实现

2.1顺序存储

采用数组来保存队列的元素，设立一个队首指针 front ，一个队尾指针 rear，分别指向队首和队尾元素。则rear-front 即为存储的元素个数！


#define MaxSize 5 //队列的最大容量
 
typedef int DataType; //队列中元素类型
 
typedef struct Queue{
	DataType queue[MaxSize];
	int front; //队头指针
	int rear; //队尾指针
}SeqQueue;

队列初始化


 
//队列初始化，将队列初始化为空队列
void InitQueue(SeqQueue* SQ){
	if (!SQ) return;
	SQ->front = SQ->rear = 0; //把对头和队尾指针同时置 0
}

队列为空


//判断队列为空
int IsEmpty(SeqQueue* SQ){
	if (!SQ) return 0;
	if (SQ->front == SQ->rear){
		return 1;
	}
	return 0;
}

队列为满


//判断队列是否为满
int IsFull(SeqQueue* SQ){
	if (!SQ) return 0;
	if (SQ->rear == MaxSize){
		return 1;
	}
	return 0;
}

入队：将新元素插入 rear 所指的位置，然后 rear 加 1。


//入队,将元素 data 插入到队列 SQ 中
int EnterQueue(SeqQueue* SQ, DataType data) {
	if (!SQ) return 0;
	if (IsFull(SQ)) {
		cout << "无法插入元素 " << data << ", 队列已满!" << endl;
		return 0;
	}
	SQ->queue[SQ->rear] = data; //在队尾插入元素 data
	SQ->rear++; //队尾指针后移一位
	return 1;
}

打印队列中的元素


//打印队列中的各元素
void PrintQueue(SeqQueue* SQ){
	if (!SQ) return;
	int i = SQ->front;
	while (i < SQ->rear){
		//setw() 用于控制输出之间的间隔，setw(4)可以使前后输出间隔4字符，头文件#include <iomanip>
		cout << setw(4) << SQ->queue[i];
		i++;
	}
	cout << endl;
}

//setw() 用于控制输出之间的间隔，setw(4)可以使前后输出间隔4字符，头文件#include <iomanip>。

出队：方式 1 —— 删除 front 所指的元素, 后面所有元素前移 1 并返回被删除元素。


 
//出队，将队列中队头的元素 data 出队，后面的元素向前移动
int DeleteQueue(SeqQueue* SQ, DataType* data) {
	if (!SQ || IsEmpty(SQ)) {
		cout << "队列为空！" << endl;
		return 0;
	}
	if (!data) return 0;
	*data = SQ->queue[SQ->front];
	for (int i = SQ->front + 1; i < SQ->rear; i++) {//移动后面的元素
		SQ->queue[i - 1] = SQ->queue[i];
	}
	SQ->rear--;//队尾指针前移一位
	return 1;
}

出队：方式 2 —— 删除 front 所指的元素，然后加 1 并返回被删元素。


//出队，将队列中队头的元素 data 出队，出队后队头指针 front 后移一位
int DeleteQueue2(SeqQueue* SQ, DataType* data){
	if (!SQ || IsEmpty(SQ)){
		cout << "队列为空！" << endl;
		return 0;
	}
	if (SQ->front >= MaxSize) {
		cout << "队列已到尽头!" << endl;
		return 0;
	}
	*data = SQ->queue[SQ->front]; //出队元素值
	SQ->front = (SQ->front) + 1; //队首指针后移一位
	return 1;
}

取队首元素：返回 front 指向的元素值


//获取队首元素
int GetHead(SeqQueue* SQ, DataType* data){
	if (!SQ || IsEmpty(SQ)){
		cout << "队列为空!" << endl;
	}
	return *data = SQ->queue[SQ->front];
}

清空队列


//清空队列
void ClearQueue(SeqQueue* SQ){
	SQ->front = SQ->rear = 0;
}

顺序队列文章结尾有完整代码~

2.2链式存储

队列的链式存储结构，其实就是线性表的单链表，只不过它只是尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点。


typedef int DataType; //队列中元素类型
 
typedef struct _QNode { //结点结构
	DataType data;
	struct _QNode* next;
}QNode;
 
typedef QNode* QueuePtr;
 
typedef struct Queue{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;

链式队列操作图示
空队列时，front 和 rear 都指向空。

删除节点

链式队列文章结尾有完整代码~

三、队列实际开发应用案例

3.1线程池中的任务队列

线程池 —— 由一个任务队列和一组处理队列的线程组成。一旦工作进程需要处理某个可能“阻塞”的操作，不用自己操作，将其作为一个任务放到线程池的队列，接着会被某个空闲线程提取处理。


typedef struct _QNode { //结点结构
	int id;
	void (*handler)();
	struct _QNode* next;
}QNode;
 
typedef QNode* QueuePtr;
 
typedef struct Queue{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;

线程池中的任务队列文章结尾有完整代码~

3.2循坏队列

在队列的顺序存储中，采用出队方式 2, 删除 front 所指的元素，然后加 1 并返回被删元素。这样可以避免元素移动，但是也带来了一个新的问题“假溢出”。

能否利用前面的空间继续存储入队呢？采用 循环队列

循环队列入队, 队尾循环后移： SQ->rear =（SQ->rear+1）%Maxsize;
循环队列出队, 队首循环后移： SQ->front =（SQ->front+1）%Maxsize;
队空：SQ.front=SQ.rear; // SQ.rear 和 SQ.front 指向同一个位置
队满： (SQ.rear+1) %Maxsize=SQ.front; // SQ.rear 向后移一位正好是 SQ.front

计算元素个数:
可以分两种情况判断：
如果 SQ.rear>= SQ.front：元素个数为 SQ.rear-SQ.front；
如果 SQ.rear<SQ.front：元素个数为 SQ.rear-SQ.front+ Maxsize；
采用取模的方法把两种情况统一为：(SQ.rear-SQ.front+Maxsize)% Maxsize

循环队列文章结尾有完整代码

3.3优先队列

英雄联盟游戏里面防御塔都有一个自动攻击功能，小兵排着队进入防御塔的攻击范围，防御塔先攻击靠得最近的小兵，这时候大炮车的优先级更高（因为系统判定大炮车对于防御塔的威胁大），所以防御塔会优先攻击大炮车。而当大炮车阵亡，剩下的全部都是普通小兵，这时候离得近的优先级越高，防御塔优先攻击距离更近的小兵。

优先队列：它的入队顺序没有变化，但是出队的顺序是根据优先级的高低来决定的。优先级高的
优先出队。


typedef int DataType; //队列中元素类型
typedef struct _QNode { //结点结构
	int priority; //每个节点的优先级,9 最高优先级，0 最低优先级，优先级相同，取第一个节点
	DataType data;
	struct _QNode* next;
}QNode;
 
typedef QNode* QueuePtr;
typedef struct Queue
{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;

空的任务队列 & 插入元素

删除一个节点

优先队列出队

优先队列文章结尾有完整代码~

3.4动态队列

使用链表动态存储的队列即为动态顺序队列~前面已经实现，故不再重复！

3.5高并发WEB服务器队列的应用

在高并发 HTTP 反向代理服务器 Nginx 中，存在着一个跟性能息息相关的模块 - 文件缓存。

经常访问到的文件会被 nginx 从磁盘缓存到内存，这样可以极大的提高 Nginx 的并发能力，不过因为内存的限制，当缓存的文件数达到一定程度的时候就会采取淘汰机制，优先淘汰进入时间比较久或是最近访问很少(LRU)的队列文件。

具体实现方案：

1. 使用双向循环队列保存缓存的文件节点，这样可以实现多种淘汰策略：
比如：如果采用淘汰进入时间比较久的策略，就可以使用队列的特性，先进先出
如果要采用按照 LRU，就遍历链表，找到节点删除。

源码实现

nginx_queue.h


#ifndef _NGX_QUEUE_H_INCLUDED_
#define _NGX_QUEUE_H_INCLUDED_
typedef struct ngx_queue_s ngx_queue_t;
struct ngx_queue_s {
	ngx_queue_t* prev;
	ngx_queue_t* next;
};
#define ngx_queue_init(q) \
	(q)->prev = q; \
	(q)->next = q
#define ngx_queue_empty(h) \
	(h == (h)->prev)
#define ngx_queue_insert_head(h, x) \
	(x)->next = (h)->next; \
	(x)->next->prev = x; \
	(x)->prev = h; \
	(h)->next = x
#define ngx_queue_insert_after ngx_queue_insert_head
#define ngx_queue_insert_tail(h, x) \
	(x)->prev = (h)->prev; \
	(x)->prev->next = x; \
	(x)->next = h; \
	(h)->prev = x
#define ngx_queue_head(h) \
	(h)->next
#define ngx_queue_last(h) \
	(h)->prev
 
#define ngx_queue_sentinel(h) \
	(h)
#define ngx_queue_next(q) \
	(q)->next
#define ngx_queue_prev(q) \
	(q)->prev
#define ngx_queue_remove(x) \
	(x)->next->prev = (x)->prev; \
	(x)->prev->next = (x)->next
#define ngx_queue_data(q, type, link) \
	(type *) ((char *) q - offsetof(type, link))
#endif

Nginx_双向循环队列.cpp


#include <Windows.h>
#include <stdlib.h>
#include <iostream>
#include "nginx_queue.h"
#include <time.h>
using namespace std;
typedef struct ngx_cached_open_file_s {
	//其它属性省略...
	int fd;
	ngx_queue_t queue;
}ngx_cached_file_t;
 
typedef struct {
	//其它属性省略...
	ngx_queue_t expire_queue;
	//其它属性省略...
} ngx_open_file_cache_t;
int main(void) {
	ngx_open_file_cache_t* cache = new ngx_open_file_cache_t;
	ngx_queue_t* q;
	ngx_queue_init(&cache->expire_queue);
	//1. 模拟文件模块，增加打开的文件到缓存中
	for (int i = 0; i < 10; i++) {
		ngx_cached_file_t* e = new ngx_cached_file_t;
		e->fd = i;
		ngx_queue_insert_head(&cache->expire_queue, &e->queue);
	}
	//遍历队列
	for (q = cache->expire_queue.next;
		q != ngx_queue_sentinel(&cache->expire_queue); q = q->next) {
		printf("队列中的元素：%d\n", (ngx_queue_data(q,
			ngx_cached_file_t, queue))->fd);
	}
	//模拟缓存的文件到期，执行出列操作
	while (!ngx_queue_empty(&cache->expire_queue)) {
		q = ngx_queue_last(&cache->expire_queue);
		ngx_cached_file_t* cached_file = ngx_queue_data(q,
			ngx_cached_file_t, queue);
		printf("出队列中的元素：%d\n", cached_file->fd);
		ngx_queue_remove(q);
		delete(cached_file);
	}
	system("pause");
	return 0;
}

顺序队列完整代码


#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>
using namespace std;
#define MaxSize 5 //队列的最大容量
typedef int DataType; //队列中元素类型
typedef struct Queue{
	DataType queue[MaxSize];
	int front; //队头指针
	int rear; //队尾指针
}SeqQueue;
 
//队列初始化，将队列初始化为空队列
void InitQueue(SeqQueue * SQ){
	if (!SQ) return;
	SQ->front = SQ->rear = 0; //把对头和队尾指针同时置 0
}
//判断队列为空
int IsEmpty(SeqQueue* SQ){
	if (!SQ) return 0;
	if (SQ->front == SQ->rear){
		return 1;
	}
	return 0;
}
//判断队列是否为满
int IsFull(SeqQueue* SQ){
	if (!SQ) return 0;
	if (SQ->rear == MaxSize){
		return 1;
	}
	return 0;
}
//入队,将元素 data 插入到队列 SQ 中
int EnterQueue(SeqQueue* SQ, DataType data) {
	if (!SQ) return 0;
	if (IsFull(SQ)) {
		cout << "无法插入元素 " << data << ", 队列已满!" << endl;
		return 0;
	}
	SQ->queue[SQ->rear] = data; //在队尾插入元素 data
	SQ->rear++; //队尾指针后移一位
	return 1;
 
}
//出队，将队列中队头的元素 data 出队，后面的元素向前移动
int DeleteQueue(SeqQueue* SQ, DataType* data) {
	if (!SQ || IsEmpty(SQ)) {
		cout << "队列为空！" << endl;
		return 0;
	}
	if (!data) return 0;
	*data = SQ->queue[SQ->front];
	for (int i = SQ->front + 1; i < SQ->rear; i++) {//移动后面的元素
		SQ->queue[i - 1] = SQ->queue[i];
	}
	SQ->rear--;//队尾指针前移一位
	return 1;
}
 
//出队，将队列中队头的元素 data 出队，出队后队头指针 front 后移一位
int DeleteQueue2(SeqQueue* SQ, DataType* data){
	if (!SQ || IsEmpty(SQ)){
		cout << "队列为空！" << endl;
		return 0;
	}
	if (SQ->front >= MaxSize) {
		cout << "队列已到尽头!" << endl;
		return 0;
	}
	*data = SQ->queue[SQ->front]; //出队元素值
	SQ->front = (SQ->front) + 1; //队首指针后移一位
	return 1;
}
//打印队列中的各元素
void PrintQueue(SeqQueue* SQ){
	if (!SQ) return;
 
	int i = SQ->front;
	while (i < SQ->rear){
		cout << setw(4) << SQ->queue[i];
		i++;
	}
	cout << endl;
}
//获取队首元素，不出队
int GetHead(SeqQueue* SQ, DataType* data){
	if (!SQ || IsEmpty(SQ)){
		cout << "队列为空!" << endl;
	}
	return *data = SQ->queue[SQ->front];
}
//清空队列
void ClearQueue(SeqQueue* SQ){
	if (!SQ) return;
	SQ->front = SQ->rear = 0;
}
 
//获取队列中元素的个数
int getLength(SeqQueue* SQ) {
	if (!SQ) return 0;
	return SQ->rear - SQ->front;
}
int main(){
	SeqQueue* SQ = new SeqQueue;
	DataType data = -1;
	//初始化队列
	InitQueue(SQ);
	//入队
	for (int i = 0; i < 7; i++) {
		EnterQueue(SQ, i);
	}
	//打印队列中的元素
 
		printf("队列中的元素(总共%d 个)：", getLength(SQ));
	PrintQueue(SQ);
	cout << endl;
	//出队
	//for(int i=0; i<10; i++){
	if (DeleteQueue2(SQ, &data)) {
		cout << "出队的元素是：" << data << endl;
	}
	else {
		cout << "出队失败！" << endl;
	}
	//}
	//打印队列中的元素
	printf("出队一个元素后，队列中剩下的元素：");
	PrintQueue(SQ);
	cout << endl;
	system("pause");
	return 0;
}

链式队列完整代码


#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>
using namespace std;
#define MaxSize 5 //队列的最大容量
typedef int DataType; //队列中元素类型
typedef struct _QNode { //结点结构
	DataType data;
	struct _QNode* next;
}QNode;
typedef QNode* QueuePtr;
typedef struct Queue{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;
 
//队列初始化，将队列初始化为空队列
void InitQueue(LinkQueue* LQ){
	if (!LQ) return;
	LQ->length = 0;
	LQ->front = LQ->rear = NULL; //把对头和队尾指针同时置 0
}
//判断队列为空
int IsEmpty(LinkQueue* LQ){
	if (!LQ) return 0;
	if (LQ->front == NULL){
		return 1;
	}
	return 0;
}
//判断队列是否为满
int IsFull(LinkQueue* LQ){
	if (!LQ) return 0;
	if (LQ->length == MaxSize){
		return 1;
	}
	return 0;
}
//入队,将元素 data 插入到队列 LQ 中
int EnterQueue(LinkQueue* LQ, DataType data) {
	if (!LQ) return 0;
	if (IsFull(LQ)) {
		cout << "无法插入元素 " << data << ", 队列已满!" << endl;
		return 0;
	}
	QNode* qNode = new QNode;
	qNode->data = data;
	qNode->next = NULL;
	if (IsEmpty(LQ)) {//空队列
		LQ->front = LQ->rear = qNode;
	}
	else {
		LQ->rear->next = qNode;//在队尾插入节点 qNode
		LQ->rear = qNode; //队尾指向新插入的节点
	}
	LQ->length++;
	return 1;
}
//出队，将队列中队头的元素出队，其后的第一个元素成为新的队首
int DeleteQueue(LinkQueue* LQ, DataType* data) {
	QNode* tmp = NULL;
	if (!LQ || IsEmpty(LQ)) {
		cout << "队列为空！" << endl;
		return 0;
	}
	if (!data) return 0;
	tmp = LQ->front;
	LQ->front = tmp->next;
	if (!LQ->front) LQ->rear = NULL;//如果对头出列后不存在其他元素，则rear 节点也要置空
		* data = tmp->data;
	LQ->length--;
	delete tmp;
	return 1;
}
//打印队列中的各元素
void PrintQueue(LinkQueue* LQ){
	QueuePtr tmp;
	if (!LQ) return;
	if (LQ->front == NULL) {
		cout << "队列为空！";
		return;
	}
	tmp = LQ->front;
	while (tmp){
		cout << setw(4) << tmp->data;
		tmp = tmp->next;
	}
	cout << endl;
}
//获取队首元素，不出队
int GetHead(LinkQueue* LQ, DataType* data)
{
	if (!LQ || IsEmpty(LQ)){
		cout << "队列为空!" << endl;
		return 0;
	}
	if (!data) return 0;
	*data = LQ->front->data;
	return 1;
}
//清空队列
void ClearQueue(LinkQueue* LQ){
	if (!LQ) return;
	while (LQ->front) {
		QueuePtr tmp = LQ->front->next;
		delete LQ->front;
		LQ->front = tmp;
	}
	LQ->front = LQ->rear = NULL;
	LQ->length = 0;
}
//获取队列中元素的个数
int getLength(LinkQueue* LQ) {
	if (!LQ) return 0;
	return LQ->length;
}
int main(){
	LinkQueue* LQ = new LinkQueue;
	DataType data = -1;
	//初始化队列
	InitQueue(LQ);
	//入队
	for (int i = 0; i < 7; i++) {
		EnterQueue(LQ, i);
	}
	//打印队列中的元素
	printf("队列中的元素(总共%d 个)：", getLength(LQ));
	PrintQueue(LQ);
	cout << endl;
	//出队
	//for(int i=0; i<10; i++){
	if (DeleteQueue(LQ, &data)) {
		cout << "出队的元素是：" << data << endl;
	}
	else {
		cout << "出队失败！" << endl;
	}
	//}
	//打印队列中的元素
	printf("出队一个元素后，队列中剩下的元素[%d]：", getLength(LQ));
	PrintQueue(LQ);
	cout << endl;
	ClearQueue(LQ);
	cout << "清空队列!\n";
	PrintQueue(LQ);
	//清理资源
	delete LQ;
	system("pause");
	return 0;
}

线程池中的任务队列完整代码


#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>
using namespace std;
#define MaxSize 1000 //队列的最大容量
typedef struct _QNode { //任务结点结构
	int id;
	void (*handler)(void);
	struct _QNode* next;
}QNode;
typedef QNode* QueuePtr;
typedef struct Queue{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;
//分配线程执行的任务节点
QueuePtr thread_task_alloc(){
	QNode* task;
	task = (QNode*)calloc(1, sizeof(QNode));
	if (task == NULL) {
		return NULL;
	}
	return task;
}
//队列初始化，将队列初始化为空队列
void InitQueue(LinkQueue* LQ){
	if (!LQ) return;
	LQ->length = 0;
	LQ->front = LQ->rear = NULL; //把对头和队尾指针同时置 0
}
 
//判断队列为空
int IsEmpty(LinkQueue * LQ){
	if (!LQ) return 0;
	if (LQ->front == NULL){
		return 1;
	}
	return 0;
}
//判断队列是否为满
int IsFull(LinkQueue* LQ){
	if (!LQ) return 0;
	if (LQ->length == MaxSize){
		return 1;
	}
	return 0;
}
//入队,将元素 data 插入到队列 LQ 中
int EnterQueue(LinkQueue* LQ, QNode* node) {
	if (!LQ || !node) return 0;
	if (IsFull(LQ)) {
		cout << "无法插入任务 " << node->id << ", 队列已满!" << endl;
		return 0;
	}
	node->next = NULL;
	if (IsEmpty(LQ)) {//空队列
		LQ->front = LQ->rear = node;
	}
	else {
		LQ->rear->next = node;//在队尾插入节点 qNode
		LQ->rear = node; //队尾指向新插入的节点
	}
	LQ->length++;
	return 1;
}
 
//出队,将队列中队头的节点出队，返回头节点
QNode * PopQueue(LinkQueue * LQ) {
	QNode* tmp = NULL;
	if (!LQ || IsEmpty(LQ)) {
		cout << "队列为空！" << endl;
		return 0;
	}
	tmp = LQ->front;
	LQ->front = tmp->next;
	if (!LQ->front) LQ->rear = NULL;//如果对头出列后不存在其他元素，则rear 节点也要置空
		LQ->length--;
	return tmp;
}
//打印队列中的各元素
void PrintQueue(LinkQueue* LQ{
	QueuePtr tmp;
	if (!LQ) return;
	if (LQ->front == NULL) {
		cout << "队列为空！";
		return;
	}
	tmp = LQ->front;
	while (tmp){
		cout << setw(4) << tmp->id;
		tmp = tmp->next;
	}
	cout << endl;
}
//获取队列中元素的个数
int getLength(LinkQueue* LQ) {
	if (!LQ) return 0;
	return LQ->length;
}
void task1() {
	printf("我是任务 1 ...\n");
}
void task2() {
	printf("我是任务 2 ...\n");
}
int main()
{
	LinkQueue* LQ = new LinkQueue;
	QNode* task = NULL;
	//初始化队列
	InitQueue(LQ);
	//任务 1 入队
	task = thread_task_alloc();
	task->id = 1;
	task->handler = &task1;
	EnterQueue(LQ, task);
	//任务 2 入队
	task = thread_task_alloc();
	task->id = 2;
	task->handler = &task2;
	EnterQueue(LQ, task);
	//打印任务队列中的元素
	printf("队列中的元素(总共%d 个)：", getLength(LQ));
	PrintQueue(LQ);
	cout << endl;
	//执行任务
	while ((task = PopQueue(LQ))) {
		task->handler();
		delete task;
	}
	//清理资源
	delete LQ;
	system("pause");
	return 0;
}

循环队列完整代码


#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>
using namespace std;
#define MaxSize 5 //循环队列的最大容量
typedef int DataType; //循环队列中元素类型
typedef struct Queue
{
	DataType queue[MaxSize];
	int front; //循环队头指针
	int rear; //循环队尾指针
}SeqQueue;
//队列初始化，将循环队列初始化为空队列
void InitQueue(SeqQueue* SQ)
{
	if (!SQ) return;
	SQ->front = SQ->rear = 0; //把对头和队尾指针同时置 0
}
//判断队列为空
int IsEmpty(SeqQueue* SQ){
	if (!SQ) return 0;
	if (SQ->front == SQ->rear){
		return 1;
	}
	return 0;
}
//判断循环队列是否为满
int IsFull(SeqQueue* SQ){
	if (!SQ) return 0;
	if ((SQ->rear + 1) % MaxSize == SQ->front){
		return 1;
	}
	return 0;
}
//入队,将元素 data 插入到循环队列 SQ 中
int EnterQueue(SeqQueue* SQ, DataType data) {
	if (!SQ) return 0;
	if (IsFull(SQ)) {
		cout << "无法插入元素 " << data << ", 队列已满!" << endl;
		return 0;
	}
	SQ->queue[SQ->rear] = data; //在队尾插入元素 data
	SQ->rear = (SQ->rear + 1) % MaxSize; //队尾指针循环后移一位
	return 1;
}
//出队，将队列中队头的元素 data 出队，出队后队头指针 front 后移一位
int DeleteQueue(SeqQueue* SQ, DataType* data){
	if (!SQ || IsEmpty(SQ)){
		cout << "循环队列为空！" << endl;
		return 0;
	}
	*data = SQ->queue[SQ->front]; //出队元素值
	SQ->front = (SQ->front + 1) % MaxSize; //队首指针后移一位
	return 1;
}
//打印队列中的各元素
void PrintQueue(SeqQueue* SQ){
	if (!SQ) return;
	int i = SQ->front;
	while (i != SQ->rear){
		cout << setw(4) << SQ->queue[i];
		i = (i + 1) % MaxSize;
	}
	cout << endl;
}
//获取队首元素，不出队
int GetHead(SeqQueue* SQ, DataType* data){
	if (!SQ || IsEmpty(SQ)){
		cout << "队列为空!" << endl;
	}
	return *data = SQ->queue[SQ->front];
}
//清空队列
void ClearQueue(SeqQueue* SQ){
	if (!SQ) return;
	SQ->front = SQ->rear = 0;
}
//获取队列中元素的个数
int getLength(SeqQueue* SQ) {
	if (!SQ) return 0;
	return (SQ->rear - SQ->front + MaxSize) % MaxSize;
}
int main(){
	SeqQueue* SQ = new SeqQueue;
	DataType data = -1;
	//初始化队列
	InitQueue(SQ);
	//入队
	for (int i = 0; i < 7; i++) {
		EnterQueue(SQ, i);
	}
	//打印队列中的元素
	printf("队列中的元素(总共%d 个)：", getLength(SQ));
	PrintQueue(SQ);
	cout << endl;
	//出队
	for (int i = 0; i < 5; i++) {
		if (DeleteQueue(SQ, &data)) {
			cout << "出队的元素是：" << data << endl;
		}
		else {
			cout << "出队失败！" << endl;
		}
	}
	//打印队列中的元素
	printf("出队五个元素后，队列中剩下的元素个数为 %d 个：",
		getLength(SQ));
	PrintQueue(SQ);
	cout << endl;
	//入队 4 个
	for (int i = 0; i < 4; i++) {
		EnterQueue(SQ, i + 10);
	}
	printf("\n 入队四个元素后，队列中剩下的元素个数为 %d 个：",
	getLength(SQ));
	PrintQueue(SQ);
	system("pause");
	return 0;
}

优先队列完整代码


#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>
using namespace std;
#define MaxSize 5 //队列的最大容量
typedef int DataType; //任务队列中元素类型
typedef struct _QNode { //结点结构
	int priority; //每个节点的优先级,0 最低优先级，9 最高优先级，优先级相同，取第一个节点
	DataType data;
	struct _QNode* next;
}QNode;
typedef QNode* QueuePtr;
 
typedef struct Queue{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;
 
//队列初始化，将队列初始化为空队列
void InitQueue(LinkQueue* LQ){
	if (!LQ) return;
	LQ->length = 0;
	LQ->front = LQ->rear = NULL; //把对头和队尾指针同时置 0
}
//判断队列为空
int IsEmpty(LinkQueue* LQ){
	if (!LQ) return 0;
	if (LQ->front == NULL){
		return 1;
	}
	return 0;
}
 
//判断队列是否为满
int IsFull(LinkQueue* LQ){
	if (!LQ) return 0;
	if (LQ->length == MaxSize){
		return 1;
	}
	return 0;
}
 
//入队,将元素 data 插入到队列 LQ 中
int EnterQueue(LinkQueue* LQ, DataType data, int priority) {
	if (!LQ) return 0;
	if (IsFull(LQ)) {
		cout << "无法插入元素 " << data << ", 队列已满!" << endl;
		return 0;
	}
	QNode* qNode = new QNode;
	qNode->data = data;
	qNode->priority = priority;
	qNode->next = NULL;
	if (IsEmpty(LQ)) {//空队列
		LQ->front = LQ->rear = qNode;
	}
	else {
		LQ->rear->next = qNode;//在队尾插入节点 qNode
		LQ->rear = qNode; //队尾指向新插入的节点
	}
	LQ->length++;
	return 1;
}
//出队，遍历队列，找到队列中优先级最高的元素 data 出队
int DeleteQueue(LinkQueue* LQ, DataType* data) {
	QNode** prev = NULL, * prev_node = NULL;//保存当前已选举的最高优先级节点上一个节点的指针地址。
	QNode * last = NULL, *tmp = NULL;
	if (!LQ || IsEmpty(LQ)) {
		cout << "队列为空！" << endl;
		return 0;
	}
	if (!data) return 0;
	//prev 指向队头 front 指针的地址
	prev = &(LQ->front);
	printf("第一个节点的优先级: %d\n", (*prev)->priority);
	last = LQ->front;
	tmp = last->next;
	while (tmp) {
		if (tmp->priority > (*prev)->priority) {
			printf("抓到个更大优先级的节点[priority: %d]\n",
				tmp->priority);
			prev = &(last->next);
			prev_node = last;
		}
		last = tmp;
		tmp = tmp->next;
	}
	*data = (*prev)->data;
	tmp = *prev;
	*prev = (*prev)->next;
	delete tmp;
	LQ->length--;
	//接下来存在 2 种情况需要分别对待
	//1.删除的是首节点,而且队列长度为零
	if (LQ->length == 0) {
		LQ->rear = NULL;
	}
	//2.删除的是尾部节点
	if (prev_node && prev_node->next == NULL) {
		LQ->rear = prev_node;
	}
	return 1;
}
 
//打印队列中的各元素
void PrintQueue(LinkQueue * LQ){
	QueuePtr tmp;
	if (!LQ) return;
	if (LQ->front == NULL) {
		cout << "队列为空！";
		return;
	}
	tmp = LQ->front;
	while (tmp){
		cout << setw(4) << tmp->data << "[" << tmp->priority << "]";
		tmp = tmp->next;
	}
	cout << endl;
}
//获取队首元素，不出队
int GetHead(LinkQueue* LQ, DataType* data){
	if (!LQ || IsEmpty(LQ)){
		cout << "队列为空!" << endl;
		return 0;
	}
	if (!data) return 0;
	*data = LQ->front->data;
	return 1;
}
//清空队列
void ClearQueue(LinkQueue* LQ){
	if (!LQ) return;
	while (LQ->front) {
		QueuePtr tmp = LQ->front->next;
		delete LQ->front;
		LQ->front = tmp;
	}
 
		LQ->front = LQ->rear = NULL;
	LQ->length = 0;
}
//获取队列中元素的个数
int getLength(LinkQueue* LQ) {
	if (!LQ) return 0;
	return LQ->length;
}
int main(){
	LinkQueue* LQ = new LinkQueue;
	DataType data = -1;
	//初始化队列
	InitQueue(LQ);
	//入队
	for (int i = 0; i < 5; i++) {
		EnterQueue(LQ, i + 10, i);
	}
	//打印队列中的元素
	printf("队列中的元素(总共%d 个)：", getLength(LQ));
	PrintQueue(LQ);
	cout << endl;
	//出队
	for (int i = 0; i < 5; i++) {
		if (DeleteQueue(LQ, &data)) {
			cout << "出队的元素是：" << data << endl;
		}
		else {
			cout << "出队失败！" << endl;
		}
	}
	//打印队列中的元素
	printf("出队五个元素后，队列中剩下的元素[%d]：\n", getLength(LQ));
	PrintQueue(LQ);
	cout << endl;
	ClearQueue(LQ);
	cout << "清空队列!\n";
	PrintQueue(LQ);
 
	//清理资源
	delete LQ;
	system("pause");
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/551856

队列 结构详解（顺序/链式队列、循环队列、优先队列、高并发WEB服务队列）（C/C++）_链式排队器的优先级

一、队列的原理精讲

二、队列算法实现

2.1顺序存储

队列初始化

队列为空

队列为满

入队：将新元素插入 rear 所指的位置，然后 rear 加 1。

打印队列中的元素

出队： 方式 1 —— 删除 front 所指的元素, 后面所有元素前移 1 并返回被删除元素。

出队： 方式 2 —— 删除 front 所指的元素，然后加 1 并返回被删元素。

取队首元素：返回 front 指向的元素值

清空队列

顺序队列文章结尾有完整代码~

2.2链式存储

链式队列操作图示 空队列时，front 和 rear 都指向空。

删除节点

链式队列文章结尾有完整代码~

三、队列实际开发应用案例

3.1线程池中的任务队列

线程池中的任务队列 文章结尾有完整代码~

3.2循坏队列

循环队列文章结尾有完整代码

3.3优先队列

空的任务队列 & 插入元素

删除一个节点

优先队列出队

优先队列文章结尾有完整代码~

3.4动态队列

3.5高并发WEB服务器队列的应用

源码实现

nginx_queue.h

Nginx_双向循环队列.cpp

顺序队列完整代码

链式队列完整代码

线程池中的任务队列完整代码

循环队列完整代码

优先队列完整代码

队列结构详解（顺序/链式队列、循环队列、优先队列、高并发WEB服务队列）（C/C++）_链式排队器的优先级

出队：方式 1 —— 删除 front 所指的元素, 后面所有元素前移 1 并返回被删除元素。

出队：方式 2 —— 删除 front 所指的元素，然后加 1 并返回被删元素。

链式队列操作图示
空队列时，front 和 rear 都指向空。

线程池中的任务队列文章结尾有完整代码~