栈(stack)


 

 L


二、栈的动作:

 

  • 结合函数调用栈的机制介绍一般函数调用的实现方式与过程,并将其推广到递归调用。
  • 以降低空间复杂度的目标为线索,介绍通过显式的维护栈的结构解决应用问题的典型方法和技巧。
  • 利用栈结构,实现基于试探回溯策略的高效搜索算法。
  • 基于轮值策略的通用循环分配器,并以银行窗口服务为例实现基本的调度算法。

栈禁止操作的一端称为盲端,


三、Stack模板类:

 将向量的末尾作为栈的入口:

 


三、Stack之应用一:逆序输出

  输出次序与处理过程次序是颠倒的;递归深度和输出的长度不容易知道。

进制转换例子:

  

 迭代实现:

  


四、Stack之应用一:递归嵌套

  具有自相似性的问题可递归描述,但分支位置和嵌套深度不确定。

 

 减而治之和分而治之:失败!!!

  

 构思思路:

 


 

 


 五、栈混洗(stack permutation)

  将栈A中的元素经过栈S插入栈B中,一些列的pop()和push()操作,就可以改变栈中元素的序列。

  

 

 长度为n的序列,栈混洗总数S(n)是多少?

  

 

栈混洗的甄别问题?

  栈混洗的禁形?

  栈混洗与括号匹配之间有关系:

  


六、延迟缓冲

  线性扫描算法模式中,在预读足够长之后,方能确定可处理的前缀。(evaluation)

例如如下软件中的表达式求值的语言,都是采用的什么语法呢?

  

  

陈小洁的三只猫
原文地址:https://www.cnblogs.com/ccpang/p/11440624.html