云课堂算法笔记之栈和队列

一：getMin

考点：新加的getMin方法是单位时间O（1），所以不能用遍历O（n）

基本方法：用两个栈来实现一个是Data栈（原始栈），一个是Help栈（辅助栈）

方法一：

Help栈的压入策略：当push的数据小于栈顶元素时，压入栈中，当push的数据大于栈顶元素时，继续将栈顶元素压入栈中，同步压，弹出也同步弹出，使Help栈中栈顶元素每个时刻都是当前栈中的最小值

代码如下：

方法二：

Help栈的压入策略:当push的数据小于等于栈顶元素时，压入栈中

弹出策略：如果两个栈的栈顶元素相等，同步弹出，大于只弹出Data栈顶（不可能出现小于的情况）

二：两个栈组成的队列

思路：如图

但是这里有一个坑：

如果我们从Data栈倒入Help栈的过程后，这时用push了一个新的元素，那么就会出现问题

所以要注意以下亮点：

①倒之前保证Help必须是空的

②Data倒数据一定要一次性倒完

代码如下：

三：两个队列实现栈

思想：先将Base除最后一位全部放入Help队列中，将Base中最后一位再返回，这时再将Help队列中的数再移回Base队列中

代码如下：

四：仅用递归函数和栈操作逆序一个栈

先思考另一个问题：

如何做一个函数功能是：返回栈底元素，同时把它从栈中删除

正常的想法，肯定是需要一个辅助空间，但是我们虽然不能主动申请空间，但是可以让系统帮助我们

先看代码：

结合代码看思想：弹出栈顶元素，如果这时栈为空，那么刚刚弹出的就是栈底元素，否则进入到递归的过程，依次进行，直到弹出栈底元素（此时栈已经为空），这时将栈底元素返回给上一层循环，现在last储存的就是栈底元素，然后将本层的元素压入栈中（最开始入栈的是倒数第二层元素），这时再将last返回给上一层，说白了，也就是将栈底元素不断向上层传递，将其他层从下到上依次压入栈的过程

 为什么能够实现？

递归是一个压栈的过程，系统把每一层的状态都记录下来，当子过程递归完用到这一层的时候，这些数就得到了

回归到第四题，我们把上面的过程看做函数f（）

其实也是一个递归过程，依次用f函数取出3、2、1，当取出1时，直接压入栈中，再向上一层传递，再压入栈中，依次下去，就完成了栈的逆置。