队列是一种受限的线性表，(Queue)，它是一种运算受限的线性表,先进先出(FIFO First In First Out)
队列是一种受限的线性结构
它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
生活中队列场景随处可见: 比如在电影院, 商场, 或者厕所排队。。。。。。
顺序存储 ：
采用数组来保存队列的元素，设立一个队首指针 front ，一个队尾指针 rear，分别指向队首和队尾元素。则
rear-front 即为存储的元素个数！
定义方式为：
#define MaxSize 5 //队列的最大容量
typedef int DataType; //队列中元素类型
typedef struct Queue {
DataType queue[MaxSize];
int front; //队头指针
int rear; //队尾指针
}SeqQueue;
#include <iostream>
#include <Windows.h>
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;
}
链式存储：
队列的链式存储结构，其实就是线性表的单链表，只不过它只是尾进头出而已，我们把它简称为链队列。为了
操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点 。
定义方式为：
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 <iostream>
#include <Windows.h>
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;
}
/*while(QL->front){
QueuePtr tmp = QL->front->next;
delete QL->front;
QL->front = tmp;
}*/
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;
}
/*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;
}
线程池 － 由一个任务队列和一组处理队列的线程组成。一旦工作进程需要处理某个可能“阻塞”的
操作，不用自己操作，将其作为一个任务放到线程池的队列，接着会被某个空闲线程提取处理。
定义方式：
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 <iostream>
#include <Windows.h>
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;
}
/*while(QL->front){
QueuePtr tmp = QL->front->next;
delete QL->front;
QL->front = tmp;
}*/
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 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.front：元素个数为 SQ.rear-SQ.front+ MAX_SIZE；
采用取模的方法把两种情况统一为：(SQ.rear-SQ.front+MAX_SIZE)% MAX_SIZE
#include <iostream>
#include <Windows.h>
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 <iostream>
#include <Windows.h>
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;
}
/*while(QL->front){
QueuePtr tmp = QL->front->next;
delete QL->front;
QL->front = tmp;
}*/
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;*/
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;
}
使用链表动态存储的队列即为动态顺序队列，前面已经实现，故不再重复！
在高并发 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 <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;
}