更好的使用Java集合(三)

原创
2016/03/14 20:52
阅读数 132

队列、双端队列和优先级队列

    队列可以有效地在尾部添加一个元素,在头部删除一个元素。有两个端头的队列叫双端队列。

    可以有效地在头部和尾部添加或删除元素,但不支持在队列中间添加元素。JavaSE6中引入了Deque接口,并由ArrayDeque和LinkedList类实现。

add(E element);offer(E element);

addFirst(E element);offerFirst(E element);

addLast(E element);offerLast(E element);

将给定元素添加到双端队列的头部或尾部。如果队列满了,add*(E element)方法将抛出IllegalStateException异常,而offer*(E element)方法返回false。

remove();poll();

removeFirst();pollFirst();

removeLast();pollLast();
如果队列不为空,删除并返回队列头部或尾部的元素。如果队列为空,remove*()方法将抛出NoSuchElementException异常,而poll*()方法返回null。

element();peek();

getFirst();peekFirst();

getLast();peekLast();
如果队列不为空,返回队列头部或尾部的元素。如果队列为空,element()方法和get*()方法将抛出NoSuchElementException异常,而peek*()方法返回null。

    优 先级队列(priority queue)中的元素可以按照任意的顺序插入,但却总是按照排序的顺序进行检索。无论何时调用remove方法,总会获得当前优先级队列中最小的元素。优 先级队列并没有对所有的元素进行排序,而是使用了堆(heap)。堆是一个可以自我调整的二叉树,可以让最小的元素移动到根,而不必花费时间对元素进行排 序。

    public class Task {
        public Task() {
        }

        public Task(String name, int priority) {
            super();
            this.name = name;
            this.priority = priority;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getPriority() {
            return priority;
        }

        public void setPriority(int priority) {
            this.priority = priority;
        }

        private String name;
        private int priority;
    }

    @Test
    public void PriorityQueueTest() {
        PriorityQueue<Task> pq = new PriorityQueue<Task>(
                new Comparator<Task>() {
                    public int compare(Task t1, Task t2) {
                        return t1.getPriority() - t2.getPriority();
                    }
                });

        pq.add(new Task("task1", 20));
        pq.add(new Task("task2", 10));
        pq.add(new Task("task3", 30));

        for (Task t : pq)
            System.out.println(t.getName() + "," + t.getPriority());
    }

    结果返回了task2,10;task1,20;task3,30。通过Task的priority属性进行了排序。

    

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
2 收藏
1
分享
返回顶部
顶部