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，但它相对没那么常用，在此就不做相关介绍了，有兴趣的读者可以自行学习！

巴特西

java集合类（六）About Queue

最新文章

热门文章