小肥柴慢慢手写数据结构（C篇）（4-3 关于栈和队列的讨论）

目录

（本帖主要从形态上讨论线性表的一些共有特性，不涉及具体的编码环节）

1 双端栈/队列

（1）一般形态的讨论：经过大量编程训练后，不禁会有疑问：

【Q】为何ArrayList，LinkedList，Stack、Queue这四种基本形态以及它们的变种被统称为“线性表”呢？涉及到“双端”话题时，又应该如何正确理解呢？

【A】很多文献中总是给出大量的理论化论述，但是我认为可以简单的归纳如下：

（1）一个线性表两头都能进出。（注意红色箭头代表的数据进出方向。）

（2）可灵活设定元素增长方向：两头向中间 or 中间向两头；当然，都要处理越界/碰头问题。

（3）人们也习惯将带回绕的线性表当做一个环来看待。（老生常谈的话题，后续看案例。）

此时，在翻看双向链表的示意图，是不是更有味道了？

2 栈与队列的相互转化

这是一对经典的面试问题，在Leecode上有对应练习，大家可以试试看。

2-1 栈转化成队列

【Q】给定两个栈，你能否组装成一个队列？

【A】设置一个栈作入队用，另一个栈作出队用：

（1）入队直接压到输入栈。

（2）出队时：

<1> 若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈。

<2> 此时输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

<3> 若输出栈不为空，直接弹出即可。

2-2 队列转化成栈

【Q】给你两个队列，你能否组装成一个栈？

【A1】常规解法

（1）queue1用于存储栈内的元素，queue2作为入栈操作的辅助队列。

（2）入栈操作时，首先将元素入队到queue2，然后将queue1的全部元素依次出队并入队到queue2，此时queue2的前端的元素即为新入栈的元素，再将queue1和queue2互换，则queue1的元素即为栈内的元素，queue1的前端和后端分别对应栈顶和栈底。

（3）由于每次入栈操作都确保queue1的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除queue1的前端元素并返回即可，获得栈顶元素操作只需要获得queue1的前端元素并返回即可（不移除元素）。

（4）由于queue1用于存储栈内的元素，判断栈是否为空时，只需要判断queue1是否为空即可。

【A2】实际上，使用一个队列亦可：循环排队。

3 经典工程案例

3-1 生产者和消费者模型（再次重温环形缓冲区）

（1）数据消费者从队列中读取新的数据。

（2）数据生产者从队列中写入新的数据。

（3）只要读写操作速度协调，必然可以一直复用这段缓存。（溢写，spill机制）

【注】实际上把这个ring撇直了也没有那么神秘，不是吗？

3-2 MapReduce中的缓冲区对<k,v>键值对排序

【Q1】设想现在给你一个Byte数组（线性数据结构）如何把<k1，v1> ~ <kn，vn>n个键值对数据存入其中？

【Q2】此时若直接排序会导致频繁的内存腾挪（联想动态数组时我们实现的resize操作？），如何避免？

【A】在实际工程设计中，将数据转化为两部分的组合：

（1） 固定长度的<k，v>键值对。

（2）非固定长度meta元数据段。

（3）<k，v>键值对还存储了meta的起始位置。

为了提高buffer的利用率，考虑使用环形buffer，那么：

（1）index = 0处就相当于一条分割线，称为赤道（equator）。

（2）<k，v>和meta都以equator为起点，分别朝两个方向存放数据。

盗一张图，更加形象的表达

【效果】

（1）排序时仅需要调整<k,v>的顺序即可，极大减少内存腾挪。

（2）排序完成后，外部读取数据时，采用间接寻址能够以正确的顺序获取到完整的数据集合。

4 小结

本节着墨不多，但我认为只要图画的清楚，看图就能彻底领悟线性表的精髓：任意进出元素的巧用！当然，如果后续补全了树状数组话题的讨论（包括堆和树，特别是N叉树的代表B/B+树），整个知识体系正常看就完备了。