[大话数据结构-读书笔记] 队列

队列

1 队列的定义

像移动、联通、电信等客服电话，客服人员与客户相比总是少数，在所有的客服人员都占线的情况下，客户会被要求等待，直到有某个客服人员空下来，才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。客服系统就是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q= (a₁, a₂, ……, an)，那么a₁就是队头元素，而a_n是队尾元素。这样我们删除时，总是从a₁开始，而插入时，在队尾插入。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后，如下图所示。

队列在程序设计中用得非常频繁。前面我们已经举了一个例子，再比如用键盘进行各种字母或数字的输入，到显示器上如记事本软件上的输出，其实就是队列的典型应用，假如你本来和女友聊天，想表达你是我的上帝，输入的是god，而屏幕上却显示出了dog发了出去，这真是要气死人了。

2 队列的抽象数据类型

同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。

3 队列的顺序存储结构及实现

队列的顺序存储结构，简称为顺序队列。

由于篇幅原因，顺序队列的实现程序不在这里贴出，详细请看我的另一篇博客：数据结构 - 顺序队列的实行（C语言）。

4 队列的链式存储结构及实现

队列的链式存储结构，简称为链队列。

由于篇幅原因，顺序队列的实现程序不在这里贴出，详细请看我的另一篇博客：数据结构 - 顺序队列的实行（C语言）。

5 顺序队列与栈队列的区别

对于循环队列与链队列的比较，可以从两方面来考虑：

• 从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。
• 对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一
  个指针域，会产生一些空间上的开销，但也可以接受。 所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

[大话数据结构-读书笔记] 队列

原文：https://www.cnblogs.com/linuxAndMcu/p/10327849.html