栈和队列的设计和递归

栈和队列是逻辑的名字，而链表、数组是底层的实现方式。

• 单向链表。每一个结点（结构体）需要一个值（value）和一个下个元素的地址（next）。

• 双向链表。每一个结点需要一个值、前一个元素的地址（last）和后一个元素的地址。

• 队列，FIFO。需要有 Head、Tail 两个属性，及 Push、Pop 两个方法。

• 栈，LIFO。需要有 Bottom、Top 两个属性，及 Push、Pop 两个方法。

双向链表实现队列和栈

• Head <-> x <-> x <-> x <-> Tail
• Bottom -> x -> x -> Top

双向链表即可实现队列，也可实现栈，它们的不同只是方法上的不同。

在队列中，是 AddFromHead，PopFromTail；而在栈中，是PushFromTop，PopFromTop。

数组实现栈和队列

一般的实现是固定大小的栈和队列（数组是固定大小的）。

数组实现栈

栈很好实现，用一个下标 index 来标记栈顶，下标 0 表示栈底。插入和弹出只需维护 index 的变化即可。

数组实现队列

用数组实现队列。需要记录 Head、Tail

方法一：两个下标标记头和尾

是用两个下标 headIndex 和 tailIndex 来标记 Head 和 Tail。这样在插入和弹出时，维护两个 index 的变化，但这样的实现很不方便，因为 tailIndex 一直在追赶 headIndex，如何区分空队列和满队列是一个问题。

方法二：用 head 和 size 标记头和尾

可以说数组的长度是一个 limit，只要 size 到了 limit 就表示队列已满。下标独立维护，Head + Size( - limit) 就是 Tail 的下标。这样 Push 和 Pop 也就方便多了。

栈和队列常见面试题

特殊的栈，可以用 getMin 获取栈的最小值

实现：用两个栈，Data 栈是一个基本的、正常的栈；Min 栈，与 Data 栈（单向）同步操作，只记录当前栈中最小值。

由于 Min 栈记录的是 Data 栈对应位置的最小 值，所以只需在 Data 栈插入的时候，用 Min 栈栈顶和插入值比较，对应得插入小值则可。在 Data 栈 Pop 出时，为保持同步，Min 栈也 Pop。

上述是用了一个 Min 栈同步于 Data 栈实现的。也可以设计成 Min 栈高度小于等于 Data 栈高度的设计方法，但需要用逻辑在弹出是做判断。（略）

用栈实现队列

实现方法：两个栈，插入时是 Push 栈，弹出时从 Push 栈移到 Pop 栈，此时的 Pop 栈的栈顶就是队列的 Head，但若插入时又需要将 Pop 栈的数据全移到 Push 栈后才能插入。

用队列实现栈

实现方法：两个队列，A 队列和 B 队列，插入数据在 A 队列，弹出时将 A 队列串除了最后一个元素外的其他元素转移到 B 队列中，此时 A 队列只有最后一个元素，弹出它即为栈式的取数据。此时 B 队列可以继续使用，每一次取数据时，进行队列转换。

递归

递归是用了系统栈的性质，具体细节不做讲述了，假设读者都有基础。

任何递归都是可以变成迭代的。递归是用了栈的结构，将方法及一些参数依次压入栈，先得出栈顶的结果再依次向下最终得出栈底的结果。迭代是顺序式的，就像 for 循环一样，依次算出结果。

有些语言提供了尾递归，其实就是语言自己将递归优化成了迭代这种方式。

一般递归的时间复杂度公式：

递归时间复杂度公式

其中，a 为递归函数调了多少次；b 为每个问题分为子问题的个数；d 为单纯的递归之外进行操作的循环次数（无其他 for 时取 0，有一次 for 遍历取 1）。

时间复杂度取值

总结

栈和队列可以实现转换，但需要有两个栈实现队列，两个队列实现栈。

---

附：查询图的宽度是用队列来做的，图的深度是用栈结构来做的。