@TOC

队列

队列是一种受限的线性表，它允许在一段进行删除操作，在另一端进行插入操作。

可以用数组实现，也可以用链表实现。

数组实现(顺序存储)

设立一个队头指针front,一个队尾指针rear，分别指向队头元素和队尾元素，rear-front为元素个数。

(数组实现中，其实就是下标。)

#define MAX_SIZE 10
typedef int DataType;

typedef struct Queue
{
    DataType queue[MAX_SIZE];
    int front;
    int rear;
}SeqQueue;

//初始化
void initQueue(SeqQueue* SQ)
{
    if (!SQ)//如果传递进来的是个空指针的话
    {
        return;
    }
    SQ->front = SQ->rear = 0;
}
//判断队列是否满了
bool isFull(SeqQueue* SQ)
{
    if (!SQ)
    {
        return false;
    }

    if (SQ->rear == MAX_SIZE)
    {
        return true;
    }
    return false;
}
//判断队列是否为空
bool isEmpty(SeqQueue* SQ)
{
    if (!SQ)
    {
        return false;
    }
    if (SQ->rear == SQ->front)
    {
        return true;
    }
    return false;
}
//入队
bool pushQueue(SeqQueue* SQ,DataType data)
{
    if (!SQ)
    {
        return false;
    }
    if (isFull(SQ))
    {
        return false;
    }
    SQ->queue[SQ->rear] = data;
    SQ->rear++;//队尾指针后移,插入之后rear"指向"当前位置的下一个位置。
    return true;
}
//输出
void printQueue(SeqQueue* SQ)
{
    if (isEmpty(SQ))
    {
        return;
    }
    int i = SQ->front;
    while (i < SQ->rear)
    {
        cout << SQ->queue[i]<<" ";
        i++;
    }
    cout << endl;
}

//出队-从表头开始删除
bool popQueue(SeqQueue* SQ)
{
    //就是删除第一个元素
    if (!SQ || isEmpty(SQ))
    {
        return false;
    }
    for (int i = SQ->front; i < SQ->rear; i++)
    {
        SQ->queue[i] = SQ->queue[i+1];
    }
    SQ->rear--;
    //直接对front进行操作的话空间会越来越小
    return false;
}
//获取队列首元素
DataType getFront(SeqQueue* SQ)
{
    if (!SQ)
    {
        return -1;
    }
    return SQ->queue[SQ->front];
}
//清空队列
bool destoryQueue(SeqQueue* SQ)
{
    if (!SQ)
    {
        return false;
    }
    SQ->front = SQ->rear = 0;
    return true;
}
//获取长度-元素个数
int getElemsNum(SeqQueue* SQ)
{
    if (!SQ)
    {
        return 0;
    }
    return SQ->rear-SQ->front;//返回SQ->rear也一样，数组下标从0开始
}

链表实现(链式存储)

为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

就是简化了单链表，加了些条件限制(一边进，一边出。)

typedef int DataType;

#define MAX_SIZE 100

//结点结构
typedef struct Qnode
{
    DataType data;
    struct Qnode* next;

}Qnode;

typedef Qnode* QueuePtr;

//用数组实现的队列rear指向的是最后一个的下一个，而用链表实现的队列rear指向的是最后一个

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

//初始化队列
bool initLinkQueue(LinkQueue* LQ)
{
    if (!LQ)
    {
        cout << "S";
        return false;
    }
    LQ->length = 0;
    LQ->front = LQ->rear = NULL;//把队头和队尾指针同时置空
    //初始化的置空可以想象成是有个“头结点”,判断队列中是否有元素就看front是否指向的是NULL
    //其实就是有个头结点，开始就已经new出来了
    return true;
}

//判断队列是否为空
bool isEmpty(LinkQueue* LQ)
{
    if (!LQ)
    {
        return false;
    }
    if (!LQ->front)
    {
        return true;
    }
    return false;
}
//判断队列是否满了
bool isFull(LinkQueue* LQ)
{
    if (!LQ)
    {
        return false;
    }
    if (LQ->length == MAX_SIZE)
    {
        return true;
    }
    return false;
}
//入队-从尾部
bool pushQueue(LinkQueue* LQ, DataType num)
{
    if (!LQ)
    {
        return false;
    }
    Qnode* node = new Qnode;
    node->data = num;
    node->next = NULL;

    if (isEmpty(LQ))
    {
        LQ->front = LQ->rear = node;
    }
    else
    {
        LQ->rear->next = node;
        LQ->rear = node;//定位到新的末尾结点
    }
    LQ->length++;
    return true;
}
//出队-从头部
bool popQueue(LinkQueue* LQ)
{
    if (!LQ || isEmpty(LQ))
    {
        return false;
    }
    Qnode* tempnode = LQ->front;
    LQ->front = LQ->front->next;
    delete tempnode;
    LQ->length--;
    //如果出了这个元素后为空，需要将rear也置空
    if (!LQ->front)
    {
        LQ->rear = NULL;
    }
    return true;
}
//打印输出
void printQueue(LinkQueue* LQ)
{
    if (!LQ || isEmpty(LQ))
    {
        return;
    }
    Qnode* tempnode = NULL;
    tempnode = LQ->front;
    while (tempnode)
    {
        cout << tempnode->data<<" ";
        tempnode = tempnode->next;
    }
    cout << endl;
}
//清空队列
bool clearQueue(LinkQueue* LQ)
{
    if (!LQ)
    {
        return false;
    }
    Qnode* tempnode = NULL;
    while (LQ->front)
    {
        tempnode = LQ->front->next;
        delete LQ->front;
        LQ->front = tempnode;
    }
    LQ->front = LQ->rear = NULL;
    LQ->length = 0;
    return true;
}
//获取队列的首元素
bool getFront(LinkQueue* LQ, DataType* recv)
{
    if (!LQ || isEmpty(LQ))
    {
        return false;
    }
    if (!recv)
    {
        return false;
    }
    *recv = LQ->front->data;
    return false;
}
//获取队列元素个数
int getNums(LinkQueue* LQ)
{
    if (!LQ)
    {
        return 0;
    }
    return LQ->length;
}

实际应用

线程池中的任务队列

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

循环队列

与数组实现队列中，出队方式相关，直接移动front(假溢出)，front前的元素全部抛弃，认为是空，下次直接覆盖上去。

判断是否满了,rear+1是否等于front

用模运算来循环

typedef int DataType;

#define MAX_SIZE 10

typedef struct Queue
{
    DataType queue[MAX_SIZE];
    int front;
    int rear;//rear一直在追front
}SeqQueue;

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

    return 0;
}
//是否为满了
bool isFull(SeqQueue* SQ)
{
    if (!SQ)
    {
        return false;
    }
    if ((SQ->rear + 1) % MAX_SIZE == SQ->front)//因为rear要指向front前的一个空的位置，所以真正只可以push进MAX_SIZE-1个
    {
        return true;
    }
    return false;
}
//是否为空
bool isEmpty(SeqQueue* SQ)
{
    if (!SQ)
    {
        return false;
    }
    if (SQ->front == SQ->rear)
    {
        return true;
    }
    return false;
}
//入队
bool pushQueue(SeqQueue* SQ, DataType m_data)
{
    if (!SQ || isFull(SQ))
    {
        return false;
    }
    SQ->queue[SQ->rear] = m_data;
    //移动队尾指针
    SQ->rear = (SQ->rear + 1) % MAX_SIZE;
    return true;
}
//出队
bool popQueue(SeqQueue* SQ)
{
    if (!SQ || isEmpty(SQ))
    {
        return false;
    }
    //队首指针后移
    SQ->front = (SQ->front + 1) % MAX_SIZE;
    return true;
}
//打印输出
//从第一个位置之后，rear都指向一个空的位置
bool printQueue(SeqQueue* SQ)
{
    if (!SQ)
    {
        return false;
    }
    int index = SQ->front;
    while (index != SQ->rear)
    {
        cout << SQ->queue[index] << " ";
        index = (index + 1) % MAX_SIZE;
    }
    cout << endl;
    return false;
}
//计算元素个数
int getElemsNum(SeqQueue* SQ)
{
    if (!SQ)
    {
        return 0;
    }
    return (SQ->rear - SQ->front + MAX_SIZE) % MAX_SIZE;
}

优先队列

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

还是要对比顺序存储和链式存储rear指向位置。

顺序存储rear指向最后一个的下一个位置

链式存储rear指向最后一个

using namespace std;

#define MAX_SIZE 10

typedef int DataType;

typedef struct Qnode//结点结构
{
    int priority;//优先级
    DataType data;
    struct Qnode* next;
}Qnode;

typedef struct Queue//队列结构
{
    int length;
    Qnode* front;
    Qnode* rear;
}Queue;

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

}
//是否为空
bool isEmpty(Queue* Q)
{
    if (!Q)
    {
        return false;
    }
    if (Q->front == NULL)//空的，返回真，不空返回假，if(isEmprt(Q) != NULL)就是： 真的就直接return 
    {
        return true;
    }
    return false;
}
//是否满了
bool isFull(Queue* Q)
{
    if (!Q)
    {
        return false;
    }
    if (isEmpty(Q))
    {
        return false;
    }
    if (Q->length == MAX_SIZE)
    {
        return true;
    }
    return false;
}
//入队
bool pushQueue(Queue* Q, DataType _data, int _priority)
{
    if (!Q)
    {
        return false;
    }
    if (isFull(Q))
    {
        return false;   
    }

    Qnode* _node = new Qnode;
    _node->priority = _priority;
    _node->data = _data;
    _node->next = NULL;

    //空队列
    if (isEmpty(Q))
    {
        Q->front = Q->rear = _node;
    }
    else
    {
        Q->rear->next = _node;
        Q->rear = _node;//定位到新的结尾
    }
    Q->length++;

    return true;
}
//出队列——按照优先级
bool popQueue(Queue* Q)
{
    if (!Q || isEmpty(Q))
    {
        return false;
    }

    Qnode* recvPrev = NULL;//存储要删除结点的前一个结点
    Qnode* start = NULL;
    Qnode* startNext = NULL;
    Qnode* deleteTmp = NULL;

    start = Q->front;
    startNext = start->next;

    recvPrev = start;//默认要删除的是第二个,所以存的是第一个结点

    //特殊情况1，当前队列中就一个结点
    if (!startNext)
    {
        delete start;
        Q->front = Q->rear = NULL;
        Q->length--;
        return true;
    }

    //正常情况,完整的遍历一遍
    while (startNext)
    {
        if (startNext->priority > start->priority)
        {
            recvPrev = start;
        }
        start = startNext;
        startNext = startNext->next;        
    }

    //特殊情况2，第一个结点是优先级最高的
    //这样得到的recvPrev是第一个结点了，也有可能是为了删除第二个结点
    //所以要进行一下验证,验证是否要删除的是第一个结点
    Qnode* difFandS = NULL;
    difFandS = Q->front->next;
    if (recvPrev->priority > difFandS->priority)
    {
        //如果第一个结点的优先级大于第二个结点
        delete recvPrev;
        Q->front = difFandS;
        Q->length--;
        return true;
    }

    //出来后recvPrev就是要删除结点的前一个结点
    deleteTmp = recvPrev->next;
    recvPrev->next = deleteTmp->next;
    delete deleteTmp;

    Q->length--;
    return true;
}
//打印
bool printQueue(Queue* Q)
{
    if (!Q)
    {
        return false;
    }
    //补充提示注意:根据具体的返回内容来书写判断语句条件
    if (isEmpty(Q))//空的，返回真，不空返回假，if(isEmprt(Q))就是： 返回了真的就直接return 
    {
        cout << "空的，别打印了" << endl;
        return false;
    }
    Qnode* tempnode = Q->front;
    while (tempnode)
    {
        cout << "<" << tempnode->data << "," << tempnode->priority << ">" << " ";
        tempnode = tempnode->next;
    }
    cout << endl;
    return true;
}
//清空整个队列
bool clearQueue(Queue* Q)
{
    if (!Q)
    {
        return false;
    }

    Qnode* tempnode = NULL;
    while (Q->front)
    {
        tempnode = Q->front->next;
        delete Q->front;
        Q->front = tempnode;
    }

    Q->front = Q->rear = NULL;
    Q->length = 0;
    return false;

}

动态顺序队列

使用链式存储(链表)实现的队列即为动态顺序队列，前面已经实现过，不再重复。

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

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

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

当缓存的文件数达到一定程度的时候就会采取淘汰机制，

优先淘汰进入时间比较久或是最近访问很少(LRU)的队列文件。

具体实现方案：

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

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

如果要采用按照 LRU(进入时间 or 最近访问较少)，就遍历链表，找到节点删除。