天天看點

java 隊列、優先級隊列、雙向隊列示例示範代碼

java 隊列、優先級隊列、雙向隊列示例示範代碼

package org.rui.collection2.queues;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.PriorityBlockingQueue;

import org.rui.generics.anonymity.Generator;
/**
 * 下面涉及Queue實作的大部分操作的基本示例
 * 可以看到除了優先隊列,Queue将精确地按照元素被置于Queue中的順序産生它們
 * @author lenovo
 *
 */
public class QueueBeHavior {
	private static int count=10;
	static<T> void test(Queue<T> queue,Generator<T> gen)
	{
		for(int i=0;i<count;i++)
		{
			//T temp=gen.next();
			//System.out.println(temp);
			queue.offer(gen.next());
		}
		
		while(queue.peek()!=null)
			System.out.print(queue.remove()+"  ");
		    System.out.println();
	}

	static class Gen implements Generator<String>
	{
		String[] s=
		("one tow three four five six seven eight nine ten".split(" "));
		int i;

		public String next() 
		{
			return s[i++];
		}
	}
	
	public static void main(String[] args) 
	{
		test(new LinkedList<String>(),new Gen());
		test(new PriorityQueue<String>(),new Gen());
		test(new ArrayBlockingQueue<String>(count),new Gen());
		test(new ConcurrentLinkedQueue<String>(),new Gen());
		test(new LinkedBlockingQueue<String>(),new Gen());
		test(new PriorityBlockingQueue<String>(),new Gen());
	}
}
/**output:
one  tow  three  four  five  six  seven  eight  nine  ten  
eight  five  four  nine  one  seven  six  ten  three  tow  
one  tow  three  four  five  six  seven  eight  nine  ten  
one  tow  three  four  five  six  seven  eight  nine  ten  
one  tow  three  four  five  six  seven  eight  nine  ten  
eight  five  four  nine  one  seven  six  ten  three  tow 
 */
           
package org.rui.collection2.queues;

import java.util.PriorityQueue;

/**
 * 優先級隊列
 * 主要和次要的優先級排序
 * 該清單的排序順序也是通過實作Comparable而進行控制的
 * @author lenovo
 *
 */
public class ToDoList  extends PriorityQueue<ToDoList.ToDoItem>
{

	static class ToDoItem implements Comparable<ToDoItem>
	{
		private char primary;//主要的
		private int secondary;//二
		private String item;
		
		public ToDoItem(String item,char primary, int secondary) 
		{
			this.primary = primary;
			this.secondary = secondary;
			this.item = item;
		}
		
		public int compareTo(ToDoItem o) 
		{
			if(primary>o.primary)//先比較主要的
				return +1;
			if(primary==o.primary)
				if(secondary>o.secondary) //再比較次要的
					return +1;
				else if(secondary==o.secondary)
					return 0;
			return -1;
		}
		
		public String toString()
		{
			return Character.toString(primary)+secondary+": "+item;
		}
	}
	
	public void add(String td,char pri,int sec)
	{
		super.add(new ToDoItem(td, pri, sec));
	}
	
	public static void main(String[] args) {
		ToDoList to=new ToDoList();
		to.add("Empty Trash",'C',4);
		to.add("Feed dog",'A',2);
		to.add("Feed bird",'B',7);
		to.add("Mow lawn",'C',3);
		to.add("Water lawn",'A',1);
		to.add("Feed cat",'B',1);
		
		while(!to.isEmpty())
		{
			System.out.println(to.remove());
		}
	}
}
/**output:
A1: Water lawn
A2: Feed dog
B1: Feed cat
B7: Feed bird
C3: Mow lawn
C4: Empty Trash
 */
           
package org.rui.collection2.queues;

import java.util.LinkedList;

/**
 * 雙向隊列就是一個隊列,但是你可以在任何一端添加或移除元素,
 * LinkedList無法實作這樣的接口,但可以使用組合來建立一個Deque類,
 * @author lenovo
 *
 * @param <T>
 */

public class Deque<T>  {
	private LinkedList<T> deque=new LinkedList<T>();
	public void addFirst(T e){deque.addFirst(e);}
	public void addLast(T e){deque.addLast(e);}
	public T getFirst(T e){return deque.getFirst();}
	public T getLast(T e){return deque.getLast();}
	public T removeFirst(){return deque.removeFirst();}
	public T removeLast(){return deque.removeLast();}
	public int size(){return deque.size();}
	public String toString(){return deque.toString();}
	//and other methods as necessary............
	
	
	public static void fillTest(Deque<Integer> de)
	{
		for(int i=10;i<17;i++)
			de.addFirst(i);
		for(int i=50;i<55;i++)
			de.addLast(i);
	}
	public static void main(String[] args) {
		Deque<Integer> deque=new Deque<Integer>();
		fillTest(deque);
		System.out.println(deque);
		while(deque.size()!=0)
			System.out.print(deque.removeFirst()+"  ");
		System.out.println();
		fillTest(deque);
		while(deque.size()!=0)
			System.out.print(deque.removeLast()+"  ");
		System.out.println();
		
	}
	
}
/** output:
[16, 15, 14, 13, 12, 11, 10, 50, 51, 52, 53, 54]
16  15  14  13  12  11  10  50  51  52  53  54  
54  53  52  51  50  10  11  12  13  14  15  16 
*/