数据结构和算法-4.2-队列

本来想栈和队列写为一篇的，而且也确实这么写了，然而写完还是决定拆分开来比较好，简洁，易读；

队列

第一个插入的数据会被最先移除，进行插入操作的端称为队尾，进行删除操作的端称为队头；例如显示中人们排队办理业务，水管中的水流；

FIFO：first in first out, 先进先出；

队列的实现

1. 先创建一个队列的基类

2. 用数组实现队列

3. 对上面队列的使用

- 循环队列：

注意上面代码中的insert和remove中的if语句，当队首队尾指针达到最值是，将他们设为初始值，这就是循环队列（也称缓冲环），然而如果像上面那样，使用时用isFull和isEmpty进行判断，就可以当作普通队列使用了；

- 双端队列：

1. 队列的每一端都可以插入和删除数据，其元素的逻辑结构仍是线性结构；可以使用双端链表实现，这个在后面介绍链表时会给具体的实现代码，它主要用到四个方法insertLeft(), removeLeft(), insertRight(), removeRight()；

2. 如果禁止insertLeft(),removeLeft()（或right）双端队列的功能就和栈一样了；

3. 如果禁止removeLeft(),insertRight()（或另两个）双端队列的功能就和队列一样了

- 先级队列：

如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了 优先级队列 这种数据结构。

下面是用数组实现优先级队列的代码，也可以用后面会学到的堆来实现

优先级队列的使用：

我是今阳，如果想要进阶和了解更多的干货，欢迎关注公众号”今阳说“接收我的最新文章