队列算法的原理和实现，及其企业级应用

一，队列的原理
二，队列的算法实现
- 队列的算法实现1：使用数组
- 队列的算法实现2：使用链表
三，队列的企业级应用案例
- 一，线程池中的任务队列
- 二，循环队列
- 三，优先队列
- 四，动态顺序队列
- 五，高并发 WEB 服务器队列的应用

一，队列的原理

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

队列是一种受限的线性结构
它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。

生活中队列场景随处可见: 比如在电影院, 商场, 或者厕所排队。。。。。。

二，队列的算法实现队列的算法实现1：使用数组

顺序存储：

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

rear-front 即为存储的元素个数！

定义方式为：

#define MaxSize 5 //队列的最大容量 

typedef int DataType; //队列中元素类型 

typedef struct Queue { 
    DataType queue[MaxSize]; 
    int front; //队头指针 
    int rear; //队尾指针 
}SeqQueue;

#include 
#include 

using namespace std;

typedef int Datatype;	//队列中的元素类型
#define MAX_SIZE 5		//队列最大容量

typedef struct _Queue {
	Datatype queue[MAX_SIZE];
	int front;
	int rear;
}Queue;

//初始化队列
bool initQueue(Queue* &Q) {
	if(!Q) return false;
	Q->front = Q->rear =0;
	return true;
}

//判断队列是否为空
bool blankQueue(Queue* &Q) {
	if(!Q) return false;
	if(Q->rear == Q->front) return true;
	return false;
}

//判断队列是否塞满
bool isFullQueue(Queue* &Q, Datatype data) {
	if(!Q) return false;
	if(Q->rear == MAX_SIZE) {
		cout << "队列已满，不能将" << data << "排进队列" << endl;	
		return true;
	}
	return false;
}

//排进队列
void queueUp(Queue* &Q, Datatype data) {
	if(!Q) return;
	if(isFullQueue(Q, data)) return;
	Q->queue[Q->rear] = data;
	Q->rear++;
}

//删除队首: 方法一
bool deleteQueueFirst(Queue* &Q, int *data) {
	if(!Q || blankQueue(Q)){
		cout << "队列为空!" << endl;
		return false;
	}
	if(!data) return false;

	int i = Q->front;
	--Q->rear;
	*data = Q->queue[Q->front];
	while(i != Q->rear) {
		Q->queue[i] = Q->queue[i+1];
		i++;
	}
	return false;
}

//删除队首: 方法二
bool deleteQueueFirst2(Queue* &Q, int *data) {
	if(!Q || blankQueue(Q)){
		cout << "队列为空!" << endl;
		return false;
	}
	if(!data) return false;
	if(Q->front == Q->rear) {
		cout << "队列已到尽头！" << endl;
		return false;
	}

	*data = Q->queue[Q->front];
	Q->front++;
	return true;
}

//获取队首元素
bool getFirstElem(Queue* &Q, Datatype *data) {
	if(!Q || blankQueue(Q)){
		cout << "队列为空!" << endl;
		return false;
	}
	if(!data) return false;

	*data = Q->queue[Q->front];
	return true;
}

//队列的长度
int OueueLength(Queue* &Q) {
	if(!Q) return 0;
	return Q->rear - Q->front;
}

//清空队列
void deleteQueue(Queue* Q) {
	Q->front = Q->rear = 0;
}

//打印队列
void printfQueue(Queue* &Q) {
	if(!Q) return;
	cout << "打印队列:";
	if(Q->front == Q->rear) {
		cout << "队列已到尽头！" << endl;
		return ;
	}
	int i = Q->front;
	while(i != Q->rear) {
		cout << Q->queue[i] << " ";
		i++;
	}
	cout << endl;
}

int main(void) {
	Queue *Q = new Queue;
	int data;

	//初始化队列
	initQueue(Q);

	for(int i=0; i<7; i++) {
		queueUp(Q, i);
	}
	printfQueue(Q);

	for(int i=0; i<10; i++) {
		if(deleteQueueFirst2(Q, &data))
			cout << "出队的元素是:" << data << endl;

		if(getFirstElem(Q, &data))
			cout << "队首的元素是:" << data << endl;
		printfQueue(Q);
	}

	system("pause");
	return 0;
}

队列的算法实现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 都指向空。

#include 
#include 

using namespace std;

typedef int Datatype;	//队列中的数据类型
#define MAX_SIZE     5	//队列中的最大容量

typedef struct _QNode {
	Datatype data;
	struct _QNode *next;
}QNode;

typedef QNode* QueuePtr;

typedef struct _QueueLink {
	int length;		//队列长度
	QueuePtr front; //指向队首
	QueuePtr rear;	//指向队尾
}QueueLink;

//队列初始化
bool initQueueLink(QueueLink* &QL) {
	if(!QL) return false;
	QL->length = 0;
	QL->front = QL->rear = NULL;
	return true;
}

//判断队列是否为空
bool isBlankQueueLink(QueueLink* &QL) {
	if(!QL) return false;
	if(!QL->front) return true;
	return false;
}

//判断队列是否塞满
bool isFullQueueLink(QueueLink* &QL) {
	if(!QL) return false;
	if(QL->length == MAX_SIZE) return true;
	return false;
}

//元素进入队列
bool enterElemQueueLink(QueueLink* &QL, Datatype data) {
	if(!QL) return false;
	if(isFullQueueLink(QL)) {
		cout << "队列已满！无法将元素" << data << "插入到队列中！" << endl;
		return false;
	}
	QNode* node = new QNode;
	node->data = data;

	if(isBlankQueueLink(QL)) {
		QL->front = QL->rear = node;
	}else {
		QL->rear->next = node;
		QL->rear = node;
	}
	node->next = NULL;
	QL->length++;
	return true;
}

//元素出队列
bool deleteElemQueueLink(QueueLink* &QL, Datatype *data) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return false;
	}
	if(!data) return false;

	QNode *tmp = NULL;
	tmp = QL->front;

	QL->front = QL->front->next;
    if(!QL->front) QL->rear = NULL;
    
	*data = tmp->data;
	delete tmp;
	QL->length--;
	return true;
}

//获取队首元素
bool getFirstElemQueueLink(QueueLink* &QL, Datatype *data) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return false;
	}
	if(!data) return false;

	*data = QL->front->data;
	return true;
}

//清空队列
void clearQueueLink(QueueLink* &QL) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return;
	}

	QNode *p = QL->front;

	while(p) {
		cout << "删除" << p->data << endl;
		QL->front = QL->front->next;
		delete p;
		 p = QL->front;
	}
	

	QL->front = QL->rear = NULL;
	QL->length = 0;

}

//队列长度
int getLengthQueueLink(QueueLink* QL) {
	if(!QL || isBlankQueueLink(QL)) return 0;

	int i=0;
	QueuePtr p = QL->front;
	while(p) {
		i++;
		p = p->next;
	}
	return i;
}

//打印队列
void printfQueueLink(QueueLink* &QL) {
	cout << "打印队列:";
	if(!QL) return;
	if(isBlankQueueLink(QL)) return;
	
	QNode *p = QL->front;
	while(p) {
		cout << p->data << " ";
		p = p->next;
	}

	cout << endl;
}

int main(void) {
	QueueLink *QL = new QueueLink;
	initQueueLink(QL);
	int x = -2;

	for(int i=0; i<7; i++) {
		if(enterElemQueueLink(QL, i)) {
			cout << "添加[" << i << "]成功！" << endl;
		}else {
			cout << "添加失败！" << endl;
		}
		printfQueueLink(QL);
		if(getFirstElemQueueLink(QL, &x)) {
			cout << "获取队首元素【" << x << "】，成功！" << endl;
		}else{
			cout << "获取队首元素失败" << endl;
		}
		cout << "队列长度：" << getLengthQueueLink(QL) << endl;
		cout << endl;
	}

	
	clearQueueLink(QL);
	printfQueueLink(QL);
	delete QL;
	system("pause");
	return 0;
}

三，队列的企业级应用案例一，线程池中的任务队列

线程池－由一个任务队列和一组处理队列的线程组成。一旦工作进程需要处理某个可能“阻塞”的

操作，不用自己操作，将其作为一个任务放到线程池的队列，接着会被某个空闲线程提取处理。

定义方式：

typedef struct _QNode { //结点结构 
    int id; 
    void (*handler)(); 
    struct _QNode *next; 
}QNode; 

typedef QNode * QueuePtr; 

typedef struct Queue { 
    int length; //队列的长度 
    QueuePtr front; //队头指针 
    QueuePtr rear; //队尾指针 
}LinkQueue;

#include 
#include 

using namespace std;

#define MAX_SIZE     5	//队列中的最大容量

typedef struct _QNode {
	int fd;
	void (*handler)();
	struct _QNode *next;
}QNode;

typedef QNode* QueuePtr;

typedef struct _QueueLink {
	int length;		//队列长度
	QueuePtr front; //指向队首
	QueuePtr rear;	//指向队尾
}QueueLink;

//分配线程中的任务节点
QueuePtr thread_task_alloc() {
	QNode *task = (QNode*)calloc(1, sizeof(QNode));;
	if(!task) return NULL;
	return task;
}

//队列初始化
bool initQueueLink(QueueLink* &QL) {
	if(!QL) return false;
	QL->length = 0;
	QL->front = QL->rear = NULL;
	return true;
}

//判断队列是否为空
bool isBlankQueueLink(QueueLink* &QL) {
	if(!QL) return false;
	if(!QL->front) return true;
	return false;
}

//判断队列是否塞满
bool isFullQueueLink(QueueLink* &QL) {
	if(!QL) return false;
	if(QL->length == MAX_SIZE) return true;
	return false;
}

//元素进入队列
bool enterElemQueueLink(QueueLink* &QL, QNode *node) {
	if(!QL || !node) return false;
	if(isFullQueueLink(QL)) {
		cout << "队列已满！无法将任务：" << node->handler << "插入到队列中！" << endl;
		return false;
	}

	if(isBlankQueueLink(QL)) {
		QL->front = QL->rear = node;
	}else {
		QL->rear->next = node;
		QL->rear = node;
	}
	node->next = NULL;
	QL->length++;
	return true;
}

//元素出队列
QueuePtr PopQueueLink(QueueLink* &QL) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return false;
	}

	QNode *tmp = NULL;
	tmp = QL->front;

	QL->front = tmp->next;
	if(!QL->front) QL->rear = NULL;

	QL->length--;
	return tmp;
}

//获取队首元素
QueuePtr getFirstElemQueueLink(QueueLink* &QL) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return NULL;
	}
	return QL->front;
}

//清空队列
void clearQueueLink(QueueLink* &QL) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return;
	}

	QNode *p = QL->front;

	while(p) {
		cout << "删除" << p->handler << endl;
		QL->front = QL->front->next;
		delete p;
		 p = QL->front;
	}
	

	QL->front = QL->rear = NULL;
	QL->length = 0;

}

//队列长度
int getLengthQueueLink(QueueLink* QL) {
	if(!QL || isBlankQueueLink(QL)) return 0;

	
	return QL->length;
}

//打印队列
void printfQueueLink(QueueLink* &QL) {
	cout << "打印任务队列:";
	if(!QL) return;
	if(isBlankQueueLink(QL)) return;
	
	QNode *p = QL->front;
	while(p) {
		cout << p->fd << " ";
		p = p->next;
	}

	cout << endl;
}

void task1(){ 
	printf("我是任务 1 ...n"); 
}

void task2(){ 
	printf("我是任务 2 ...n"); 
}

int main(void) {
	QueueLink *QL = new QueueLink;

	//初始化队列
	initQueueLink(QL);

	//任务1入队
	QNode *task = thread_task_alloc();
	task->fd = 1;
	task->handler  = &task1;
	enterElemQueueLink(QL, task);

	//任务2入队
	task = thread_task_alloc();
	task->fd = 2;
	task->handler  = &task2;
	enterElemQueueLink(QL, task);

	cout << "队列中的任务长度为：" << getLengthQueueLink(QL) << endl;
	printfQueueLink(QL);
	cout << endl;

	//执行任务队列
	while((task=PopQueueLink(QL))) {
		task->handler();
		delete task;
	}

	delete QL;
	system("pause");
	return 0;
}

二，循环队列

循环队列

在队列的顺序存储中，采用出队方式 2, 删除 front 所指的元素，然后加 1 并返回被删元素。这样可以避免元素

移动，但是也带来了一个新的问题“假溢出”。

能否利用前面的空间继续存储入队呢？采用循环队列可以解决这个问题.

循环队列入队, 队尾循环后移： SQ->rear =（SQ->rear+1）%MAX_SIZE;

循环队列出队, 队首循环后移： SQ->front =（SQ->front+1）%MAX_SIZE;

队空：SQ.front=SQ.rear; // SQ.rear 和 SQ.front 指向同一个位置

队满： (SQ.rear+1) %MAX_SIZE=SQ.front; // SQ.rear 向后移一位正好是 SQ.front

计算元素个数:

可以分两种情况判断：

如果 SQ.rear>= SQ.front：元素个数为 SQ.rear-SQ.front；
如果 SQ.rear

采用取模的方法把两种情况统一为：(SQ.rear-SQ.front+MAX_SIZE)% MAX_SIZE

#include 
#include 

using namespace std;

typedef int Datatype;	//队列中的元素类型
#define MAX_SIZE 5		//队列最大容量

typedef struct _Queue {
	Datatype queue[MAX_SIZE];
	int front;
	int rear;
}Queue;

//初始化队列
bool initQueue(Queue* &Q) {
	if(!Q) return false;
	Q->front = Q->rear =0;
	return true;
}

//判断队列是否为空
bool blankQueue(Queue* &Q) {
	if(!Q) return false;
	if(Q->rear == Q->front) return true;
	return false;
}

//判断队列是否塞满
bool isFullQueue(Queue* &Q) {
	if(!Q) return false;
	if((Q->rear + 1)%MAX_SIZE == Q->front) return true;
	return false;
}

//进入队列
void queueUp(Queue* &Q, Datatype data) {
	if(!Q) return;
	if(isFullQueue(Q)) {
	cout << "队列已满，不能将" << data << "排进队列" << endl;	
		return;
	}

	Q->queue[Q->rear] = data;
	Q->rear = (Q->rear + 1)%MAX_SIZE;
}

//删除队首
bool deleteQueueFirst(Queue* &Q, int *data) {
	if(!Q || blankQueue(Q)){
		cout << "队列为空!" << endl;
		return false;
	}
	if(!data) return false;
	
	*data = Q->queue[Q->front];
	Q->front = (Q->front+ 1)%MAX_SIZE;
	return true;
}

//获取队首元素
bool getFirstElem(Queue* &Q, Datatype *data) {
	if(!Q || blankQueue(Q)){
		cout << "队列为空!" << endl;
		return false;
	}
	if(!data) return false;

	*data = Q->queue[Q->front];
	return true;
}

//队列的长度
int OueueLength(Queue* &Q) {
	if(!Q) return 0;
	return (Q->rear - Q->front + MAX_SIZE)%MAX_SIZE;
}

//清空队列
void deleteQueue(Queue* Q) {
	Q->front = Q->rear = 0;
}

//打印队列
void printfQueue(Queue* &Q) {
	if(!Q || blankQueue(Q)){
		cout << "队列为空!" << endl;
		return ;
	}
	cout << "打印队列:";
	
	int i = Q->front;
	while(i != Q->rear) {
		cout << Q->queue[i] << " ";
		i = (i + 1)%MAX_SIZE;
	}
	cout << endl;
}

int main(void) {
	Queue *Q = new Queue;
	int data;

	//初始化队列
	initQueue(Q);

	for(int i=0; i<7; i++) {
		queueUp(Q, i);
	}
	cout << "队列长度：" << OueueLength(Q) << endl;
	printfQueue(Q);

	cout << endl;

	for(int i=0; i<5; i++) {
		if(deleteQueueFirst(Q, &data))
			cout << "出队的元素是:" << data << endl;

		if(getFirstElem(Q, &data))
			cout << "队首的元素是:" << data << endl;
		cout << "队列长度：" << OueueLength(Q) << endl;
		printfQueue(Q);
		cout << endl;
	}

	for(int i=0; i<7; i++) {
		queueUp(Q, i);
	}
	cout << "队列长度：" << OueueLength(Q) << endl;
	printfQueue(Q);

	cout << endl;

	for(int i=0; i<5; i++) {
		if(deleteQueueFirst(Q, &data))
			cout << "出队的元素是:" << data << endl;

		if(getFirstElem(Q, &data))
			cout << "队首的元素是:" << data << endl;
		cout << "队列长度：" << OueueLength(Q) << endl;
		printfQueue(Q);
		cout << endl;
	}
	
    delete Q;
    
	system("pause");
	return 0;
}

三，优先队列

优先队列：

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

优先出队。

定义方式为：

typedef int Datatype;	//队列中的数据类型
#define MAX_SIZE     5	//队列中的最大容量

typedef struct _QNode {
	int priority;	//每个节点的优先级,9 最高优先级，0 最低优先级，优先级相同， 取第一个节点
	Datatype data;
	struct _QNode *next;
}QNode;

typedef QNode* QueuePtr;

typedef struct _QueueLink {
	int length;		//队列长度
	QueuePtr front; //指向队首
	QueuePtr rear;	//指向队尾
}QueueLink;

在链表队列中，主要改动出列的代码，改动之后如下：

//元素出队列
bool deleteElemQueueLink(QueueLink* &QL, Datatype *data) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return false;
	}
	if(!data) return false;

	QNode **prev = NULL, *prev_node = NULL;
	QNode *tmp = NULL, *last = NULL;

	prev = &(QL->front);
	cout << "第一个结点的优先级是： " << (*prev)->priority << endl;
	
	last = QL->front;
	tmp = last->next;

	while(tmp) {
		if(tmp->priority > (*prev)->priority) {
			cout << "抓到一个更大的优先级：" << tmp->priority << endl;
			prev = &(last->next);
			prev_node = last;
		}
		last = tmp;
		tmp = tmp->next;
	}

	tmp = *prev;
	*prev = (*prev)->next;
	*data = tmp->data;
	delete tmp;
	QL->length--;

	//如果只有一个节点
    if(!QL->length) QL->rear = NULL;

	//如果删除的是最后一个节点
	//if(prev_node && !prev_node->next) QL->rear = prev_node; 与下面这个写法可以达到相同的效果
	if(!*prev) QL->rear = prev_node;
    
	return true;
}

完整代码：

#include 
#include 

using namespace std;

typedef int Datatype;	//队列中的数据类型
#define MAX_SIZE     5	//队列中的最大容量

typedef struct _QNode {
	int priority;	//优先级
	Datatype data;
	struct _QNode *next;
}QNode;

typedef QNode* QueuePtr;

typedef struct _QueueLink {
	int length;		//队列长度
	QueuePtr front; //指向队首
	QueuePtr rear;	//指向队尾
}QueueLink;

//队列初始化
bool initQueueLink(QueueLink* &QL) {
	if(!QL) return false;
	QL->length = 0;
	QL->front = QL->rear = NULL;
	return true;
}

//判断队列是否为空
bool isBlankQueueLink(QueueLink* &QL) {
	if(!QL) return false;
	if(!QL->front) return true;
	return false;
}

//判断队列是否塞满
bool isFullQueueLink(QueueLink* &QL) {
	if(!QL) return false;
	if(QL->length == MAX_SIZE) return true;
	return false;
}

//元素进入队列
bool enterElemQueueLink(QueueLink* &QL, Datatype data, int priority) {
	if(!QL) return false;
	if(isFullQueueLink(QL)) {
		cout << "队列已满！无法将元素" << data << "插入到队列中！" << endl;
		return false;
	}
	QNode* node = new QNode;
	node->data = data;
	node->priority = priority;

	if(isBlankQueueLink(QL)) {
		QL->front = QL->rear = node;
	}else {
		QL->rear->next = node;
		QL->rear = node;
	}
	node->next = NULL;
	QL->length++;
	return true;
}

//元素出队列
bool deleteElemQueueLink(QueueLink* &QL, Datatype *data) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return false;
	}
	if(!data) return false;

	QNode **prev = NULL, *prev_node = NULL;
	QNode *tmp = NULL, *last = NULL;

	prev = &(QL->front);
	cout << "第一个结点的优先级是： " << (*prev)->priority << endl;
	
	last = QL->front;
	tmp = last->next;

	while(tmp) {
		if(tmp->priority > (*prev)->priority) {
			cout << "抓到一个更大的优先级：" << tmp->priority << endl;
			prev = &(last->next);
			prev_node = last;
		}
		last = tmp;
		tmp = tmp->next;
	}

	tmp = *prev;
	*prev = (*prev)->next;
	*data = tmp->data;
	delete tmp;
	QL->length--;

	//如果只有一个节点
    if(!QL->length) QL->rear = NULL;

	//如果删除的是最后一个节点
	//if(prev_node && !prev_node->next) QL->rear = prev_node; 与下面这个写法可以达到相同的效果
	if(!*prev) QL->rear = prev_node;
    
	return true;
}

//获取队首元素
bool getFirstElemQueueLink(QueueLink* &QL, Datatype *data) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return false;
	}
	if(!data) return false;

	*data = QL->front->data;
	return true;
}

//清空队列
void clearQueueLink(QueueLink* &QL) {
	if(!QL || isBlankQueueLink(QL)) {
		cout << "队列为空" << endl;
		return;
	}

	QNode *p = QL->front;

	while(p) {
		cout << "删除" << p->data << endl;
		QL->front = QL->front->next;
		delete p;
		 p = QL->front;
	}
	

	QL->front = QL->rear = NULL;
	QL->length = 0;

}

//队列长度
int getLengthQueueLink(QueueLink* QL) {
	if(!QL || isBlankQueueLink(QL)) return 0;

	
	return QL->length;
}

//打印队列
void printfQueueLink(QueueLink* &QL) {
	cout << "打印队列:";
	if(!QL) return;
	if(isBlankQueueLink(QL)) return;
	
	QNode *p = QL->front;
	while(p) {
		cout << p->data <<"["<< p->priority <<"]" << " ";
		p = p->next;
	}

	cout << endl;
}

int main(void) {
	QueueLink *QL = new QueueLink;
	initQueueLink(QL);
	int x = -2;


	if(enterElemQueueLink(QL, 8, 6)) {
			cout << "添加[" << 8 << "]成功！" << endl;
		}else {
			cout << "添加失败！" << endl;
		}
		printfQueueLink(QL);

		if(enterElemQueueLink(QL, 0, 9)) {
			cout << "添加[" << 0 << "]成功！" << endl;
		}else {
			cout << "添加失败！" << endl;
		}
		printfQueueLink(QL);

	for(int i=0; i<7; i++) {
		if(enterElemQueueLink(QL, i+10, i)) {
			cout << "添加[" << i+10 << "]成功！" << endl;
		}else {
			cout << "添加失败！" << endl;
		}
		printfQueueLink(QL);
		if(getFirstElemQueueLink(QL, &x)) {
			cout << "获取队首元素【" << x << "】，成功！" << endl;
		}else{
			cout << "获取队首元素失败" << endl;
		}
		cout << "队列长度：" << getLengthQueueLink(QL) << endl;
		cout << endl;
	}

	int data = -1;
	for(int i=0; i<7; i++) {
		if(deleteElemQueueLink(QL, &data)) {
			cout << data << "出队成功！" << endl;
		}else {
			cout << "出队失败！" << endl;
		}
		printfQueueLink(QL);
		if(getFirstElemQueueLink(QL, &x)) {
			cout << "获取队首元素【" << x << "】，成功！" << endl;
		}else{
			cout << "获取队首元素失败" << endl;
		}
		cout << "队列长度：" << getLengthQueueLink(QL) << endl;
		cout << endl;
	}
	clearQueueLink(QL);
	printfQueueLink(QL);

	delete QL;
	system("pause");
	return 0;
}

四，动态顺序队列

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

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

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

经常访问到的文件会被 nginx 从磁盘缓存到内存，这样可以极大的提高 Nginx 的并发能力，不过因为

内存的限制，当缓存的文件数达到一定程度的时候就会采取淘汰机制，优先淘汰进入时间比较久或是最近

访问很少(LRU)的队列文件。

具体实现方案：

使用双向循环队列保存缓存的文件节点，这样可以实现多种淘汰策略：

比如：如果采用淘汰进入时间比较久的策略，就可以使用队列的特性，先进先出

如果要采用按照 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  
#include  
#include  
#include "nginx_queue.h" 
#include  

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("队列中的元素：%dn", (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("出队列中的元素：%dn", cached_file->fd); ngx_queue_remove(q); 				delete(cached_file); 
    }
    system("pause"); 
    return 0; 
}

队列算法的原理和实现，及其企业级应用

C/C++/C#相关栏目本月热门文章