一、什么是队列？

队列是一种特殊的线性表，单向队列只能在一端插入数据（后），另一端删除数据（前）；它和栈一样，队列是一种操作受限制的线性表；进行插入操作的称为队尾，进行删除操作的称为队头；队列中的数据被称为元素；没有元素的队列称为空队列。

由于只能一端删除或者插入，所以只有最先进入队列的才能被删除，因此又被称为先进先出（FIFO—first in first out）线性表。

队列分为两种：双向队列和单向队列 

单向队列：只能在一端删除数据，另一端插入数据。

双向队列：两端都可以进行插入数据和删除数据操作。

二、java单向队列模拟实现

package com.lzw.demo;

/**
 * @author lzw
 * @Date 2019年5月15日
 */
public class MyQueue {

	  	private Object[] queArray;
	    //队列总大小
	    private int maxSize;
	    //前端
	    private int front;
	    //后端
	    private int rear;
	    //队列中元素的实际数目
	    private int nItems;
	     
	    public MyQueue(int s){
	        maxSize = s;
	        queArray = new Object[maxSize];
	        front = 0;
	        rear = -1;
	        nItems = 0;
	    }
	     
	    //队列中新增数据
	    public void insert(int value){
	        if(isFull()){
	            System.out.println("队列已满！！！");
	        }else{
	            //如果队列尾部指向顶了，那么循环回来，执行队列的第一个元素
	            if(rear == maxSize -1){
	                rear = -1;
	            }
	            //队尾指针加1，然后在队尾指针处插入新的数据
	            queArray[++rear] = value;
	            nItems++;
	        }
	    }
	     
	    //移除数据
	    public Object remove(){
	        Object removeValue = null ;
	        if(!isEmpty()){
	            removeValue = queArray[front];
	            queArray[front] = null;
	            front++;
	            if(front == maxSize){
	                front = 0;
	            }
	            nItems--;
	            return removeValue;
	        }
	        return removeValue;
	    }
	     
	    //查看对尾数据
	    public Object peekRear(){
	        return queArray[rear];
	    }
	    
	    //查看对头数据
	    public Object peekFront(){
	        return queArray[front];
	    }
	     
	     
	    //判断队列是否满了
	    public boolean isFull(){
	        return (nItems == maxSize);
	    }
	     
	    //判断队列是否为空
	    public boolean isEmpty(){
	        return (nItems ==0);
	    }
	     
	    //返回队列的大小
	    public int getSize(){
	        return nItems;
	    }

	
	public static void main(String[] args) {
		 	MyQueue queue = new MyQueue(3);
	        queue.insert(1);
	        System.out.println("队列大小:"+queue.getSize());
	        queue.insert(2);
	        System.out.println("队列大小:"+queue.getSize());
	        queue.insert(3);//queArray数组数据为[1,2,3]
	        System.out.println("队列大小:"+queue.getSize());
	        System.out.println("队头:"+queue.peekFront()); //1
	        System.out.println("队尾:"+queue.peekRear());
	        queue.remove();//queArray数组数据为[null,2,3]
	        System.out.println(queue.peekFront()); //2
	        System.out.println("队列大小:"+queue.getSize());
	        queue.insert(4);//queArray数组数据为[4,2,3]
	        queue.insert(5);//队列已满,queArray数组数据为[4,2,3]
	        System.out.println("队列大小:"+queue.getSize());
	        System.out.println("队头:"+queue.peekFront());
	        System.out.println("队尾:"+queue.peekRear());

	}

}


三、双向队列 

双向队列就是队列的两端都可以进行删除和插入的操作。

package com.lzw.demo;

import java.util.LinkedList;

/**
 * @author lzw
 * @param <T>
 * @Date 2019年5月15日
 */
public class Deque<T> {

	private LinkedList<T> deque = new LinkedList<T>();

	/**从队头插入元素*/
	public void addFirst(T e) {
		deque.addFirst(e);
	}
	/**从队尾插入元素*/
	public void addLast(T e) {
		deque.addLast(e);
	}
	/**获取第一个元素*/
	public T getFirst(T e) {
		return deque.getFirst();
	}
	/**获取最后一个元素*/
	public T getLast(T e) {
		return deque.getLast();
	}
	/**从队头移出元素*/
	public T removeFirst() {
		return deque.removeFirst();
	}
	/**从队尾移出元素*/
	public T removeLast() {
		return deque.removeLast();
	}
	/**获取队列的大小*/
	public int size() {
		return deque.size();
	}

	public String toString() {
		return deque.toString();
	}

	
	public static void fillTest(Deque<Integer> de) {
		for (int i = 10; i < 17; i++)
			de.addFirst(i);
		for (int i = 50; i < 55; i++)
			de.addLast(i);
	}

	public static void main(String[] args) {
		Deque<Integer> deque = new Deque<Integer>();
		fillTest(deque);
		System.out.println(deque);
		while (deque.size() != 0)
			System.out.print(deque.removeFirst() + "  ");
		System.out.println();
		fillTest(deque);
		while (deque.size() != 0)
			System.out.print(deque.removeLast() + "  ");
		System.out.println();

	}

}


 

                                                  C++数据结构——队列

 

参考博客：

 数据结构图文解析之：队列详解与C++模板实现
	
 C++ stl队列Queue用法介绍:删除，插入等操作代码举例
 

1、队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点：

（1）队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构；

（2）在队尾添加元素，在队头删除元素。

2、队列的相关概念：

（1）队头与队尾： 允许元素插入的一端称为队尾，允许元素删除的一端称为队头；

（2）入队：队列的插入操作；

（3）出队：队列的删除操作。

3、队列的操作：

（1）入队： 通常命名为push()

（2）出队： 通常命名为pop()

（3）求队列中元素个数

（4）判断队列是否为空

（5）获取队首元素

4、队列的分类：

（1）基于数组的循环队列（循环队列）

（2）基于链表的队列（链队列）

5、实例分析

       C++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。C++队列Queue是一种容器适配器，它给予程序员一种先进先出(FIFO)的数据结构。

       那么我们如何判断队列是空队列还是已满呢？

      a、栈空： 队首标志=队尾标志时，表示栈空。

      b、栈满 : 队尾+1 = 队首时，表示栈满。

       使用标准库的队列时, 应包含相关头文件，在栈中应包含头文件： #include< queue> 。定义：queue< int > q;

q.empty()               如果队列为空返回true，否则返回false
q.size()                返回队列中元素的个数
q.pop()                 删除队列首元素但不返回其值
q.front()               返回队首元素的值，但不删除该元素
q.push()                在队尾压入新元素
q.back()                返回队列尾元素的值，但不删除该元素


（1）基于数组的循环队列（循环队列）

       以数组作为底层数据结构时，一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作。具体的示例图参考：http://www.cnblogs.com/QG-whz/p/5171123.html。

       循环队列，可以把数组看出一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。参考博客：【c++版数据结构】之循环队列的实现，判断循环队列是“空”还是“ 满”，有两种处理方法：

A. 设置状态标志位以区别空还是满
	
B. 少用一个元素，约定“队头front在队尾rear的下一个位置（指的是环的下一个位置）”作为“满”的标志
        C语言中，不能用动态分配的一维数组来实现循环队列，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；如果用户无法预估所用队列的最大长度，则宜采用链队列。

       定义front为队列头元素的位置，rear为队列尾元素的位置，MAXSIZE为循环队列的最大长度。注意以下几点，循环队列迎刃而解：

A.  求元素的个数：(rear - front + MAXSIZE) % MAXSIZE
	
B.  front/rear指向逻辑的下一个空间  front =（front+1)%MAXSIZE，rear = (rear+1)%MAXSIZE
	
C.  判空：front == rear
	
D.  判满：(rear+1+MAXSZIE) == front
 

例子1、简单的队列操作

#include <queue>
#include <iostream>
using namespace std;

int main(){
	queue<int> q;
	for (int i = 0; i < 10; i++){
		q.push(i);
	}
	if (!q.empty()){
		cout << "队列q非空！" << endl;
		cout << "q中有" << q.size() << "个元素" << endl;
	}
	cout << "队头元素为：" << q.front() << endl;
	cout << "队尾元素为：" << q.back() << endl;
	for (int j = 0; j < 10; j++){
		int tmp = q.front();
		cout << tmp << " ";
		q.pop();
	}
	cout << endl;
	if (!q.empty()){
		cout << "队列非空！" << endl;
	}
	system("pause");
	return 0;
}

运行结果：



 

 

例子2、循环队列的C++实现

#include <iostream>
#include <queue>
#include <string>
using namespace std;

template <typename T>
class LoopQueue
{
public:
	LoopQueue(int c = 10);
	~LoopQueue();
	bool isEmpty();        //队列的判空
	int size();            //队列的大小
	bool push(T t);        //入队列
	bool pop();            //出队列
	T front();            //队首元素

private:
	int capacity;
	int begin;
	int end;
	T*  queue;
};


template<typename T>
LoopQueue<T>::LoopQueue(int c = 10)
	:capacity(c), begin(0), end(0), queue(nullptr)
{
	queue = new T[capacity];
};

template<typename T>
LoopQueue<T>::~LoopQueue()
{
	delete[]queue;
}

template <typename T>
bool LoopQueue<T>::isEmpty()                   //判断循环队列是否为空
{
	if (begin == end)
		return true;
	return false;
};

template<typename T>
int LoopQueue<T>::size()
{
	return (end - begin + capacity) % capacity; //计算循环队列的长度
};

template<typename T>
bool LoopQueue<T>::push(T t)
{
	if (end + 1 % capacity == begin)            //判断队列是否已满
	{
		return false;
	}
	queue[end] = t;
	end = (end + 1) % capacity;
	return true;
};

template <typename T>
bool LoopQueue<T>::pop()                        //判断队列是否为空
{
	if (end == begin) 
	{
		return false;
	}
	begin = (begin + 1) % capacity;
	return true;
};

template <typename T>
T LoopQueue<T>::front()
{
	if (end == begin)
	{
		return false;
	}
	return queue[begin];
};

int main()
{
	LoopQueue<string> queue(6);
	queue.push("one");
	queue.push("two");
	queue.push("three");
	queue.push("four");
	queue.push("five");
	cout << "队列长度" << queue.size() << endl;
	while (!queue.isEmpty())
	{
		cout << queue.front() << endl;
		queue.pop();
	}
	getchar();
	//system("pause");
	return 0;
}

运行结果：



 

（2）基于链表的队列（链队列）

       链队列是基于链表实现的队列，它不存在数组的O(n)的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首，哪头做队尾。显然我们应该以链表头部为队首，链表尾部为队尾。存储一个指向队尾的指针，方便从链表尾插入元素；使用带头节点的链表，方便从链表头删除元素。

代码参考：链式队列的C++实现

#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;    //从头节点开始，一个一个删除队列结点，释放空间
		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++ 链队列和循环队列基本操作。

 

总结：

       1、循环队列中判断队空的方法是判断front==rear，队满的方法是判断front=（rear+1）%MAXSIZE。（为什么不用一个length表示队长，当length==maxSize时表示队满，原因就是，在频繁的队列操作中，多出一个变量会大量的增加执行时间，所以不如浪费一个数组空间来得划算。）

       2、用单链表表示的链式队列特别适合于数据元素变动较大的情形，而且不存在溢出的情况。

1  面试题
1.1 说说你对队列的理解，队列和集合的区别。
答：对队列的理解：
首先队列本身也是个容器，底层也会有不同的数据结构，比如 LinkedBlockingQueue 是底层是链表结构，所以可以维持先入先出的顺序，比如 DelayQueue 底层可以是队列或堆栈，所以可以保证先入先出，或者先入后出的顺序等等，底层的数据结构不同，也造成了操作实现不同；

部分队列（比如 LinkedBlockingQueue ）提供了暂时存储的功能，我们可以往队列里面放数据，同时也可以从队列里面拿数据，两者可以同时进行；

队列把生产数据的一方和消费数据的一方进行解耦，生产者只管生产，消费者只管消费，两者之间没有必然联系，队列就像生产者和消费者之间的数据通道一样，如 LinkedBlockingQueue；

队列还可以对消费者和生产者进行管理，比如队列满了，有生产者还在不停投递数据时，队列可以使生产者阻塞住，让其不再能投递，比如队列空时，有消费者过来拿数据时，队列可以让消费者 hodler 住，等有数据时，唤醒消费者，让消费者拿数据返回，如 ArrayBlockingQueue；

队列还提供阻塞的功能，比如我们从队列拿数据，但队列中没有数据时，线程会一直阻塞到队列有数据可拿时才返回。

队列和集合的区别：
和集合的相同点，队列（部分例外）和集合都提供了数据存储的功能，底层的储存数据结构是有些相似的，比如说 LinkedBlockingQueue 和 LinkedHashMap 底层都使用的是链表，ArrayBlockingQueue 和 ArrayList 底层使用的都是数组。
和集合的区别：
2.1 部分队列和部分集合底层的存储结构很相似的，但两者为了完成不同的事情，提供的 API 和其底层的操作实现是不同的。
2.2 队列提供了阻塞的功能，能对消费者和生产者进行简单的管理，队列空时，会阻塞消费者，有其他线程进行 put 操作后，会唤醒阻塞的消费者，让消费者拿数据进行消费，队列满时亦然。
2.3 解耦了生产者和消费者，队列就像是生产者和消费者之间的管道一样，生产者只管往里面丢，消费者只管不断消费，两者之间互不关心。
1.2 哪些队列具有阻塞的功能，大概是如何阻塞的？
答：队列主要提供了两种阻塞功能，如下：
LinkedBlockingQueue 链表阻塞队列和 ArrayBlockingQueue 数组阻塞队列是一类，前者容量是 Integer 的最大值，后者数组大小固定，两个阻塞队列都可以指定容量大小，当队列满时，如果有线程 put 数据，线程会阻塞住，直到有其他线程进行消费数据后，才会唤醒阻塞线程继续 put，当队列空时，如果有线程 take 数据，线程会阻塞到队列不空时，继续 take。

SynchronousQueue 同步队列，当线程 put 时，必须有对应线程把数据消费掉，put 线程才能返回，当线程 take 时，需要有对应线程进行 put 数据时，take 才能返回，反之则阻塞，举个例子，线程 A put 数据 A1 到队列中了，此时并没有任何的消费者，线程 A 就无法返回，会阻塞住，直到有线程消费掉数据 A1 时，线程 A 才能返回。
1.3 底层是如何实现阻塞的？
答：队列本身并没有实现阻塞的功能，而是利用 Condition 的等待唤醒机制，阻塞底层实现就是更改线程的状态为沉睡，细节我们在锁小节会说到。
1.4 LinkedBlockingQueue 和 ArrayBlockingQueue 有啥区别。
答：相同点：
两者的阻塞机制大体相同，比如在队列满、空时，线程都会阻塞住。

不同点：
LinkedBlockingQueue 底层是链表结构，容量默认是 Interge 的最大值，ArrayBlockingQueue 底层是数组，容量必须在初始化时指定。

两者的底层结构不同，所以 take、put、remove 的底层实现也就不同。
1.5 往队列里面 put 数据是线程安全的么？为什么？
答：是线程安全的，在 put 之前，队列会自动加锁，put 完成之后，锁会自动释放，保证了同一时刻只会有一个线程能操作队列的数据，以 LinkedBlockingQueue 为例子，put 时，会加 put 锁，并只对队尾 tail 进行操作，take 时，会加 take 锁，并只对队头 head 进行操作，remove 时，会同时加 put 和 take 锁，所以各种操作都是线程安全的，我们工作中可以放心使用。
1.6 take 的时候也会加锁么？既然 put 和 take 都会加锁，是不是同一时间只能运行其中一个方法。
答：1：是的，take 时也会加锁的，像 LinkedBlockingQueue 在执行 take 方法时，在拿数据的同时，会把当前数据删除掉，就改变了链表的数据结构，所以需要加锁来保证线程安全。
2：这个需要看情况而言，对于 LinkedBlockingQueue 来说，队列的 put 和 take 都会加锁，但两者的锁是不一样的，所以两者互不影响，可以同时进行的，对于 ArrayBlockingQueue 而言，put 和 take 是同一个锁，所以同一时刻只能运行一个方法。
1.7 工作中经常使用队列的 put、take 方法有什么危害，如何避免。
答：当队列满时，使用 put 方法，会一直阻塞到队列不满为止。
当队列空时，使用 take 方法，会一直阻塞到队列有数据为止。
两个方法都是无限（永远、没有超时时间的意思）阻塞的方法，容易使得线程全部都阻塞住，大流量时，导致机器无线程可用，所以建议在流量大时，使用 offer 和 poll 方法来代替两者，我们只需要设置好超时阻塞时间，这两个方法如果在超时时间外，还没有得到数据的话，就会返回默认值（LinkedBlockingQueue 为例），这样就不会导致流量大时，所有的线程都阻塞住了。
这个也是生产事故常常发生的原因之一，尝试用 put 和 take 方法，在平时自测中根本无法发现，对源码不熟悉的同学也不会意识到会有问题，当线上大流量打进来时，很有可能会发生故障，所以我们平时工作中使用队列时，需要谨慎再谨慎。
1.8 把数据放入队列中后，有木有办法让队列过一会儿再执行？
答：可以的，DelayQueue 提供了这种机制，可以设置一段时间之后再执行，该队列有个唯一的缺点，就是数据保存在内存中，在重启和断电的时候，数据容易丢失，所以定时的时间我们都不会设置很久，一般都是几秒内，如果定时的时间需要设置很久的话，可以考虑采取延迟队列中间件（这种中间件对数据会进行持久化，不怕断电的发生）进行实现。
1.9 DelayQueue 对元素有什么要求么，我把 String 放到队列中去可以么？
答：DelayQueue 要求元素必须实现 Delayed 接口，Delayed 本身又实现了 Comparable 接口，Delayed 接口的作用是定义还剩下多久就会超时，给使用者定制超时时间的，Comparable 接口主要用于对元素之间的超时时间进行排序的，两者结合，就可以让越快过期的元素能够排在前面。
所以把 String 放到 DelayQueue 中是不行的，编译都无法通过，DelayQueue 类在定义的时候，是有泛型定义的，泛型类型必须是 Delayed 接口的子类才行。
1.10 DelayQueue 如何让快过期的元素先执行的？
答：DelayQueue 中的元素都实现 Delayed 和 Comparable 接口的，其内部会使用 Comparable 的 compareTo 方法进行排序，我们可以利用这个功能，在 compareTo 方法中实现过期时间和当前时间的差，这样越快过期的元素，计算出来的差值就会越小，就会越先被执行。
1.11 如何查看 SynchronousQueue 队列的大小？
答：此题是个陷进题，题目首先设定了 SynchronousQueue 是可以查看大小的，实际上 SynchronousQueue 本身是没有容量的，所以也无法查看其容量的大小，其内部的 size 方法都是写死的返回 0。
1.12 SynchronousQueue 底层有几种数据结构，两者有何不同？
答：底层有两种数据结构，分别是队列和堆栈。
两者不同点：
队列维护了先入先出的顺序，所以最先进去队列的元素会最先被消费，我们称为公平的，而堆栈则是先入后出的顺序，最先进入堆栈中的数据可能会最后才会被消费，我们称为不公平的。

两者的数据结构不同，导致其 take 和 put 方法有所差别，具体的可以看 《 SynchronousQueue 源码解析 》章节。
1.13 假设 SynchronousQueue 底层使用的是堆栈，线程 1 执行 take 操作阻塞住了，然后有线程 2 执行 put 操作，问此时线程 2 是如何把 put 的数据传递给 take 的？
答：这是一个好问题，也是理解 SynchronousQueue 的核心问题。
首先线程 1 被阻塞住，此时堆栈头就是线程 1 了，此时线程 2 执行 put 操作，会把 put 的数据赋值给堆栈头的 match 属性，并唤醒线程 1，线程 1 被唤醒后，拿到堆栈头中的 match 属性，就能够拿到 put 的数据了。
严格上说并不是 put 操作直接把数据传递给了 take，而是 put 操作改变了堆栈头的数据，从而 take 可以从堆栈头上直接拿到数据，堆栈头是 take 和 put 操作之间的沟通媒介。
1.14 如果想使用固定大小的队列，有几种队列可以选择，有何不同？
答：可以使用 LinkedBlockingQueue 和 ArrayBlockingQueue 两种队列。
前者是链表，后者是数组，链表新增时，只要建立起新增数据和链尾数据之间的关联即可，数组新增时，需要考虑到索引的位置（takeIndex 和 putIndex 分别记录着下次拿数据、放数据的索引位置），如果增加到了数组最后一个位置，下次就要重头开始新增。
1.15 ArrayBlockingQueue 可以动态扩容么？用到数组最后一个位置时怎么办？
答：不可以的，虽然 ArrayBlockingQueue 底层是数组，但不能够动态扩容的。
假设 put 操作用到了数组的最后一个位置，那么下次 put 就需要从数组 0 的位置重新开始了。
假设 take 操作用到数组的最后一个位置，那么下次 take 的时候也会从数组 0 的位置重新开始。
1.16 ArrayBlockingQueue take 和 put 都是怎么找到索引位置的？是利用 hash 算法计算得到的么？
答：ArrayBlockingQueue 有两个属性，为 takeIndex 和 putIndex，分别标识下次 take 和 put 的位置，每次 take 和 put 完成之后，都会往后加一，虽然底层是数组，但和 HashMap 不同，并不是通过 hash 算法计算得到的。
2  总结
队列是锁、线程池等复杂 API 的基础，很多面试官都会在问这些 API 时冷不防的问你队列的知识，如果你回答不好，面试官可能会认为你仅仅是用过锁和线程池，但却对其底层的原理和实现了解的不够全面，所以说队列还是蛮重要的，但队列的源码比较复杂，建议大家可以尝试 debug 的方式来理解源码。

既然是队列那么先要包含头文件#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