AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】队列(C++)

2022-05-12 142
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】队列(C++)

队列

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

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

数组实现(顺序存储)

设立一个队头指针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;
}

实际应用

线程池中的任务队列

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cLqdaUda-1633952322505)(队列.assets/image-20211011090328793.png)]

循环队列

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gnXxCPJV-1633952322509)(队列.assets/image-20211011092439002.png)]

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

用模运算来循环

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4N7F8GmI-1633952322510)(队列.assets/image-20211011092958249.png)]

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)的队列文件。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sNN7ughq-1633952322512)(队列.assets/image-20211011183523476.png)]

具体实现方案：

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

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

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

文章标签：
Java
C++
应用服务中间件
nginx
缓存
存储
关键词：
数据结构队列
数据结构c++
半生瓜のblog
目录
相关文章
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
161 9
糜终
|
2月前
|
缓存 算法 调度
数据结构之 - 双端队列数据结构详解: 从基础到实现
数据结构之 - 双端队列数据结构详解: 从基础到实现
糜终
85 5
糜终
|
2月前
|
存储 算法 搜索推荐
探索常见数据结构：数组、链表、栈、队列、树和图
探索常见数据结构：数组、链表、栈、队列、树和图
糜终
115 64
龙大吉
|
19天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
42 5
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
25 1
禁默
|
2月前
初步认识栈和队列
初步认识栈和队列
禁默
61 10
java冯坚持
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列，数组模拟队列，模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
java冯坚持
26 0
数据结构与算法学习二、稀疏数组与队列，数组模拟队列，模拟环形队列
GuGuStudy
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
GuGuStudy
34 2
努力学习的小廉
|
2月前
【数据结构】--- 栈和队列
【数据结构】--- 栈和队列
努力学习的小廉
37 1
糜终
|
2月前
|
消息中间件 存储 Java
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
糜终
40 4