什么是队列
队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。
队列有两种:
- 单队列
- 循环队列
单队列就是常见的队列, 每次添加元素时,都是添加到队尾:
以数组实现的队列为例,初始时队列长度固定为 4,font 和 rear 均为 0:
每添加一个元素,rear 后移一位。当添加四个元素后, rear 到了索引为 4 的位置:
这时 a1,a2 出队,front 后移动到 2:
这时想要再添加两个元素,但 rear 后移两位后就会越界:
明明有三个空位,却只能再放入一个!这就是单队列的“假溢出”情况。
(上述参考借鉴自 http://www.nowamagic.net/librarys/veda/detail/2350)
针对这种情况,解决办法就是后面满了,就再从头开始,也就是头尾相接的循环。这就是 “循环队列” 的概念。
循环队列:
循环队列中,
rear = (rear - size) % size
接着上面的例子,当 rear 大于 队列长度时,rear = ( 5 - 5) % 5 = 0 :
这样继续添加时,还可以添加几个元素:
那如何判断队列是否装满元素了呢,单使用 front == rear 无法判断究竟是空的还是满了。
两种方法:
- 加个标志 flag ,初始为 false,添加满了置为 true;
- 不以 front = rear 为放满标志,改为 (rear - front) % size = 1。
法 2 的公式放满元素时空余了一个位置,这个公式是什么意思呢?
接着上面的情况,当 rear 从后面添加元素跑到前面 0 时,再添加一个元素 a6,rear 后移一位到 1,这时 front = 2, (1 - 2) % 5 = 1, 满足放满条件。
因此,当 rear > font 时,队列中元素个数 = rear - font;
当 rear < font 时,队列中元素分为两部分: size - font 和 rear ,也就是 rear + size - font。以上述图片为例,队列中元素个数 = 1 + 5 - 2 = 4.
接着我们介绍 Java 集合框架中的队列 Queue
Java 集合中的 Queue 继承自 Collection 接口 ,Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。
Queue 用来存放 等待处理元素 的集合,这种场景一般用于缓冲、并发访问。
除了继承 Collection 接口的一些方法,Queue 还添加了额外的 添加、删除、查询操作。
添加、删除、查询这些个操作都提供了两种形式,其中一种在操作失败时直接抛出异常,而另一种则返回一个特殊的值:
Queue 方法介绍:
1.add(E), offer(E) 在尾部添加:
- 1
- 2
- 3
- 4
他们的共同之处是建议实现类禁止添加 null 元素,否则会报空指针 NullPointerException;
不同之处在于 add() 方法在添加失败(比如队列已满)时会报 一些运行时错误 错;而 offer() 方法即使在添加失败时也不会奔溃,只会返回 false。
2016.11.21 添加
注意
Queue 是个接口,它提供的 add, offer 方法初衷是希望子类能够禁止添加元素为 null,这样可以避免在查询时返回 null 究竟是正确还是错误。
事实上大多数 Queue 的实现类的确响应了 Queue 接口的规定,比如 ArrayBlockingQueue,PriorityBlockingQueue 等等。
但还是有一些实现类没有这样要求,比如 LinkedList。
感谢 sumsear 指出。
2.remove(), poll() 删除并返回头部:
- 1
- 2
- 3
- 4
当队列为空时 remove() 方法会报 NoSuchElementException 错; 而 poll() 不会奔溃,只会返回 null。
3.element(), peek() 获取但不删除:
- 1
- 2
- 3
- 4