CC150-Stack and Queue

3.2 请设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。push、 pop和min三个方法的时间复杂度必须为O(1)。（第 50 页）

LeetCode 155
Two Stack 
One Stack

3.3 设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度 时， 我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应 该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和 SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一 个栈时的情况一样）。 进阶 实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。（第 51 页）

这个实现起来有点棘手，不过，我们可以设想一个“推入”动作。从栈1弹出元素时，我们 需要移出栈2的栈底元素，并将其推到栈1中。随后，将栈3的栈底元素推入栈2，将栈4的栈底元 素推入栈3，等等。

你可能会指出，何必执行“推入”操作，有些栈不填满不是也挺好的。而且，这还会改善时 间复杂度（元素很多时尤其明显），但是，若之后有人假定所有的栈（最后一个栈除外）都是填 满的，就可能会让我们陷入棘手的境地。这个问题并没有“标准答案”，你应该跟面试官讨论各 种做法的优劣。

popAt(int index)
leftShif()
pop()
removeBottom()

3.5 实现一个MyQueue类，该类用两个栈来实现一个队列。（第 51 页）

LeetCode 232

每当执行peek()和pop()操作时，就要将s1的所有元素弹出，压入s2中， 然后执行peek/pop操作

3.6 编写程序，按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的 栈存放临时数据，但不得将元素复制到别的数据结构中（如数组）。该栈支持如下操作：push、 pop、peek和isEmpty。（第 51 页）

一种做法是实现初步的排序算法。搜索整个栈，找出最小元素，之后将其压入另一个栈。然 后，在剩余元素中找出最小的，并将其入栈。这种做法实际上需要三个栈：s1为原先的栈，s2 为最终排好序的栈，s3在搜索s1时用作缓冲区。要在s1中搜索最小值，我们需要弹出s1的元素， 将它们压入缓冲区s3。 可惜，我们只能使用一个额外的栈。有没有更好的做法？有。

s1 unsorted

s2 sorted

tmp - store top of s1

pop s2 to s1 until peek() <= tmp

repeat sort

这个算法的时间复杂度为O(N 2 )，空间复杂度为O(N)。 如果允许使用的栈数量不限，我们可以实现修改版的quicksort或mergesort。

对于mergesort解法，我们可以再创建两个栈，并将这个栈分为两部分。我们会递归排序每个 栈，然后将它们归并到一起并排好序，放回原来的栈中。注意，该解法要求每层递归都创建两个 额外的栈。

对于quicksort解法，我们会创建两个额外的栈，并根据基准元素（pivot element）将这个栈 分为两个栈。这两个栈会进行递归排序，然后归并在一起，放回原来的栈中。与上一个解法一样， 每层递归都会创建两个额外的栈。