java集合类（六）About Queue

比眉伴天荒 2021-12-17 08:13 258阅读 0赞

[接上篇“java集合类（五）About Map”][java_About Map]

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

*  About “interface Queue<E>”

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

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

All Known Implementing Classes: [AbstractQueue][Collection], [ArrayBlockingQueue][Collection], [ArrayDeque][Collection], [ConcurrentLinkedDeque][Collection], [ConcurrentLinkedQueue][Collection], [DelayQueue][Collection], [LinkedBlockingDeque][Collection], [LinkedBlockingQueue][Collection], [LinkedList][Collection], [LinkedTransferQueue][Collection], [PriorityBlockingQueue][Collection], [PriorityQueue][Collection], [SynchronousQueue][Collection] 先简要说明下队列： 之前，在“ [java集合类（三）About Iterator & Vector（Stack）][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）提到][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的操作

<table style="width:537px;"> 
 <tbody> 
  <tr> 
   <td>&nbsp;</td> 
   <td style="text-align:center;"><span style="font-family:arial, helvetica, sans-serif;"><code>Throws exception</code></span></td> 
   <td style="text-align:center;"><code><span style="font-family:'宋体';">Returns special value</span></code></td> 
  </tr> 
  <tr> 
   <td><strong>Insert</strong></td> 
   <td style="text-align:center;"><a href="http://www.cnblogs.com/allenpengyu/admin/" rel="nofollow"><code>add(e)</code></a></td> 
   <td style="text-align:center;"><a href="http://www.cnblogs.com/allenpengyu/admin/" rel="nofollow"><code>offer(e)</code></a></td> 
  </tr> 
  <tr> 
   <td><strong>Remove</strong></td> 
   <td style="text-align:center;"><a href="http://www.cnblogs.com/allenpengyu/admin/" rel="nofollow"><code>remove()</code></a></td> 
   <td style="text-align:center;"><a href="http://www.cnblogs.com/allenpengyu/admin/" rel="nofollow"><code>poll()</code></a></td> 
  </tr> 
  <tr> 
   <td><strong>Examine</strong></td> 
   <td style="text-align:center;"><a href="http://www.cnblogs.com/allenpengyu/admin/" rel="nofollow"><code>element()</code></a></td> 
   <td style="text-align:center;"><a href="http://www.cnblogs.com/allenpengyu/admin/" rel="nofollow"><code>peek()</code></a></td> 
  </tr> 
 </tbody> 
</table>

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（）等方法获取元素时，得到的是具有最高优先级的的元素。另外，在学习数据结构[堆排序][Link 1]的时候，老师跟我们讲得一般都是基于大顶堆而不是小顶堆，因为一般小顶堆通常用来实现维持优先级队列。下面举例说明：

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:

![16191245-1cbd40e47f8d4b838c47b1ad64da42fc.png][]

从最后一行可以看出：空格的优先级比一般的字母要高。下面看一个关于自己定义顺序，修改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，但它相对没那么常用，在此就不做相关介绍了，有兴趣的读者可以自行学习！

转载于:https://www.cnblogs.com/allenpengyu/p/3467199.html

[java_About Map]: http://www.cnblogs.com/allenpengyu/p/3465678.html
[Collection]: http://www.cnblogs.com/allenpengyu/admin/
[java_About Iterator _ Vector_Stack]: http://www.cnblogs.com/allenpengyu/p/3462928.html
[Link 1]: http://baike.baidu.com/link?url=PiqIOq_oZVLGMAsny-bSYkn0ZXGSc-yN5LVKp_6cB_HvoCkURsUDVnVn8CscA32P
[16191245-1cbd40e47f8d4b838c47b1ad64da42fc.png]: /images/20211217/d0bfa50ab6a0423f8f992f3b799e9c51.png