队列的数据结构
#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;