Cpp的队列(Queue)学习笔记
队列是一种先入先出(First In First Out)的数据结构,它的实现用两个整型变量(Head、tail
)和一个存储数据的数组(Date[Num]
)来实现的。
自定义的数据结构体:
struct queue{
int date[Num];
int head;
int tail;
};
这里要注意的是结构体内定义的是类型和变量空间,所以最好不要在结构体内初始化
队列的操作总共有三种:
一、入列操作:
q.date[tail] = x;
tail++;
二、出列操作:
x = q.date[head];
head++;
三、判断非空操作:
head<tail;
STL(Queue)
C++语言的STL中自带了queue
的数据结构类型
Queue
的模板类封装在头文件中
Queue
模板类需要两个参数,一个是元素类型,一个是容器类型
(元素类型书必要的,容器类型是可选的,默认为deque类型)
一、队列对象的定义:
queue< int > q1;
queue< double > q2;
二、队列对象的操作:
-
入队:
q.push(x); // 将x放入队列的尾部
-
出列:
q.pop; // 弹出队列的头部数据
-
非空判断:
q.empty(); // 判断操作的返回值
-
访问队首元素:
q.front(); // 得到返回值
-
访问队尾元素:
q.back(); // 得到返回值
-
访问队列中的元素个数:
q.size(); // 返回元素个数的整型值
三、Priority_queue(优先队列)
在<queue>
的头文件中,除了queue
这个模板类之外,还定义了另外一个模板类priority_queue(优先队列)
优先队列和队列的区别在于优先队列不是按照队列入队的顺序出队,而是按照队列中元素的优先权顺序来出队(默认为大者优先,也可以通过指定算子来指定自己的优先顺序)。
priority_queue
模板类有三个参数:第一个是元素类型,第二个是容器类型,第三个是比较算子。其中后两个参数都可以省略,默认容器为vector
,默认算子为less
,即小的往前排,大的往后排(出队时序列尾的元素出队)。
-
定义priority_queue对象:
priority_queue< int > q1;
priority_queue< pair<int, int> > q2; // 注意在两个尖括号之间一定要留空格。
priority_queue<int, vector<int>, greater<int> > q3; // 定义小的先出队
priority_queue
的基本操作和queue
基本相同
初学者在使用priority_queue
时,最困难的可能就是如何定义比较算子了。 如果是基本数据类型,或已定义了比较运算符的类,可以直接用STL的less
算子和greater
算子——默认为使用less
算子,即小的往前排,大的先出队。
如果要定义自己的比较算子,方法有多种,这里介绍其中的一种:重载比较运算符。优先队 列试图将两个元素x 和y 代入比较运算符(对less
算子,调用x<y,对greater
算子,调用x>y),
若结果为真,则x 排在y 前面,y 将先于x 出队,反之,则将y 排在x 前面,x 将先出队。 看下面这个简单的示例:
#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c)
{
}
};
bool operator < (const T &t1, const T &t2)
{
return t1.z < t2.z; // 按照z 的顺序来决定t1 和t2 的顺序
}
main()
{
priority_queue<T> q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 1;
}
输出结果为(注意是按照z 的顺序从大到小出队的):
3 3 6
2 2 5
1 5 4
4 4 3
再看一个按照z 的顺序从小到大出队的例子:
#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c)
{
}
};
bool operator > (const T &t1, const T &t2)
{
return t1.z > t2.z;
}
main()
{
priority_queue<T, vector<T>, greater<T> > q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 1;
}
输出结果为:
4 4 3
1 5 4
2 2 5
3 3 6
如果我们把第一个例子中的比较运算符重载为:
bool operator < (const T &t1, const T &t2)
{
return t1.z > t2.z; // 按照z 的顺序来决定t1 和t2 的顺序
}
则第一个例子的程序会得到和第二个例子的程序相同的输出结果。
版权声明:本文为博主原创文章,未经博主允许不得转载。By PengCoX ( Pengc825@foxmail.com )
分享到:
相关推荐
这是c prime plus 第17章中的学习内容 此部分配和我写的队列的分析一起作为学习使用 biubiu
消息队列 Queue与Topic区别
Unity3d 队列 方法 Queue
设一循环队列Queue,只有头指针front,不设尾指针,另设一个内含元素个数的计数器,试写出相应的进队、出队算法。
主要介绍了C#队列Queue多线程用法,实例分析了队列的相关使用技巧,需要的朋友可以参考下
数据结构 严蔚敏 队列 queue
python 队列的使用 python2例程展示了队列的使用过程,供学习参考使用 队列:Queue queue_test.py put()函数主动改变队列 get()函数阻塞,代替查询 Produser & Consumer 定期生产,一有货就被抢购 ...
java 自定义Queue队列 java 自定义Queue队列
c++消息队列queue.rar
依次展开“Microsoft Message Queue (MSMQ) 服务器”、“Microsoft Message Queue (MSMQ) 服务器核心”, 然后选中要安装的消息队列功能的复选框。单击“确定”。 如果系统提示您重新启动计算机,请单击“确定”以...
Queue是python标准库中的线程安全的队列(FIFO)实现,提供了一个适用于多线程编程的先进先出的数据结构,即队列,用来在生产者和消费者线程之间的信息传递 基本FIFO队列 class Queue.Queue(maxsize=0) FIFO即First ...
队列类Queue的C++实现
基于C语言的数据结构-队列queue
队列Queue,先进先出,先生产的货物先出货,后生产的货物后出货,下面看示例学习c#队列Queue
delphi中关于队列的使用QUEUE,已在delphi7中调试通过。 学习queue的小例子。
C++实现队列
数据结构Queue的实现在queue.h中, testQ为queue的用法
基于python的数据结构代码实现-队列Queue
用C++类实现队列功能。 包含添加、删除、初始化。
本文实例分析了C#队列Queue用法。分享给大家供大家参考。具体分析如下: 队列(Queue)在程序设计中扮演着重要的角色,因为它可以模拟队列的数据操作。例如,排队买票就是一个队列操作,后来的人排在后面,先来的人...