queue是什么意思

C语⾔优先队列（priorityqueue）详解

0x00，优先队列（priorityqueue）

priorityqueue是⼀个⽤"堆"实现的，类似t的容器，有着queue的基本功能。特征是"具有优先级，可以按照优先级出队"

可能不是特别好理解，其实就是⼀个排序啦。。。

举个栗⼦：

3⼊队，4⼊队，1⼊队，如果是queue的容器，出队顺序为3,4,1，⽽priorityqueue则在内部会排好序，出队顺序为4,3,1。

这种数据结构在解决⼀些⾼级问题，例如贪⼼类问题，或者迪杰斯特拉算法，都可以更加⽅便的解决问题。

0x01，声明与操作

声明与操作和queue基本⼀样，例如这段程序：

#include

#include

usingnamespacestd;

intmain(){

priority_queueq;

(3);

(4);

(2);

cout<<();

return0;

}

输出的结果是4。

如果加上出队程序，出队的序列为4,3,2。

queue中的pop，size，empty等函数在priority_queue中仍然适⽤。

0x02，基本数据类型优先级的设置

在前⾯，priorityqueue默认的顺序总是数字⼤的优先级⾼，⽽如果我们需要⾃定义优先级呢

解决这⼀问题很简单，我们只需要改变⼀下定义priorityqueue的⽅式即可：

priority_queue,less>q;

这样，数字⼤的优先级⼤

在这⾥，三个ElementType的类型必须保持⼀致。这⾥vector是队列内部⽤于承载底层数据结构堆的容器，less是对第⼀个参数的⽐较

类。

less表⽰数字越⼤优先级越⼤（如果是char类型则根据ASCII码来判断），如果希望数字越⼩优先级越⼤，只需要将less换成greater即

可。例如

priority_queue,less>q;

要注意最后⼀个‘>’与下⼀个‘>’之间必须有空格。否则编译器会误认为是在做移位运算。

这⾥很容易记混，再次重复⼀遍：

less->数字⼤的优先级⼤，数字⼤被放在队⾸。所以先输出数字⼤的

greater->数字⼩的优先级⼤，数字⼩被放在队⾸。所以先输出数字⼩的

继续举栗⼦：

#include

#include

usingnamespacestd;

intmain(){

priority_queue,less>q;

(8);

(3);

(5);

while(!()){

cout<<()<

();

}

return0;

}

运⾏结果：

0x03，结构体的优先级设置

⽐如博主是个卖⽔果的，我希望写个程序，帮助我优先卖出贵的⽔果。

⾸先我定义⼀个结构体变量：

structfruit{

stringname;//⽔果名

intprice;//⽔果价格

};

如果我们直接把结构体压⼊priorityqueue，代码：

#include

#include

#include

usingnamespacestd;

structfruit{

stringname;

intprice;

}f1,f2,f3;

intmain(){

priority_queueq;

/*定义⽔果和价格*/

="桃⼦";=3;

="梨";=4;

="苹果";=1;

/*压⼊队列*/

(f1);(f2);(f3);

while(!()){

cout<<().name<<'t'<<().price<

();

}

return0;

}

得到的结果是这样的：

好吧，编译都通不过，⼤概的意思是，C++中，queue的操作库直接使⽤了⼩于号⽐较⼤⼩，⽽结构体之间不能使⽤⼩于号⽐较，所

以，boom。

这⾥我们可以重载⼩于号，也就是重新让编译器理解⼩于号的意思。

（⽐如编译器默认的⼩于号意思是直接⽐较⼩于号两边数字的⼤⼩，我们可以重新定义⼩于号，让编译器认为⼩于号是⽐较结构体中某些变

量的⼤⼩。如果还是没有太理解，可以想想algorithm头⽂件中sort函数。这⾥重新定义⼩于号，也就相当于定义sort函数中的cmp函数）

（这⾥必须重载⼩于号，不能重载⼤于号，因为从上图中可以看出，C++queue的库函数采⽤的是⼩于号，所以定义⼤于号是没⽤滴）

我们修改结构体的定义⽅式，使得重载⼩于号：

structfruit{

stringname;

intprice;

friendbooloperator<(fruitf1,fruitf2){//重新定义bool类型操作符‘<’，

//‘<’的两边分别是fruit类型的f1和f2

<;//操作符返回是否⼩鱼

}

}

这⾥friend的意思是"友元"。当然，你也可以把return后⾯的‘<’改为‘>’，这样就可以反着排序了。

#include

#include

#include

usingnamespacestd;

structfruit{

stringname;

intprice;

friendbooloperator<(fruitf1,fruitf2){

<;

}

}f1,f2,f3;

intmain(){

priority_queueq;

/*定义⽔果和价格*/

="桃⼦";=3;

="梨";=4;

="苹果";=1;

/*压⼊队列*/

(f1);(f2);(f3);

while(!()){

cout<<().name<<'t'<<().price<

();

}

return0;

}

结果：