这一章节我们来讨论一下队列（Queue）。

1.什么是队列？

队列是一种特殊的线性表，特殊之处在于它仅仅同意在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样。队列是一种操作受限制的线性表。

2.特性

（1）元素是有序的

（2）元素是先进先出

3.java里面的实现类：Linkedlist和PriorityQueue，两者之间性能不存在区别，区别的地方是排序的行为。

package com.ray.ch14;import java.util.LinkedList;import java.util.PriorityQueue;import java.util.Queue;public class Test {	public static <T> void test(Queue<T> queue, Generator<T> generator,			int count) {		for (int i = 0; i < count; i++) {			queue.add(generator.next());		}		while (queue.peek() != null) {			System.out.print(queue.remove() + " ");		}		System.out.println();	}	public static void main(String[] args) {		test(new LinkedList<String>(), new MyGenerator(), 10);		test(new PriorityQueue<String>(), new MyGenerator(), 10);	}}interface Generator<T> {	T next();}class MyGenerator implements Generator<String> {	private String str = "one two three four five six seven eight nine ten eleven";	private int index = 0;	@Override	public String next() {		if (index > str.split(" ").length) {			return "";		} else {			return str.split(" ")[index++];		}	}}

输出：

one two three four five six seven eight nine ten
eight five four nine one seven six ten three two

4.优先级队列

排序对象实现Comparable接口就可以。

package com.ray.ch14;import java.util.PriorityQueue;import java.util.Random;public class Test {	private static PriorityQueue<MyClass> priorityQueue = new PriorityQueue<MyClass>();	public static PriorityQueue<MyClass> test(int count) {		for (int i = 0; i < count; i++) {			priorityQueue.add(new MyClass(new Random().nextInt(10)));		}		return priorityQueue;	}	public static void main(String[] args) {		System.out.println(test(10));	}}class MyClass implements Comparable<MyClass> {	private int pri = 0;	public MyClass(int pri) {		this.pri = pri;	}	@Override	public int compareTo(MyClass myClass) {		if (this.pri < myClass.pri) {			return -1;		} else {			if (this.pri == myClass.pri) {				return 0;			} else {				return 1;			}		}	}	@Override	public String toString() {		return this.pri + "";	}}

输出：

[0, 1, 3, 3, 2, 5, 5, 6, 6, 7]

5.双向队列

特点：能够在不论什么一段加入或者删除元素。

因为在现有的java 里面没有实现双向队列的接口。可是在Linkedlist里面事实上已经模拟出来了。因此我们使用组合来模拟一下。

class Deque<T> {	private LinkedList<T> linkedList = new LinkedList<T>();	public void addFirst(T t) {		linkedList.addFirst(t);	}	public void addLast(T t) {		linkedList.addLast(t);	}	public void removeFirst() {		linkedList.removeFirst();	}	public void removeLast() {		linkedList.removeLast();	}}

总结：这一章节主要讲述队列的概念、特点。以及优先级和双向队列。

这一章节就到这里，谢谢。

-----------------------------------

文件夹