c++ 队列

简介: 队列的数据结构

队列的数据结构

#include <iostream>
#include <cstdlib>
using namespace std;
struct QNode    //定义队列结点的数据结构
{
    QNode *next; //指针域,指向下一个结点
    double data;    //数据域,存储队列信息
};
struct LinkQueue    //定义队列的数据结构
{
    QNode *front;      //队首指针,指向QNode类型的指针
    QNode *rear;       //队尾指针
};
void InitQueue(LinkQueue &Q)     //构造一个空的队列
{
    QNode *q;
    q = new QNode;    //申请一个结点的空间
    q->next = NULL;   //当作头结点
    //队首与队尾指针都指向这个结点,指针域为NULL
    Q.front = q;
    Q.rear = q;
}
int IsEmpty(LinkQueue &Q)    //判断队列是否为空
{
    if (Q.rear == Q.front)
        return 0;
    else
        return 1;
}
void EnQueue(LinkQueue &Q, double e)     //从队列尾部插入元素
{
    QNode *p;    //新创建一个结点
    p = new QNode;
    p->next = NULL;
    p->data = e;  //输入数据信息
    //将新结点插入队列尾部
    Q.rear->next = p;
    Q.rear = p;       //设置新的尾结点
}
void DeQueue(LinkQueue &Q, double &e)   //从队列首部删除一个结点
{
    QNode *p;
    p = Q.front->next;
    e = p->data;    //保存要出队列的数据
    Q.front->next = p->next;       //将下一个结点当作头结点后面链接的第一个结点
    if (Q.rear == p)    //如果要删除的元素即为尾结点,则将头指针赋予尾指针,一同指向头结点,表示队列为空
        Q.rear = Q.front;
    delete p;
}
void DestoryQueue(LinkQueue &Q)       //销毁一个队列
{
    while (Q.front)
    {
        Q.rear = Q.front->next;    //从头节点开始,一个一个删除队列结点,释放空间
        delete Q.front;
        Q.front = Q.rear;
    }
}
int main()
{
    LinkQueue *Q;  //定义一个队列Q
    Q = new LinkQueue;
    InitQueue(*Q);
    cout << "开始往队列里输入数据,以-1作为结束符" << endl;
    cout << "请输入一个数:" << endl;
    double a, x;
    cin >> a;
    while (a != -1)
    {
        EnQueue(*Q, a);
        cout << "请输入一个数:" << endl;
        cin >> a;
    }
    //输出队列元素,队首->队尾
    QNode *p;
    p = Q->front->next;
    if (p == NULL)     //如果为空表,直接退出
    {
        cout << "队列为空!" << endl;
        return 0;
    }
    cout << "队列数据依次为:" << endl;
    while (p != NULL)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
    //删除队列元素
    while (!IsEmpty(*Q))
    {
        DeQueue(*Q, x);
        cout << x << " ";
    }
    //释放内存空间
    delete Q->front;
    delete Q;
    system("pause");
    return 0;
}

队列 C++ STL

定义:queue<typename> 队列名字;

直接定义默认空队列,queue<int> q2(q1);还可以通过此方法复制

引用方法:

#include <queue> or #include <bits/stdc++.h>

用法:

q.front();        //获取队首
q.back();        //获取队尾
q.push(x);        //插入元素,x表示要插入的值,什么都行(但是类型必须和定义的相同)
q.pop();        //将队头弹出,无返回值
q.size();        //返回队列里有多少个元素
q.empty();        //如果队列为空,返回true,否则返回false( 等同于q.size()==0 )
q.swap(q2);        //交换q和q2里面的值(q2需要和q是一个类型)

双向队列

双向队列不仅可以在队尾插入,在队头删除,还可以在队头插入,在队尾删除,支持下标访问

缺点:速度慢

deque<typename> 双向队列名字;

引用:

#include <deque>
#include <queue>
因为在queue这个头文件里面包含了deque
万能头文件

使用:

q.push_front(x);    //在队头插入元素,x表示要插入的值,什么都行(但是类型必须和定义的相同)
q.push_back(x);        //在队尾插入元素,x表示要插入的值,什么都行(但是类型必须和定义的相同)
q.pop_front();        //将队头弹出,无返回值
q.pop_back();        //将队尾弹出,无返回值
q.front();        //和queue的一样
q.back();        //和queue的一样
q.size();        //和queue的一样
q.empty();        //和queue的一样
q.swap(q2);        //和queue的一样
q[i]        //获取第i个元素(队头是第0个)
q.at(i);    //同上(不同的地方很少)
q.clear();        //清空双向队列
q.begin();        //获取首地址,返回迭代器 (待会说怎么用)
q.end();        //获取位地址+1 注意!还要加1
还有很多......

优先队列

Queue是一个先进先出(FIFO)的队列。

在银行柜台办业务时,我们假设只有一个柜台在办理业务,但是办理业务的人很多,怎么办?

可以每个人先取一个号,例如:A1、A2、A3……然后,按照号码顺序依次办理,实际上这就是一个 Queue。

如果这时来了一个VIP客户,他的号码是V1,虽然当前排队的是A10、A11、A12……但是柜台下一个呼叫的客户号码却是V1。

这个时候,我们发现,要实现“VIP插队”的业务,用 Queue 就不行了,因为 Queue 会严格按 FIFO 的原则取出队首元素。

我们需要的是优先队列:PriorityQueue。

PriorityQueue 和 Queue 的区别在于,它的出队顺序与元素的优先级有关

优先队列保证队头最大(想最小也行)但内部排列随意,每次删除都会把接下来最大or最小的放上来

定义办法:

priority_queue<Type, Container, Functional>
Type 是数据类型;Container 是容器类型,一般使用vector;Functional 是比较的方式。

引用方法同队列

方法:

q.push(x);            //插入元素到队尾并排序,x表示要插入的值,什么都行(但是类型必须和定义的相同)
q.pop();            //将队头弹出,无返回值
q.top();            //和queue的一样
q.size();            //和queue的一样
q.empty();            //和queue的一样

接下来介绍如何让优先队列的队头最小或者最大

我们首先要知道这样的概念:

大顶堆:字面意思,根(顶)最大的堆。

小顶堆:根(顶)最小的堆。

//_________________默认为大顶堆_________________
priority_queue<int> q1;
//_________________标准一般写法_________________
//小顶堆,队头最小
priority_queue<int,vector<int>,greater<int> > q2;
//大顶堆
priority_queue<int,vector<int>,less<int> >q3;

目录
相关文章
|
9天前
|
设计模式 算法 C++
【C++初阶】12. Stack(栈)和Queue(队列)
【C++初阶】12. Stack(栈)和Queue(队列)
43 3
|
9天前
|
算法 调度 C++
【C/C++ 数据结构 线性表】C/C++中队列的原理与实现:从基础到循环队列
【C/C++ 数据结构 线性表】C/C++中队列的原理与实现:从基础到循环队列
45 0
|
9天前
|
设计模式 C++ iOS开发
【C++】STL容器适配器入门:【堆】【栈】【队列】(16)
【C++】STL容器适配器入门:【堆】【栈】【队列】(16)
【C++】STL容器适配器入门:【堆】【栈】【队列】(16)
|
9天前
|
存储 设计模式 C语言
C++中的栈和队列
C++中的栈和队列
15 0
|
9天前
|
存储 设计模式 算法
【C++/STL】stack和queue(容器适配器、优先队列、双端队列)
【C++/STL】stack和queue(容器适配器、优先队列、双端队列)
17 1
|
9天前
|
设计模式 C语言 C++
【C++进阶(六)】STL大法--栈和队列深度剖析&优先级队列&适配器原理
【C++进阶(六)】STL大法--栈和队列深度剖析&优先级队列&适配器原理
|
9天前
|
算法 数据安全/隐私保护 C++
【C/C++ 编程题 03】用两个栈实现一个队列的功能
【C/C++ 编程题 03】用两个栈实现一个队列的功能
17 0
|
9天前
|
算法 编译器 C语言
【C/C++ 编程题 02】用两个栈实现一个队列的功能
【C/C++ 编程题 02】用两个栈实现一个队列的功能
21 0
|
9天前
|
安全 算法 调度
C++队列探秘:队列容器的使用技巧与实战案例解析
C++队列探秘:队列容器的使用技巧与实战案例解析
136 0
|
9天前
|
Rust
2023年博客之星入围选拔重装开启——今年没有拉票环节啦
2023年博客之星入围选拔重装开启——今年没有拉票环节啦
32 0
2023年博客之星入围选拔重装开启——今年没有拉票环节啦