队列的实现一般有两种:顺序队列 和 循环队列,我们上面的事例使用的是顺序队列,那么下面我们看一下循环队列的实现方式
环形缓冲区
循环队列一般是以环状缓冲区(ring buffer)的方式实现的,它是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构,适合缓存数据流。假如我们要用 6 个元素的数组来实现一个环形缓冲区,这时可以从起始位置开始有序的存储数据,然后再按照存储时的顺序把数据读出。在数组的末尾写入数据后,后一个数据就会从缓冲区的头开始写。这样,数组的末尾和开头就连接了起来。
链表
下面我们来介绍一下链表和 二叉树,它们都是可以不用考虑索引的顺序就可以对元素进行读写的方式。通过使用链表,可以高效的对数据元素进行添加 和 删除操作。而通过使用二叉树,则可以更高效的对数据进行检索。
在实现数组的基础上,除了数据的值之外,通过为其附带上下一个元素的索引,即可实现链表。数据的值和下一个元素的地址(索引)就构成了一个链表元素,如下所示
对链表的添加和删除都是非常高效的,我们来叙述一下这个添加和删除的过程,假如我们要删除地址为 p[2] 的元素,链表该如何变化呢?
我们可以看到,删除地址为 p[2] 的元素后,直接将链表剔除,并把 p[2] 前一个位置的元素 p[1] 的指针域指向 p[2] 下一个链表元素的数据区即可。