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