队列：

先进先出，处理类似排队的问题，先排的。先处理，后排的等前面的处理完了，再处理

对于插入和移除操作的时间复杂度都为O(1)。从后面插入，从前面移除

双端队列：

即在队列两端都能够insert和remove：insertLeft、insertRight。removeLeft、removeRight

含有栈和队列的功能，如去掉insertLeft、removeLeft，那就跟栈一样了。如去掉insertLeft、removeRight。那就跟队列一样了

一般使用频率较低，时间复杂度 O(1)

优先级队列：

内部维护一个按优先级排序的序列。插入时须要比較查找插入的位置，时间复杂度O(N)， 删除O(1)

/*

 * 队列	先进先出。一个指针指示插入的位置，一个指针指示取出数据项的位置

 */

public class QueueQ<T> {

	private int max;

	private T[] ary;

	private int front; //队头指针  指示取出数据项的位置

	private int rear;  //队尾指针  指示插入的位置

	private int nItems; //实际数据项个数

	public QueueQ(int size) {

		this.max = size;

		ary = (T[]) new Object[max];

		front = 0;

		rear = -1;

		nItems = 0;

	}

	//插入队尾

	public void insert(T t) {

		if (rear == max - 1) {//已到实际队尾，从头開始

			rear = -1;

		}

		ary[++rear] = t;

		nItems++;

	}

	//移除队头

	public T remove() {

		T temp = ary[front++];

		if (front == max) {//列队到尾了，从头開始

			front = 0;

		}

		nItems--;

		return temp;

	}

	//查看队头

	public T peek() {

		return ary[front];

	}

	public boolean isEmpty() {

		return nItems == 0;

	}

	public boolean isFull() {

		return nItems == max;

	}

	public int size() {

		return nItems;

	}

	public static void main(String[] args) {

		QueueQ<Integer> queue = new QueueQ<Integer>(3);

		for (int i = 0; i < 5; i++) {

			queue.insert(i);

			System.out.println("size:" + queue.size());

		}

		for (int i = 0; i < 5; i++) {

			Integer peek = queue.peek();

			System.out.println("peek:" + peek);

			System.out.println("size:" + queue.size());

		}

		for (int i = 0; i < 5; i++) {

			Integer remove = queue.remove();

			System.out.println("remove:" + remove);

			System.out.println("size:" + queue.size());

		}

		System.out.println("----");

		for (int i = 5; i > 0; i--) {

			queue.insert(i);

			System.out.println("size:" + queue.size());

		}

		for (int i = 5; i > 0; i--) {

			Integer peek = queue.peek();

			System.out.println("peek:" + peek);

			System.out.println("size:" + queue.size());

		}

		for (int i = 5; i > 0; i--) {

			Integer remove = queue.remove();

			System.out.println("remove:" + remove);

			System.out.println("size:" + queue.size());

		}

	}

}

/*

 * 双端队列<span style="white-space:pre">	</span>两端插入、删除

 */

public class QueueQT<T> {

	private LinkedList<T> list;

	public QueueQT() {

		list = new LinkedList<T>();

	}

	// 插入队头

	public void insertLeft(T t) {

		list.addFirst(t);

	}

	// 插入队尾

	public void insertRight(T t) {

		list.addLast(t);

	}

	// 移除队头

	public T removeLeft() {

		return list.removeFirst();

	}

	// 移除队尾

	public T removeRight() {

		return list.removeLast();

	}

	// 查看队头

	public T peekLeft() {

		return list.getFirst();

	}

	// 查看队尾

	public T peekRight() {

		return list.getLast();

	}

	public boolean isEmpty() {

		return list.isEmpty();

	}

	public int size() {

		return list.size();

	}

}

/*

 * 优先级队列	队列中按优先级排序。是一个有序的队列

 */

public class QueueQP {

	private int max;

	private int[] ary;

	private int nItems; //实际数据项个数

	public QueueQP(int size) {

		this.max = size;

		ary =  new int[max];

		nItems = 0;

	}

	//插入队尾

	public void insert(int t) {

		int j;

		if (nItems == 0) {

			ary[nItems++] = t;

		} else {

			for (j = nItems - 1; j >= 0; j--) {

				if (t > ary[j]) {

					ary[j + 1] = ary[j]; //前一个赋给后一个  小的在后		相当于用了插入排序。给定序列本来就是有序的。所以效率O(N)

				} else {

					break;

				}

			}

			ary[j + 1] = t;

			nItems++;

		}

		System.out.println(Arrays.toString(ary));

	}

	//移除队头

	public int remove() {

		return ary[--nItems]; //移除优先级小的

	}

	//查看队尾 优先级最低的

	public int peekMin() {

		return ary[nItems - 1];

	}

	public boolean isEmpty() {

		return nItems == 0;

	}

	public boolean isFull() {

		return nItems == max;

	}

	public int size() {

		return nItems;

	}

	public static void main(String[] args) {

		QueueQP queue = new QueueQP(3);

		queue.insert(1);

		queue.insert(2);

		queue.insert(3);

		int remove = queue.remove();

		System.out.println("remove:" + remove);

	}

}