JDK学习之Queue

masterzs

浏览: 16923 次
性别:
来自: 北京

最近访客更多访客>>

zhangbohun

rEdMiddLe

nesuk

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

JDK学习

JDK J#UML IDEA

今天学习Queue，基本数据类型，特点先进先出(FIFO)。

1.JDK中接口的定义：

在jdk里边，LinkedList直接实现的Queue接口，所以我们可以使用LinkedList来模拟Queue，看一下几个

主要方法：

2，主要方法解析：

加入一条记录，offer(E o)

    public boolean offer(E o) {
        return add(o);
    }

可以看到内部默认调用LinkedList的add方法,也就是默认放到队尾，head的previous指向，

取出一条记录，

    public E poll() {
        if (size==0)
            return null;
        return removeFirst();
    }

调用LinkedList的removeFirst方法，再看这个方法的实现：

 public E removeFirst() {
	return remove(header.next);
    }

结果就是删除head.next指向的数据项，就是队列的第一个条数据，也是最早进入队列的数据。

下边我们看下JDK中的继承关系，其中有个PriorityQueue，优先队列，怎么个优先法呢，我们看看其增加和删除方法

看下其成员变量和构造函数：

    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    private transient Object[] queue;
    private int size = 0;
    private final Comparator<? super E> comparator;
    private transient int modCount = 0;

    public PriorityQueue(int initialCapacity, 
                         Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity + 1];
        this.comparator = comparator;
    }

从这里我们看到其内部是通过数组来实现存储，构造函数，默认初始化一个queue，下边我们通过添加一条数据来看看为什么称为优先级队列，

增加一条数据，

    public boolean offer(E o) {
        if (o == null)
            throw new NullPointerException();
        modCount++;
        ++size;

        // Grow backing store if necessary
        if (size >= queue.length) 
            grow(size);

        queue[size] = o;
        fixUp(size);
        return true;
    }

关键看fixUp这个函数，

    private void fixUp(int k) {
        if (comparator == null) {
            while (k > 1) {
                int j = k >> 1;
                if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        } else {
            while (k > 1) {
                int j = k >>> 1;
                if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        }
    }

首先判断是否有实现的comparator接口的函数，如果没有说明默认为实现Comparable接口，然后用折半查找进行排序，否则就是用实现了Comparator接口的类进行比较，现在我们

知道了如果使用PriorityQueue，其加入的类应该实现Comparable接口，或者提供一个Comparator比较器，默认String会安装首字母顺序排序。

从队列中删除一条记录，poll():

    public E poll() {
        if (size == 0)
            return null;
        modCount++;

        E result = (E) queue[1];
        queue[1] = queue[size];
        queue[size--] = null;  // Drop extra ref to prevent memory leak
        if (size > 1)
            fixDown(1);

        return result;
    }

关键方法fixDown,看一下其实现：

    private void fixDown(int k) {
        int j;
        if (comparator == null) {
            while ((j = k << 1) <= size && (j > 0)) {
                if (j<size && 
                    ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
                    j++; // j indexes smallest kid

                if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        } else {
            while ((j = k << 1) <= size && (j > 0)) {
                if (j<size && 
                    comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
                    j++; // j indexes smallest kid
                if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        }
    }

跟添加逻辑是相似的，需要对现有数据进行重新排序。

3 典型案例

我们通过一个例子来看看PriorityQueue的应用：

Person类：

public class Person implements Comparable{
	

	private String name;
	private String age; 
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public String getAge() {
		return age;
	}
	public void setAge(String age) {
		this.age = age;
	}
	public int compareTo(Object o) {
		
		return this.age.compareTo(((Person)o).getAge());
	}
	
	

}

主调用类：

public class QueueTest {

	public static void main(String[] args) {

		Queue<Person> queue = new PriorityQueue<Person>();
		 Person p = new Person();
		 p.setAge("23");
		 Person p1 = new Person();
		 p1.setAge("34");
		 Person p2 = new Person();
		 p2.setAge("12");
		 
		 Person p3 = new Person();
		 p3.setAge("12");
		 Person p4 = new Person();
		 p4.setAge("83");
		 
		 queue.offer(p);
		 queue.offer(p1);
		 queue.offer(p2);
		 queue.offer(p3);
		 queue.offer(p4);
		 
		 while(!queue.isEmpty()){
			 
			 System.out.print(queue.poll().getAge()+" ");
			
		 }
			}

}

打印结果：