Go语言视频零基础入门到精通

javalearner

今天学习Queue，基本数据类型，特点先进先出(FIFO)。 1.JDK中接口的定义：

          在jdk里边，LinkedList直接实现的Queue接口，所以我们可以使用LinkedList来模拟Queue，看一下几个     主要方法： 2，主要方法解析：     加入一条记录，offer(E o)     public boolean offer(E o) {
        return add(o);
    }[/code]          可以看到内部默认调用LinkedList的add方法,也就是默认放到队尾，head的previous指向，     取出一条记录，     public E poll() {
        if (size==0)
            return null;
        return removeFirst();
    }[/code]     调用LinkedList的removeFirst方法，再看这个方法的实现：  public E removeFirst() {
        return remove(header.next);
    }[/code]     结果就是删除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;
    }[/code]           从这里我们看到其内部是通过数组来实现存储，构造函数，默认初始化一个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;
    }[/code]     关键看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;
            }
        }
    }[/code]  首先判断是否有实现的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;
    }[/code] 关键方法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;
            }
        }
    }[/code]  跟添加逻辑是相似的，需要对现有数据进行重新排序。 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());
        }
       
       
}[/code] 主调用类： 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()+" ");
                       
                 }
                        }
}
                        [/code]  打印结果： 12 12 23 34 83 [/code] 4 总结 本人在实际项目中从未使用过Queue，但是其思想可以为我们所用，优先级队列在插入和删除的时候，需要重新排序，会有一定的性能损失。大家有没有在实际项目中应用Queue， 有的话，可以留言进行讨论，谢谢。