主页

队列的数据结构

#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;

版权属于:染念
作品采用:本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
14
查看目录

目录

来自 《c++ 队列》
评论

  1. 评论头像
    2022-09-06 回复

    →_→( ๑´•ω•) "(ㆆᴗㆆ)

        MacOS /    Google Chrome
  2. 评论头像
    2022-09-05 回复

    333333

        Windows 10 /    Google Chrome
  3. 评论头像
    2022-09-05 回复

    测试测试

        Windows 10 /    Google Chrome
  4. 评论头像
    染念 作者
    2022-08-21 回复

    测试评论

        Windows 10 /    Google Chrome

染念

博主很懒,啥都没有
152 文章数
546 评论量
4 分类数
156 页面数
已在风雨中度过 5年232天17小时35分
© 2022 染念的笔记
浙ICP备19020194号-1