容器深入研究--队列

Leefs 2020-01-16 AM 2052℃ 0条

# 容器深入研究--队列

### 前言

本篇讲述《Java编程思想》第17.7小节，队列

### 概述

除了并发应用中，Queue在java中仅有两个实现是LinkedList和PriorityQueue，它们的差异在于排序行为而不是性能。

**示例**

```java
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++){
            queue.offer(gen.next());//向队列中添加一个元素  容量满时返回false
        }
        while(queue.peek() != null){//返回队列的头元素，不删除
            System.out.print(queue.remove()+" ");
        }
        System.out.println();
    }
    static class Gen implements Generator<String>{
        String[] s = ("one two three four five six seven eight nine ten").split(" ");
        int i;
        @Override
        public String next() {
            return s[i++];//先返回s[i],再i++，这样当i到9的时候，return s[9],然后i=10,test方法中的for条件判断不满足，退出
            // 如果++i的话，i=8的时候，return  s[9],for条件中i=9,满足，再到next方法中，先i+1变为10，这时return s[10]已经越界，报错
        }
    }

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());
        //PriorityBlockingQueue:提供了可阻塞读取功能的优先级队列，当队列中没有元素的时候，会阻塞读取者，这种队列不需要额外的同步操作
        test(new PriorityBlockingQueue<String>(),new Gen());
    }
}
```

> 运行结果

```java
one two three four five six seven eight nine ten 
eight five four nine one seven six ten three two 
one two three four five six seven eight nine ten 
one two three four five six seven eight nine ten 
one two three four five six seven eight nine ten 
eight five four nine one seven six ten three two 
```

> 使用队列中的方法说明

+ 1.`ArrayBlockingQueue`：是一个阻塞式的队列，继承自`AbstractBlockingQueue`,间接的实现了Queue接口和Collection接口。底层以数组的形式保存数据(实际上可看作一个循环数组)。常用的操作包括 add，offer，put，remove，poll，take，peek。（基于数组的阻塞队列）
  + 1.1.先进先出队列（队列头的是最先进队的元素；队列尾的是最后进队的元素）
  + 1.2.有界队列（即初始化时指定的容量，就是队列最大的容量，不会出现扩容，容量满，则阻塞进队操作；容量空，则阻塞出队操作）
  + 队列不支持空元素

+ 2.`ConcurrentLinkedQueue`：一个基于链接节点的无界线程安全队列。此队列按照 FIFO（先进先出）原则对元素进行排序。
+ 3.`LinkedBlockingQueue`：是基于链表的、有界的、遵循FIFO原则的阻塞队列，队列默认的最大长度为`Integer.MAX_VALUE`
+ 4.`priorityBlockingQueue`：是一个无界队列，它没有限制，在内存允许的情况下可以无限添加元素；它又是具有优先级的队列，是通过构造函数传入的对象来判断，传入的对象必须实现comparable接口。

**总结**

上述程序中，除了优先级队列，Queue将精确地按照元素被置于Queue中的顺序产生它们。

### 优先级队列

**代码示例**

```java
public class ToDoList extends PriorityQueue<ToDoList.ToDoItem> {
    public class ToDoItem implements Comparable<ToDoItem>{
        private char primary;
        private int secondary;
        private String item;
        public ToDoItem(String td,char pri,int sec){
            primary=pri;
            secondary=sec;
            item = td;
        }
        @Override
        public int compareTo(ToDoItem arg) {
            if(primary>arg.primary)
                return +1;
            if(secondary == 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 td,char pri,int sec){
        super.add(new ToDoItem(td,pri,sec));
    }

public static void main(String[] args) {
        ToDoList toDoList = new ToDoList();
        toDoList.add("Empty trash",'C',4);
        toDoList.add("Feed dog",'A',2);
        toDoList.add("Feed bird",'B',7);
        toDoList.add("Mow lawn",'C',3);
        toDoList.add("Water lawn",'A',1);
        toDoList.add("Feed cat",'B',1);
        while (!toDoList.isEmpty()){
            System.out.println(toDoList.remove());
        }
    }
}
```

> 运行结果

```
A1:Water lawn
A2:Feed dog
B7:Feed bird
B1:Feed cat
C4:Empty trash
C3:Mow lawn
```

> 参数说明

`PriorityQueue`：列表中的每个对象都包含一个字符串和一个主要的以及次要的优先级值，该列表的排序顺序也是通过实现Comparable而进行控制的。

从上面程序你可以看到各个项的排序是如何因为使用了优先级队列而得以自动发生的。

### 双向队列

双向队列就像一个队列，但是可以在任意一段添加或移除元素。在LinkedList中包含支持双向队列的方法，但在Java标准类库中没有任何显式的用于双向队列的接口。因此，LinkedList无法去实现这样的接口，无法像前面转型到Queue那样向上转型为Deque。但是可以使用组合创建一个Deque类，并直接从LinkedList中暴露相关方法：

> `queue.addFirst()`：向队列首部添加元素
> `queue.addList()`： 向队列尾部添加元素
> `queue.getLast()`：获取队列尾部元素
> `queue.getFirst()`：获取队列首部元素
> `queue.removeFirst()`：移除队列首部元素
> `queue.removeLast()`：移除队列尾元素
> `queue.size()`：返回队列大小

标签: Java编程思想, 容器深入研究, 队列

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/434.html

上一篇【转载】MyBatis一次性插入多条数据

下一篇容器深入研究--理解Map

容器深入研究--队列

评论已关闭

栏目分类

标签云

友情链接申请

容器深入研究--队列

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请