既然是队列那么先要包含头文件#include <queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队
 
优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的
 
 
 
和队列基本操作相同:
 
 
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容
 
 
定义：priority_queue<Type, Container, Functional>
 Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆
 一般是：
 
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
 
 
基本类型例子：
 
#include<iostream>
#include <queue>
using namespace std;
int main() 
{
    //对于基础类型 默认是大顶堆
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;
    
  
    priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆
    priority_queue<string> b;

    for (int i = 0; i < 5; i++) 
    {
        a.push(i);
        c.push(i);
    }
    while (!a.empty()) 
    {
        cout << a.top() << ' ';
        a.pop();
    } 
    cout << endl;

    while (!c.empty()) 
    {
        cout << c.top() << ' ';
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while (!b.empty()) 
    {
        cout << b.top() << ' ';
        b.pop();
    } 
    cout << endl;
    return 0;
}
 
输出
 
4 3 2 1 0
0 1 2 3 4
cbd abcd abc
 
2.pari的比较，先比较第一个元素，第一个相等比较第二个
 
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() 
{
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << ' ' << a.top().second << '\n';
        a.pop();
    }
}
 
输出
 
2 5
1 3
1 2
 
3.对于自定义类型
 
#include <iostream>
#include <queue>
using namespace std;

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}
 
输出
 
3
2
1

3
2
1

优先队列
 
重要通知！！！！！！！！！！！！！
 优先队列没有back（）操作！！！！！
 误人子弟Crloss已经自毙了！！！！！
 同时更正了一些小问题。
 ——2018.11.03
 
引入
 
优先队列是一种特殊的队列，在学习堆排序的时候就有所了解，点“击”查看。
 
那么优先队列是什么呢？
 说白了，就是一种功能强大的队列。如果不太清楚队列，可以看看我这篇博客。
 
它的功能强大在哪里呢？
 四个字：自动排序。
 
优先队列的头文件&&声明
 
首先，你需要
 
#include<queue>
using namespace std;//这个不是头文件但我也不晓得叫什么专业定语反正要和头文件一起开就是了！
 
这两个头文件东西。
 
 
 
using namespace std; 这句话，代表，使用一个叫做“std”的namespace，namespace里面封存了一系列东西，比方说奇异的数据结构和奇异的函数。当打开了namespace以后，就跟打开了头文件的本质是一样的，都是可以直接用它里面封存的函数。
 不同之处在什么地方？就是不开namespace的使用，在你想用的（以std为例）函数面前加上“std::”即可。
 例如，std::sort(a+1,a+1+N); 之类的。
 感谢 @龙征天 的评论指点！
 
 
其次，一个优先队列声明的基本格式是：
 priority_queue<结构类型> 队列名;
 比如：
 
priority_queue <int> i;
priority_queue <double> d;
 
不过，我们最为常用的是这几种：
 
priority_queue <node> q;
//node是一个结构体
//结构体里重载了‘<’小于符号
priority_queue <int,vector<int>,greater<int> > q;
//不需要#include<vector>头文件
//注意后面两个“>”不要写在一起，“>>”是右移运算符
priority_queue <int,vector<int>,less<int> >q;
 
我们将在下文来讲讲这几种声明方式的不同。
 
优先队列的基本操作
 
与队列的基本操作如出一辙。
 如果想要了解请点击这里，看关于队列的介绍。
 
以一个名为q的优先队列为例。
 
q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
 
优先队列的特性
 
上文已经说过了，自动排序。
 怎么个排法呢？
 在这里介绍一下：
 
默认的优先队列（非结构体结构）
 
priority_queue <int> q;
 
这样的优先队列是怎样的？让我们写程序验证一下。
 
#include<cstdio>
#include<queue>
using namespace std;
priority_queue <int> q;
int main()
{
	q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);
	while(!q.empty())
		printf("%d ",q.top()),q.pop();
}
 
程序大意就是在这个优先队列里依次插入10、8、12、14、6，再输出。
 结果是什么呢？
 14 12 10 8 6
 也就是说，它是按从大到小排序的！
 
默认的优先队列（结构体，重载小于）
 
先看看这个结构体是什么。
 
struct node
{
	int x,y;
	bool operator < (const node & a) const
	{
		return x<a.x;
	}
};
 
这个node结构体有两个成员，x和y，它的小于规则是x小者小。
 再来看看验证程序：
 
#include<cstdio>
#include<queue>
using namespace std;
struct node
{
	int x,y;
	bool operator < (const node & a) const
	{
		return x<a.x;
	}
}k;
priority_queue <node> q;
int main()
{
	k.x=10,k.y=100; q.push(k);
	k.x=12,k.y=60; q.push(k);
	k.x=14,k.y=40; q.push(k);
	k.x=6,k.y=80; q.push(k);
	k.x=8,k.y=20; q.push(k);
	while(!q.empty())
	{
		node m=q.top(); q.pop();
		printf("(%d,%d) ",m.x,m.y);
	}
}
 
程序大意就是插入(10,100),(12,60),(14,40),(6,20),(8,20)这五个node。
 再来看看它的输出：
 (14,40) (12,60) (10,100) (8,20) (6,80)
 
它也是按照重载后的小于规则，从大到小排序的。
 ↑好好康康这句话！（摘眼镜）
 
less和greater优先队列
 
还是以int为例，先来声明：
 
priority_queue <int,vector<int>,less<int> > p;
priority_queue <int,vector<int>,greater<int> > q;
 
再次强调：“>”不要两个拼在一起。
 
话不多说，上程序和结果：
 
#include<cstdio>
#include<queue>
using namespace std;
priority_queue <int,vector<int>,less<int> > p;
priority_queue <int,vector<int>,greater<int> > q;
int a[5]={10,12,14,6,8};
int main()
{
	for(int i=0;i<5;i++)
		p.push(a[i]),q.push(a[i]);
		
	printf("less<int>:")；
	while(!p.empty())
		printf("%d ",p.top()),p.pop();	
		
	printf("\ngreater<int>:")；
	while(!q.empty())
		printf("%d ",q.top()),q.pop();
}
 
结果：
 less<int>:14 12 10 8 6 greater<int>:6 8 10 12 14
 
所以，我们可以知道，less是从大到小，greater是从小到大。
 
作个总结
 
为了装13方便，在平时，建议大家写：
 
priority_queue<int,vector<int>,less<int> >q;
priority_queue<int,vector<int>,greater<int> >q;
 
平时如果用从大到小不用后面的vector<int>,less<int>，可能到时候要改成从小到大，你反而会搞忘怎么写greater<int>，反而得不偿失。
 
另一种排序方法
 
有可能遇到这种情况：心情不好不想用重载小于一个结构体的优先队列，要按照各种不一样的规则排序。
 
当然，如果不是优先队列而是数组，我们就会多写几个bool函数塞到sort里面来改变它的小于规则，比如：
 
struct node
{
	int fir,sec;
}arr[2030];

bool cmp1(node x,node y)
{
	return x.fir<y.fir;  //当一个node x的fir值小于另一个node y的fir值时，称x<y
}

bool cmp2(node x,node y)
{
	return x.sec<y.sec;  //当一个node x的sec值小于另一个node y的sec值时，称x<y
}

bool cmp3(node x,node y)
{
	return x.fir+x.sec<y.fir+y.sec;  //当一个node x的fri值和sec值的和小于另一个node y的fir值和sec值的和时，称x<y
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d %d",&arr[i].fir,&arr[i].sec);
	
	puts("\n--------------------");
	sort(arr+1,arr+1+n,cmp1); for(int i=1;i<=n;i++) printf("%d. {%d %d}\n",i,arr[i].fir,arr[i].sec);
}

	puts("\n--------------------");
	sort(arr+1,arr+1+n,cmp2); for(int i=1;i<=n;i++) printf("%d. {%d %d}\n",i,arr[i].fir,arr[i].sec);
}

	puts("\n--------------------");
	sort(arr+1,arr+1+n,cmp3); for(int i=1;i<=n;i++) printf("%d. {%d %d}\n",i,arr[i].fir,arr[i].sec);
}
 
因为不是整体所以就省略了验证环节（也就是说上面那个代码的正确性不保证）
 
但是优先队列可没有sort那么灵活想用什么作小于规则用什么作小于规则，它只会用一个固定的小于规则。
 所以如果想把一个队列按不同的方式优先，就要：
 
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n;
struct node
{
	int fir,sec;
	void Read() {scanf("%d %d",&fir,&sec);}
}input;

struct cmp1
{
	bool operator () (const node &x,const node &y) const
	{
		return x.fir<y.fir;
	}
};//当一个node x的fir值小于另一个node y的fir值时，称x<y

struct cmp2
{
	bool operator () (const node &x,const node &y) const
	{
		return x.sec<y.sec;  
	}
};//当一个node x的sec值小于另一个node y的sec值时，称x<y

struct cmp3
{
	bool operator () (const node &x,const node &y) const
	{
		return x.fir+x.sec<y.fir+y.sec; 
	}
};//当一个node x的fri值和sec值的和小于另一个node y的fir值和sec值的和时，称x<y

priority_queue<node,vector<node>,cmp1> q1;
priority_queue<node,vector<node>,cmp2> q2;
priority_queue<node,vector<node>,cmp3> q3;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) input.Read(),q1.push(input),q2.push(input),q3.push(input);
	
	printf("\ncmp1:\n");
	while(!q1.empty()) printf("(%d,%d) ",q1.top().fir,q1.top().sec),q1.pop();	
		
	printf("\n\ncmp2:\n");
	while(!q2.empty()) printf("(%d,%d) ",q2.top().fir,q2.top().sec),q2.pop();	
		
	printf("\n\ncmp3:\n");
	while(!q3.empty()) printf("(%d,%d) ",q3.top().fir,q3.top().sec),q3.pop();	
}
 
读入：
 
7
1 2
2 1
6 9
9 6
-100 100
-500 20
4000 -3000
 
输出：
 
cmp1:
(4000,-3000) (9,6) (6,9) (2,1) (1,2) (-100,100) (-500,20)

cmp2:
(-100,100) (-500,20) (6,9) (9,6) (1,2) (2,1) (4000,-3000)

cmp3:
(4000,-3000) (6,9) (9,6) (1,2) (2,1) (-100,100) (-500,20)
 
我们可以发现啊，priority_queue <int,vector<int>,less<int> > p;的那个less<int>其实就代表这个优先队列的小于规则，所以把这个换成cmp1就会有上述效果，desu~
 所以说，所以说啦，一定要记得写全称！
 搞定！
 
总结
 
优先队列到此就作了个小结。
 其实不管是队列，还是优先队列，都不仅仅只有我讲的这些，还有更多可以探索。
 
应该入门级别都讲得差不多了，之后呢，在下就期待诸君的表演了。
 学，无止境。
 
 
UPD （2019.10.31）
 
可持久化阅读博客，点此查看历史版本
 现在你百度“优先队列”搜到的第一条，就是我UPD之前的历史版本了。
 其实是此人不动声色地把我标题里的“【原创】”拿掉了，挂了个转载就转走了。
 
话说在很久以前的很长一段时间，我啊一直是百度“优先队列”的第一条。不晓得是因为我改了名还是我修正了没有back操作的错误还是我的自定义栏目被csdn拿掉了，就刷下去了。
 当然看到我的历史版本很快顶替了这个位置我还是很高兴呢，我也把人们被那篇博客的称赞看作是对我自己的称赞，更喜的是一位哥们在那篇博客里评论了一句之后又点进超链接到我的博客下面又评论了一句一模一样的的。真的xswl。
 我之所以要写这几句话只是因为我最近太高兴了，几乎感觉不到压力，压力很小呢，就爱把正能量发泄出去。真的没有任何批评指责的意思，你看我这句话都没加粗。
 做人理应宽容大度，别人打你左脸还要伸右脸，亲亲，这边建议您把我的那些个超链接链接到的东西都转载过去哦。
 
反正是小事。
 一个小人物因为自己的小成就被另一个小人物取代了而在这里无意义的悻悻，传播正能量。
 $xswl$，$wxsl$。

一、队列（Queue）
 
Python的Queue模块中提供了同步的、线程安全的队列类，包括FIFO（先入先出)队列Queue，LIFO（后入先出）队列LifoQueue，和优先级队列PriorityQueue。这些队列都实现了锁原语，能够在多线程中直接使用。可以使用队列来实现线程间的同步。
 
常用方法：
 
Queue.qsize() 返回队列的大小
Queue.empty() 如果队列为空，返回True,反之False
Queue.full() 如果队列满了，返回True,反之False，Queue.full 与 maxsize 大小对应
Queue.get([block[, timeout]])获取队列，timeout等待时间
Queue.get_nowait() 相当于Queue.get(False)，非阻塞方法
Queue.put(item) 写入队列，timeout等待时间
Queue.task_done() 在完成一项工作之后，Queue.task_done()函数向任务已经完成的队列发送一个信号。每个get()调用得到一个任务，接下来task_done()调用告诉队列该任务已经处理完毕。
Queue.join() 实际上意味着等到队列为空，再执行别的操作
示例代码如下：
 
from Queue import Queue,LifoQueue,PriorityQueue
#先进先出队列
q=Queue(maxsize=5)
#后进先出队列
lq=LifoQueue(maxsize=6)
#优先级队列
pq=PriorityQueue(maxsize=5)

for i in range(5):
    q.put(i)
    lq.put(i)
    pq.put(i)
    
print "先进先出队列：%s;是否为空：%s；多大,%s;是否满,%s" %(q.queue,q.empty(),q.qsize(),q.full())
print "后进先出队列：%s;是否为空：%s;多大,%s;是否满,%s" %(lq.queue,lq.empty(),lq.qsize(),lq.full())
print "优先级队列：%s;是否为空：%s,多大,%s;是否满,%s" %(pq.queue,pq.empty(),pq.qsize(),pq.full())

print q.get(),lq.get(),pq.get()

print "先进先出队列：%s;是否为空：%s；多大,%s;是否满,%s" %(q.queue,q.empty(),q.qsize(),q.full())
print "后进先出队列：%s;是否为空：%s;多大,%s;是否满,%s" %(lq.queue,lq.empty(),lq.qsize(),lq.full())
print "优先级队列：%s;是否为空：%s,多大,%s;是否满,%s" %(pq.queue,pq.empty(),pq.qsize(),pq.full())
 
先进先出队列：deque([0, 1, 2, 3, 4]);是否为空：False；多大,5;是否满,True
后进先出队列：[0, 1, 2, 3, 4];是否为空：False;多大,5;是否满,False
优先级队列：[0, 1, 2, 3, 4];是否为空：False,多大,5;是否满,True
0 4 0
先进先出队列：deque([1, 2, 3, 4]);是否为空：False；多大,4;是否满,False
后进先出队列：[0, 1, 2, 3];是否为空：False;多大,4;是否满,False
优先级队列：[1, 3, 2, 4];是否为空：False,多大,4;是否满,False
 
 还有一种队列是双边队列，示例代码如下：
 
from Queue import deque
dq=deque(['a','b'])
dq.append('c')
print dq
print dq.pop()
print dq
print dq.popleft()
print dq
dq.appendleft('d')
print dq
print len(dq)
 
deque(['a', 'b', 'c'])
c
deque(['a', 'b'])
a
deque(['b'])
deque(['d', 'b'])
2
 
 二、生产者消费者模式
 
生产者消费者模式并不是GOF提出的众多模式之一，但它依然是开发同学编程过程中最常用的一种模式
 
 
生产者模块儿负责产生数据，放入缓冲区，这些数据由另一个消费者模块儿来从缓冲区取出并进行消费者相应的处理。该模式的优点在于：
 
解耦：缓冲区的存在可以让生产者和消费者降低互相之间的依赖性，一个模块儿代码变化，不会直接影响另一个模块儿
并发：由于缓冲区，生产者和消费者不是直接调用，而是两个独立的并发主体，生产者产生数据之后把它放入缓冲区，就继续生产数据，不依赖消费者的处理速度
三、采用生产者消费者模式开发的Python多线程
 
在Python中，队列是最常用的线程间的通信方法，因为它是线程安全的，自带锁。而Condition等需要额外加锁的代码操作，在编程对死锁现象要很小心，Queue就不用担心这个问题。
 
Queue多线程代码示例如下：
 
from Queue import Queue
import time,threading
q=Queue(maxsize=0)

def product(name):
    count=1
    while True:
        q.put('气球兵{}'.format(count))
        print ('{}训练气球兵{}只'.format(name,count))
        count+=1
        time.sleep(5)
def consume(name):
    while True:
        print ('{}使用了{}'.format(name,q.get()))
        time.sleep(1)
        q.task_done()
t1=threading.Thread(target=product,args=('wpp',))
t2=threading.Thread(target=consume,args=('ypp',))
t3=threading.Thread(target=consume,args=('others',))

t1.start()
t2.start()
t3.start()
 
网上还有很多非常好的生产者消费者模式的Queue代码例子，开发同学需要根据具体的实际需求去设计实际模式

Queue
 
Queue是python标准库中的线程安全的队列（FIFO）实现,提供了一个适用于多线程编程的先进先出的数据结构，即队列，用来在生产者和消费者线程之间的信息传递
 
基本FIFO队列
 
class Queue.Queue(maxsize=0)
 
FIFO即First in First Out,先进先出。Queue提供了一个基本的FIFO容器，使用方法很简单,maxsize是个整数，指明了队列中能存放的数据个数的上限。一旦达到上限，插入会导致阻塞，直到队列中的数据被消费掉。如果maxsize小于或者等于0，队列大小没有限制。
 
举个栗子：
 
import Queue

q = Queue.Queue()

for i in range(5):
    q.put(i)

while not q.empty():
    print q.get()
 
输出：
 
0
1
2
3
4
 
LIFO队列
 
class Queue.LifoQueue(maxsize=0)
 
LIFO即Last in First Out,后进先出。与栈的类似，使用也很简单,maxsize用法同上
 
再举个栗子：
 
import Queue

q = Queue.LifoQueue()

for i in range(5):
    q.put(i)

while not q.empty():
    print q.get()
 
输出：
 
4
3
2
1
0
 
可以看到仅仅是将Queue.Quenu类替换为Queue.LifiQueue类
 
优先级队列
 
class Queue.PriorityQueue(maxsize=0)
 
构造一个优先队列。maxsize用法同上。
 
import Queue
import threading

class Job(object):
    def __init__(self, priority, description):
        self.priority = priority
        self.description = description
        print 'Job:',description
        return
    def __cmp__(self, other):
        return cmp(self.priority, other.priority)

q = Queue.PriorityQueue()

q.put(Job(3, 'level 3 job'))
q.put(Job(10, 'level 10 job'))
q.put(Job(1, 'level 1 job'))

def process_job(q):
    while True:
        next_job = q.get()
        print 'for:', next_job.description
        q.task_done()

workers = [threading.Thread(target=process_job, args=(q,)),
        threading.Thread(target=process_job, args=(q,))
        ]

for w in workers:
    w.setDaemon(True)
    w.start()

q.join()
 
结果
 
Job: level 3 job
Job: level 10 job
Job: level 1 job
for: level 1 job
for: level 3 job
for: job: level 10 job
 
一些常用方法
 
task_done()
 
意味着之前入队的一个任务已经完成。由队列的消费者线程调用。每一个get()调用得到一个任务，接下来的task_done()调用告诉队列该任务已经处理完毕。
 
如果当前一个join()正在阻塞，它将在队列中的所有任务都处理完时恢复执行（即每一个由put()调用入队的任务都有一个对应的task_done()调用）。
 
join()
 
阻塞调用线程，直到队列中的所有任务被处理掉。
 
只要有数据被加入队列，未完成的任务数就会增加。当消费者线程调用task_done()（意味着有消费者取得任务并完成任务），未完成的任务数就会减少。当未完成的任务数降到0，join()解除阻塞。
 
put(item[, block[, timeout]])
 
将item放入队列中。
 
如果可选的参数block为True且timeout为空对象（默认的情况，阻塞调用，无超时）。
如果timeout是个正整数，阻塞调用进程最多timeout秒，如果一直无空空间可用，抛出Full异常（带超时的阻塞调用）。
如果block为False，如果有空闲空间可用将数据放入队列，否则立即抛出Full异常
其非阻塞版本为put_nowait等同于put(item, False)
 
get([block[, timeout]])
 
从队列中移除并返回一个数据。block跟timeout参数同put方法
 
其非阻塞方法为｀get_nowait()｀相当与get(False)
 
empty()
 
如果队列为空，返回True,反之返回False