一、什么是队列？

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

由于只能一端删除或者插入，所以只有最先进入队列的才能被删除，因此又被称为先进先出（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();

	}

}


 

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 的方式来理解源码。

                                                  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、用单链表表示的链式队列特别适合于数据元素变动较大的情形，而且不存在溢出的情况。

消息队列中间件是分布式系统中重要的组件，主要解决应用耦合，异步消息，流量削锋等问题

实现高性能，高可用，可伸缩和最终一致性架构

使用较多的消息队列有ActiveMQ，RabbitMQ，ZeroMQ，Kafka，MetaMQ，RocketMQ

二、消息队列应用场景

以下介绍消息队列在实际应用中常用的使用场景。异步处理，应用解耦，流量削锋和消息通讯四个场景

2.1异步处理

场景说明：用户注册后，需要发注册邮件和注册短信。传统的做法有两种 1.串行的方式；2.并行方式

（1）串行方式：将注册信息写入数据库成功后，发送注册邮件，再发送注册短信。以上三个任务全部完成后，返回给客户端

 

（2）并行方式：将注册信息写入数据库成功后，发送注册邮件的同时，发送注册短信。以上三个任务完成后，返回给客户端。与串行的差别是，并行的方式可以提高处理的时间

 

假设三个业务节点每个使用50毫秒钟，不考虑网络等其他开销，则串行方式的时间是150毫秒，并行的时间可能是100毫秒。

因为CPU在单位时间内处理的请求数是一定的，假设CPU1秒内吞吐量是100次。则串行方式1秒内CPU可处理的请求量是7次（1000/150）。并行方式处理的请求量是10次（1000/100）


小结：如以上案例描述，传统的方式系统的性能（并发量，吞吐量，响应时间）会有瓶颈。如何解决这个问题呢？


引入消息队列，将不是必须的业务逻辑，异步处理。改造后的架构如下：

 

按照以上约定，用户的响应时间相当于是注册信息写入数据库的时间，也就是50毫秒。注册邮件，发送短信写入消息队列后，直接返回，因此写入消息队列的速度很快，基本可以忽略，因此用户的响应时间可能是50毫秒。因此架构改变后，系统的吞吐量提高到每秒20 QPS。比串行提高了3倍，比并行提高了两倍

2.2应用解耦

场景说明：用户下单后，订单系统需要通知库存系统。传统的做法是，订单系统调用库存系统的接口。如下图

 

传统模式的缺点：


	
假如库存系统无法访问，则订单减库存将失败，从而导致订单失败
	
	

	
订单系统与库存系统耦合
	

如何解决以上问题呢？引入应用消息队列后的方案，如下图：


 


	
订单系统：用户下单后，订单系统完成持久化处理，将消息写入消息队列，返回用户订单下单成功
	
	

	
库存系统：订阅下单的消息，采用拉/推的方式，获取下单信息，库存系统根据下单信息，进行库存操作
	
	

	
假如：在下单时库存系统不能正常使用。也不影响正常下单，因为下单后，订单系统写入消息队列就不再关心其他的后续操作了。实现订单系统与库存系统的应用解耦
	
2.3流量削锋

流量削锋也是消息队列中的常用场景，一般在秒杀或团抢活动中使用广泛

应用场景：秒杀活动，一般会因为流量过大，导致流量暴增，应用挂掉。为解决这个问题，一般需要在应用前端加入消息队列。


	
可以控制活动的人数
	
	

	
可以缓解短时间内高流量压垮应用
	
 


	
用户的请求，服务器接收后，首先写入消息队列。假如消息队列长度超过最大数量，则直接抛弃用户请求或跳转到错误页面
	
	

	
秒杀业务根据消息队列中的请求信息，再做后续处理
	
2.4日志处理

日志处理是指将消息队列用在日志处理中，比如Kafka的应用，解决大量日志传输的问题。架构简化如下

 


	
日志采集客户端，负责日志数据采集，定时写受写入Kafka队列
	
	

	
Kafka消息队列，负责日志数据的接收，存储和转发
	
	

	
日志处理应用：订阅并消费kafka队列中的日志数据
	
以下是新浪kafka日志处理应用案例：转自（http://cloud.51cto.com/art/201507/484338.htm）

 

(1)Kafka：接收用户日志的消息队列

(2)Logstash：做日志解析，统一成JSON输出给Elasticsearch

(3)Elasticsearch：实时日志分析服务的核心技术，一个schemaless，实时的数据存储服务，通过index组织数据，兼具强大的搜索和统计功能

(4)Kibana：基于Elasticsearch的数据可视化组件，超强的数据可视化能力是众多公司选择ELK stack的重要原因

2.5消息通讯

消息通讯是指，消息队列一般都内置了高效的通信机制，因此也可以用在纯的消息通讯。比如实现点对点消息队列，或者聊天室等

点对点通讯：

 

客户端A和客户端B使用同一队列，进行消息通讯。

聊天室通讯：

 

客户端A，客户端B，客户端N订阅同一主题，进行消息发布和接收。实现类似聊天室效果。

以上实际是消息队列的两种消息模式，点对点或发布订阅模式。模型为示意图，供参考。

三、消息中间件示例

3.1电商系统

 

消息队列采用高可用，可持久化的消息中间件。比如Active MQ，Rabbit MQ，Rocket Mq。

（1）应用将主干逻辑处理完成后，写入消息队列。消息发送是否成功可以开启消息的确认模式。（消息队列返回消息接收成功状态后，应用再返回，这样保障消息的完整性）

（2）扩展流程（发短信，配送处理）订阅队列消息。采用推或拉的方式获取消息并处理。

（3）消息将应用解耦的同时，带来了数据一致性问题，可以采用最终一致性方式解决。比如主数据写入数据库，扩展应用根据消息队列，并结合数据库方式实现基于消息队列的后续处理。

3.2日志收集系统

 

分为Zookeeper注册中心，日志收集客户端，Kafka集群和Storm集群（OtherApp）四部分组成。


	
Zookeeper注册中心，提出负载均衡和地址查找服务
	
	

	
日志收集客户端，用于采集应用系统的日志，并将数据推送到kafka队列
	
	

	
Kafka集群：接收，路由，存储，转发等消息处理
	
Storm集群：与OtherApp处于同一级别，采用拉的方式消费队列中的数据




四、JMS消息服务

讲消息队列就不得不提JMS 。JMS（Java Message Service,Java消息服务）API是一个消息服务的标准/规范，允许应用程序组件基于JavaEE平台创建、发送、接收和读取消息。它使分布式通信耦合度更低，消息服务更加可靠以及异步性。

在EJB架构中，有消息bean可以无缝的与JM消息服务集成。在J2EE架构模式中，有消息服务者模式，用于实现消息与应用直接的解耦。

4.1消息模型

在JMS标准中，有两种消息模型P2P（Point to Point）,Publish/Subscribe(Pub/Sub)。
4.1.1 P2P模式

 

P2P模式包含三个角色：消息队列（Queue），发送者(Sender)，接收者(Receiver)。每个消息都被发送到一个特定的队列，接收者从队列中获取消息。队列保留着消息，直到他们被消费或超时。

P2P的特点


	
每个消息只有一个消费者（Consumer）(即一旦被消费，消息就不再在消息队列中)
	
	

	
发送者和接收者之间在时间上没有依赖性，也就是说当发送者发送了消息之后，不管接收者有没有正在运行，它不会影响到消息被发送到队列
	
	

	
接收者在成功接收消息之后需向队列应答成功 
	
如果希望发送的每个消息都会被成功处理的话，那么需要P2P模式。（架构KKQ：466097527，欢迎加入）

4.1.2 Pub/sub模式

 

包含三个角色主题（Topic），发布者（Publisher），订阅者（Subscriber） 多个发布者将消息发送到Topic,系统将这些消息传递给多个订阅者。

Pub/Sub的特点


	
每个消息可以有多个消费者
	
	

	
发布者和订阅者之间有时间上的依赖性。针对某个主题（Topic）的订阅者，它必须创建一个订阅者之后，才能消费发布者的消息
	
	

	
为了消费消息，订阅者必须保持运行的状态
	
为了缓和这样严格的时间相关性，JMS允许订阅者创建一个可持久化的订阅。这样，即使订阅者没有被激活（运行），它也能接收到发布者的消息。

如果希望发送的消息可以不被做任何处理、或者只被一个消息者处理、或者可以被多个消费者处理的话，那么可以采用Pub/Sub模型。

4.2消息消费

在JMS中，消息的产生和消费都是异步的。对于消费来说，JMS的消息者可以通过两种方式来消费消息。

（1）同步

订阅者或接收者通过receive方法来接收消息，receive方法在接收到消息之前（或超时之前）将一直阻塞；

（2）异步

订阅者或接收者可以注册为一个消息监听器。当消息到达之后，系统自动调用监听器的onMessage方法。

 

JNDI：Java命名和目录接口,是一种标准的Java命名系统接口。可以在网络上查找和访问服务。通过指定一个资源名称，该名称对应于数据库或命名服务中的一个记录，同时返回资源连接建立所必须的信息。

JNDI在JMS中起到查找和访问发送目标或消息来源的作用。

4.3JMS编程模型

(1) ConnectionFactory

创建Connection对象的工厂，针对两种不同的jms消息模型，分别有QueueConnectionFactory和TopicConnectionFactory两种。可以通过JNDI来查找ConnectionFactory对象。

(2) Destination

Destination的意思是消息生产者的消息发送目标或者说消息消费者的消息来源。对于消息生产者来说，它的Destination是某个队列（Queue）或某个主题（Topic）;对于消息消费者来说，它的Destination也是某个队列或主题（即消息来源）。

所以，Destination实际上就是两种类型的对象：Queue、Topic可以通过JNDI来查找Destination。

(3) Connection

Connection表示在客户端和JMS系统之间建立的链接（对TCP/IP socket的包装）。Connection可以产生一个或多个Session。跟ConnectionFactory一样，Connection也有两种类型：QueueConnection和TopicConnection。

(4) Session

Session是操作消息的接口。可以通过session创建生产者、消费者、消息等。Session提供了事务的功能。当需要使用session发送/接收多个消息时，可以将这些发送/接收动作放到一个事务中。同样，也分QueueSession和TopicSession。

(5) 消息的生产者

消息生产者由Session创建，并用于将消息发送到Destination。同样，消息生产者分两种类型：QueueSender和TopicPublisher。可以调用消息生产者的方法（send或publish方法）发送消息。

(6) 消息消费者

消息消费者由Session创建，用于接收被发送到Destination的消息。两种类型：QueueReceiver和TopicSubscriber。可分别通过session的createReceiver(Queue)或createSubscriber(Topic)来创建。当然，也可以session的creatDurableSubscriber方法来创建持久化的订阅者。

(7) MessageListener

消息监听器。如果注册了消息监听器，一旦消息到达，将自动调用监听器的onMessage方法。EJB中的MDB（Message-Driven Bean）就是一种MessageListener。

 

深入学习JMS对掌握JAVA架构，EJB架构有很好的帮助，消息中间件也是大型分布式系统必须的组件。本次分享主要做全局性介绍，具体的深入需要大家学习，实践，总结，领会。

五、常用消息队列

一般商用的容器，比如WebLogic，JBoss，都支持JMS标准，开发上很方便。但免费的比如Tomcat，Jetty等则需要使用第三方的消息中间件。本部分内容介绍常用的消息中间件（Active MQ,Rabbit MQ，Zero MQ,Kafka）以及他们的特点。

5.1 ActiveMQ

ActiveMQ 是Apache出品，最流行的，能力强劲的开源消息总线。ActiveMQ 是一个完全支持JMS1.1和J2EE 1.4规范的 JMS Provider实现，尽管JMS规范出台已经是很久的事情了，但是JMS在当今的J2EE应用中间仍然扮演着特殊的地位。

ActiveMQ特性如下：

⒈ 多种语言和协议编写客户端。语言: Java,C,C++,C#,Ruby,Perl,Python,PHP。应用协议： OpenWire,Stomp REST,WS Notification,XMPP,AMQP

⒉ 完全支持JMS1.1和J2EE 1.4规范 （持久化，XA消息，事务)

⒊ 对spring的支持，Activ