java集合类（六）About Queue

终于来到了java集合类的尾声，太兴奋了，不是因为可以休息一阵了，而是因为又到了开启新知识的时刻，大家一起加油打气！！Come on...Fighting！

About “interface Queue<E>”

All Superinterfaces:Collection<E>, Iterable<E>

All Known Subinterfaces:BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes:AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

先简要说明下队列：
之前，在“java集合类（三）About Iterator & Vector（Stack）”中讲到堆（heap）与栈（stack）的区别，现在讨论栈Stack与队列Queue的区别：
1）队列：FIFO先进先出，栈LIFO后进先出
2）队列：从队尾进对头出，栈：栈顶进栈顶出
3）遍历的速度不同：栈只能从栈顶取数，要得到最先入栈的元素，必须遍历这个栈，而且还需要开辟临时空间；队列则不同，它基于指针进行遍历，可以从对头或者队尾开始（不能同时），无需临时空间，遍历过程不影响数据结构，速度要快得多

Queue的实现：在学习LinkedList的时候，我们已知道LinkedList实现了Queue接口，所以今天的Queue也可以用LinkedList实现，并且LinkedList还实现了Stack（java集合类（三）About Iterator & Vector（Stack）提到），所以我们也可以设想能不能用Stack实现Queue？答案是肯定的，不过要用两个Stack才能实现！现在来看一个Queue的基础例子：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

/**
 * @author jp
 *@date 2013-12-16
 */
public class queuedemo {
    public static void printqueue(Queue queue) {
		while (queue.peek() != null) {
			System.out.print(queue.remove() + " ");
		}
		System.out.println();	
	}
	public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<Integer>();
        Random random  = new Random(32);
        for (int i = 0; i < 10; i++) 
			queue.offer(random.nextInt(i + 10));
		printqueue(queue);
		Queue<Character> qCharacters  = new LinkedList<Character>();
		for(char c: "GreatUniversity".toCharArray())
			qCharacters.offer(c);
		printqueue(qCharacters);
	}
}

Output：

7 7 5 9 9 2 9 3 0 2
G r e a t U n i v e r s i t y

说明：关于Queue的操作

	`Throws exception`	`Returns special value`
Insert	`add(e)`	`offer(e)`
Remove	`remove()`	`poll()`
Examine	`element()`	`peek()`

add（）& offer（）：在队尾插入元素，成功则返回true，失败则返回false，并且可能会会抛出IllegalStateException等；但offer（）不会抛出任何异常；

remove（）& poll（）：移除并返回对头元素，但在队列为空时，pull（）返回null，而remove（）则抛出NoSuchElementException；

element（） & peek（）：不移除并返回对头元素，但在队列为空时，peek（）返回null，而element（）则抛出NoSuchElementException；

About PriorityQueue：PriorityQueue与Queue的最基本的区别在于，优先级队列PriorityQueue具有顺序性；通常PriorityQueue用offer（）方法进行插入元素的时候，它的默认顺序是对象的自然顺序（数字小到大，字母按字母表），但程序员可以通过提供自己的Comparator修改默认排序，以确保在通过peek（），poll（），remove（）等方法获取元素时，得到的是具有最高优先级的的元素。另外，在学习数据结构堆排序的时候，老师跟我们讲得一般都是基于大顶堆而不是小顶堆，因为一般小顶堆通常用来实现维持优先级队列。下面举例说明：

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Set;

/**
 * @author jp
 *@date 2013-12-16
 */
public class priorityqueuedemo {
    public static void printqueue(Queue queue) {
		while (queue.peek() != null) {
			System.out.print(queue.remove() + " ");
		}
		System.out.println();	
	}
	public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
        Random random = new Random(32);
        for(int i = 0;i < 10; i++)
        	priorityQueue.offer(random.nextInt(i + 10));
        printqueue(priorityQueue);
        java.util.List<Integer> list = Arrays.asList(12,14,15,16,17,18,19,20);
        priorityQueue = new PriorityQueue<Integer>(list);
        printqueue(priorityQueue);
        priorityQueue = new PriorityQueue<Integer>(list.size(), Collections.reverseOrder());
        priorityQueue.addAll(list);
        printqueue(priorityQueue);
         
        String string = "i have a great dream";
        Set<Character> charset = new HashSet<Character>();
        for (char c: string.toCharArray()) {
			charset.add(c);
		}
        PriorityQueue<Character> pCharacters = new PriorityQueue<Character>(charset);
        printqueue(pCharacters);
	}
}

Output:

从最后一行可以看出：空格的优先级比一般的字母要高。下面看一个关于自己定义顺序，修改Comparator的例子：

import java.util.*;

class ToDoList extends PriorityQueue<ToDoList.ToDoItem> {

	static class ToDoItem implements Comparable<ToDoItem> {
		private char primary;
		private int secondary;
		private String item;

		public ToDoItem(String s, char c, int i) {
			primary = c;
			secondary = i;
			item = s;
		}

		/*
		 * @see java.lang.Comparable#compareTo(java.lang.Object)
		 * @implements Comparabale,then define the CompareTo()
		 * @function firstly compare "key value",then "secondary value"(+1,0,-1)
		 */
		public int compareTo(ToDoItem arg) {
            if(primary > arg.primary)
            	return +1;
            if(primary == arg.primary)
            	if(secondary > arg.secondary)
            		return +1;
            	else if(secondary == arg.secondary)
            		return 0;
			return -1;
		}
		
		public String toString() {
			return Character.toString(primary) + secondary +": " + item;
		}
	}
	
	public void add(String s, char c, int i) {
		super.add(new ToDoItem(s, c, i));
	}
	
	public static void  main(String[] args) {
		ToDoList toDoList = new ToDoList();
		toDoList.add("allen",'a',2);
		toDoList.add("jackson",'a',3);
		toDoList.add("davil",'b',3);
		toDoList.add("avily",'b',2);
		while (!toDoList.isEmpty()) {
			System.out.println(toDoList.remove());
		}
	}
}

output：

a2: allen
a3: jackson
b2: avily
b3: davil

除了一般的Queue和PriorityQueue，还有一种叫做双端队列Deque，但它相对没那么常用，在此就不做相关介绍了，有兴趣的读者可以自行学习！