队列的数据结构

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