Stack ADT
-
栈(stack)是受限的序列
- 只能在栈顶(top)插入和删除
- 栈底(bottom)为盲端
-
基本接口
size()
/ empty()
push()
入栈
pop()
出栈
top()
查顶
-
后进先出(LIFO)
扩展接口 :getMax()
使用一个辅助栈来跟踪最大元素:
- 维护两个栈,一个是主栈用于正常的 push 和 pop 操作,另一个是辅助栈用于跟踪最大元素。
- 当往主栈中压入一个元素时,首先检查辅助栈是否为空。如果为空,就将这个元素同时压入辅助栈。
- 如果辅助栈不为空,就比较要压入主栈的元素与辅助栈栈顶元素的大小。如果新元素大于等于栈顶元素,就将新元素压入辅助栈。否则,不将新元素压入辅助栈,保持辅助栈栈顶元素不变。
- 当你主栈中弹出元素时,同时也从辅助栈中弹出元素。这样,辅助栈始终反映了主栈中的最大元素。
- 如果你需要查找栈中的最大元素,只需查看辅助栈的栈顶元素,它将是当前主栈中的最大元素。
使用 steap 结构实现
Steap
函数调用栈
原理
深度与空间
递归法求阶乘
递归求 fib 序列
空间复杂度
递归算法所需的空间,主要取决于递归深度,而非递归实例总数:
消除递归
递归函数的空间复杂度
为隐式地维护调用栈,需花费额外的时间、空间——为节省空间,可
尾递归
定义
- 尾递归指递归调用在函数体最后一步的递归调用。
- 递归求 factorial 的最后一步是乘法与函数的自我调用。
特点
尾递归是最简单的递归模式:一旦抵达递归基,便会引发一连串的 return(且返回地址相同),调用栈相应地连续 pop。
故不难改写为迭代形式,越来越多的编译器可以自动识别并代为改写
消除尾递归
进制转换
数制转换原理
λ 进制的数可以表示为:
n=(dm...d2d1d0)λ=dm⋅λm+...+d2⋅λ2+d1⋅λ1+d0⋅λ0
则令:ni=(dm...di+2di+1di)λ
有:ni+1=ni/λ 和 di=ni%λ
如此对 λ 反复整除、取余,即可自低而高得出 λ 进制的各位。
实现
原数的位数并不确定,因此不适合使用向量存储原数,并且浪费严重:
- 若使用向量,则扩容策略必须得当;
- 若使用列表,则多数接口均被闲置。
另外,运算的顺序与输出顺序相反——数位从低到高运算获得,但是输出却由高到低。这种相反的顺序非常符合栈的思想:
括号匹配
思路尝试
- 核心思想:在括号串内部,消去一对紧邻的括号,不会影响全局的匹配判断。
实现:一种括号
扩展:多类括号
- 推广时要做括号类型的判断,直接根据左右是不能实现的;
栈混洗
问题描述
对栈 A=<a1, a2, a3,.., an]
,另有空栈 S 作中转、B 作转存处。A 只能弹出元素,B 只能压入元素,S 可以压入或弹出。经过一系列操作后,A 中所有元素转入 B 中,则 B 的当前从栈底到栈顶的序列称为对 A 的一次栈混洗:
栈混洗总数
同一输入序列有多种栈混洗,那么对长度为 n 的序列,栈混洗总数记作 SP(n)
显然,SP(1)=1
。考察当 S 变空时,即 A 的栈顶元素从 S 中弹出时,显然有 n 种情况:
SP(n)=k=1∑nSP(k−1)⋅SP(n−k)=catalan(n)=(n+1)!⋅n!(2n)!
catalan 数应用⭐
- 栈混洗:catalan (n)
- 括号匹配 n 对:catalan (n)
- 二叉树形态 n 节点:catalan (n)
- 互异 BST 的数量 n 节点:catalan (n)
- n 个叶节点的真二叉树数量:catalan (n-1)
- n 个叶节点的真二叉树,其中有内部节点 n-1个,故相当于 n-1个互异节点的 BST 的数量:
Catalan(n-1)
禁形及其判断
若要判断输入序列的任一排列是否为栈混洗,则本质是判断相对次序是否符合栈的运算规律。
可以观察到并推广——任意三个元素能否按某相对次序出现于混洗中,与其它元素无关,即:对任何 1<=i<j<k<=n
, [..., k,..., i,..., j,...>
一定不是栈混洗,这就是一个禁形。
- O(n3) 算法:逐个判断;
- O(n2) 算法:只需考虑 i<j 情况下,是否有
[...,j+1,...,i,...,j,...
- O(n) 算法:借助栈直接模拟栈混洗的过程,每次 pop 栈 S 时检查是否已空,或需弹出的元素在栈 S 中却不是栈顶,则必为禁形。
栈混洗与括号匹配
每一栈混洗,都对应于栈 S 的 n 次 push 和 pop 操作的一组序列,由括号匹配中的推广,push 和 pop 就是一对括号操作。因此 n 个元素的栈混洗,等价于 n 对括号的匹配:
中缀表达式求值
问题描述
中缀表达式:就是运算符在两个操作数中间的计算式,如 1+1=2
自然地,中缀表达式求值的规则是基于优先级的局部计算,然后逐渐减治到全局——运算符逐渐减少,局部运算代以数值,最终得到结果。
设表达式 S=SL+S0+SR,对 S0 可以优先计算(优先级局部最高)且 val(S0)=v0,则可以递推得化简式:val(S)=val(SL+str(v0)+SR
思路
由于运算符优先级多样,并且还有括号可以改变局部运算的优先级——仅根据表达式的前缀,不足以确定各运算符的计算次序,只有获得足够的后续信息才能确定哪些运算符可以执行。
很自然地,这种读取顺序和运算顺序相反的情况,也适合用栈。栈在这里的作用,是缓冲了运算的及时需求:
- 自左向右扫描表达式,用栈记录已扫描的部分以及中间结果;
- 栈内最后所剩值(若非值,亦可判断表达式非法),就是表达式的正确结果。
算法实现
实例
逆波兰表达式
定义
逆波兰表达式——后缀表达式:运算符在操作数之后,且不需要括号就可以表示优先级运算关系。
栈式求值
对后缀表达式:0! 123 + 4 5 6 ! * 7 ! 8 / + * 9 / +
计算方式如下:
- 引入栈 S 存放操作数:
- 逐个处理后缀表达式中下一元素 x,
- 若 x 是操作数,则压入栈 S,
- 否则弹出运算符 x 所需要的目的操作数,执行计算后再压入栈中
- 最后返回栈顶。
中缀表达式转后缀表达式
手动
- 每遇到一个运算符,
- 若是一元运算符则与前面紧邻的操作数括起来,
- 若是二元运算符且后面的操作数满足与前面操作数的运行需求,则括起来;
- 最后将运算符移到最近的右括号之外;
- 脱去括号即可。
0!+123+4∗(5∗6!+7!/8)/9=((0!)+123)+4∗((5∗(6!))+((7!)/8))/9=((0!)+123)+((4∗((5∗(6!))+((7!)/8)))/9)=(((0!)+123)+((4∗((5∗(6!))+((7!)/8)))/9))=(((0)!123)+((4((5(6)!)∗((7)!8)/)+)∗9)/)+=0!123+4 5 6 !∗7!8/+∗9/+
自动
Queue ADT
特点
队列(queue)也是受限的序列:
- 只能在队尾插入(查询):
- 只能在队头删除(查询):
- 先进先出(FIFO)、后进后出(LILO)
扩展接口 :getMax()
使用 queap 结构实现
Queap
直方图最大矩形
44-Histogram-MaxRectangle-impl
问题描述
在非负整数值的直方图区间 H[0, n)
中,如何找到最大的竖直矩形?
显然求最大矩形面积的公式为:maxRect(r)=H[r]⋅(t(r)−s(r))
这里
- s (r)表示区间
[0,r]
上小于 H[r]
的最大值的坐标:
- s(r)=max{k∣0≤k≤r and H[k−1]<H[r]}
- t (r)表示区间
[r,n]
上小于 H[r]
的最小值的坐标:
- t(r)=min{k∣r<k≤n and H[r]>H[k]}
暴力法
一一测试所有可能的 r 值,时间复杂度是 O(n2),因为每一个 r 都要确定 s(r) 和 t(r)
使用栈
每一轮循环的结束,S 都会存储一串 s[]
,有如下关系:
S[S.size()−1]=S.top()=r 并且 ∀0≤k<S.size(),S[k−1]+1=s[S[k]]
One-pass
对于 t(r) 而言,只有当输入完全结束后才能开始,不是一个在线算法。若要改进到 s(r) 和 t(r) 都只是一轮扫描确定:
每一次外部循环中,总有:
∀0≤k>SR.size(),SR[k−1]+1=s[SR[k]]
对每个内层循环中弹出的 r,有:
t(r)=t 并且 s[r]=SR.top()+1
栈堆与队列堆
Steap
Steap = Stack + Heap = push + pop + getMax
使用两个栈 S 和 P,S 存储数据,P 则存储 S 中对应后缀的最大者(即 S.getMax()
)
ADT:
Steap::getMax(){return P.top();}
Steap::pop(){P.pop(); return S.pop();}//O(1)
Steap::push(){P.push(max(e,P.top()));S.push(e);}//O(1)
Queap
Queap = Queue + Heap = enqueue + dequeue + getMax
使用两个队列 Q 和 P,Q 存储数据并且是单进单出;P 存放 Q 的后缀的最大值,并且允许队尾插入和删除两种操作,即单进双出:
ADT:
Queap::getMax(){return P.front();}
Queap::dequeue(){P.dequeue();return Q.dequeue();}//O(1)
Queap::enqueue(e){Q.enqueue(e);P.enqueue(e);for(x=P.rear();x && (x->key <=e);x=x->pred) x->key=e;} // 最坏O(n)
双栈当队
ADT
复杂度(均摊)
最好情况:O(1)
最坏情况:O(n)
习题:41-Stack-queue-Exercise