队列
队列是一种特殊的现形镳,特殊之处在于它只允许在队列的前端(front)进行删除操作,而在队列的后端(rear)进行插入操作,和栈一样是一种操作受限制的线性表。进行插入操作的一端称为队尾,进行删除操作的一端称为对头。
队列这个概念非常好理解。可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。先进者先出,这就是典型的“队列”。
队列支持的最基本操作有两个:入队 enqueue(),放一个数据到队列尾部;出队 dequeue() ,从队列头部取一个元素。如下图:
队列的概念很好理解,基本操作也很容易掌握。作为一种非常基础的数据结构,队列的应用也非常广泛,特别是一些具有某些额外特性的队列,比如循环队列、阻塞队列、并发队列。
它们在很多偏底层系统、框架、中间件的开发中,起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存,都用到了循环并发队列;Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
顺序队列
队列和栈一样,都是一种抽象的数据结构。它具有先进先出的特性,支持在队尾插入元素,在对头删除元素。队列可以用数组来实现,也可以用链表来实现。用数组实现的队列叫做顺序队列,用链表实现的队列叫做链式队列。
顺序队列
顺序队列需要两个指针,一个是 head 指针,指向对队头;一个是 tail 指针,指向队尾。比如,当 a、b、c、d 依次入队后,队列中的 head 指针指向下标为 0 的位置,tail 指针指向下表为 4 的位置。
当我们调用两次出队操作之后,队列中 head 指针指向下标为 2 的位置,tail 指针仍然指向下标为 4 的位置。
这样的话就会出现一个问题,随着不停地进行入队、出队操作,head 和 tail 都会持续往后移动。当 tail 移动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了,因为 tail 指针大于数组长度,出现了“溢出”。
像这种不是因为存储空间不够而产生的溢出,称为假溢出。
实际上为了解决假溢出现象,通常都会使用循环队列。
循环队列
循环队列,就是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列,可以想成数组的头部和尾部连接在一起。原本数组是有头有尾的,是一条直线。现在我们把首尾相连,扳成了一个环。如下图:
在上图中,队列的大小为11,当前 head = 6,tail = 10。当有一个新的元素 e 入队时,把元素放入下标为 10 的位置。但这个时候,我们并不把 tail 更新为 11,而是将其在环中后移一位,到下标 0 的位置。当再有一个元素 e 入队时,我们将 e 放入下标 0 的位置,然后 tail 加 1 更新为 1。
在添加完 e 之后,又添加 f 元素之后,循环队列就变成了下面这个样子
对于循环队列,实现的代码难度要比非循环队列难多了,最关键的是:如何确定队列空和队列满的判定条件。
假设队列的大小是 n,那么在非循环队列中,队列满的判断条件是 taill == n,队列空的判断条件是 head == tail。那么针对循环队列,队列空和队列满的情况如下:
循环队列的队列空判断条件仍然是 head == tail。队列满的判断条件分为几种:
- 设置 length 字段,length == n 的话则队列满
- 少用一个存储空间,( tail + 1 ) % n == head 的方法来判断
这里采用第二种方案,先看下图:
上图中,head 在下标 6 的位置,tail 在下标 5 的位置,当 (tail + 1) % n == head
时,可以说明当前循环队列已经满了。
链式队列
基于链表的实现,我们同样需要两个指针:head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。如图所示,入队时,tail->next= new_node, tail = tail->next;出队时,head = head->next。
相对于顺序队列,链式队列就不需要担心数据搬移的问题。
阻塞队列
有一些聚友特殊特性的队列应用会应用的比较广泛,比如阻塞队列和并发队列。
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。
其实这种就是一种”生产者 - 消费者模型“,可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快,“消费者”来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到“消费者”消费了数据,“生产者”才会被唤醒继续“生产”。
而且不仅如此,基于阻塞队列,我们还可以通过协调“生产者”和“消费者”的个数,来提高数据的处理效率,如下图: