栈
卡特兰数
栈的数学性质: 当 n 个不同元素进栈时, 出栈元素不同排列的个数为{
Q: 共享栈, 相对于顺序栈对存取效率有影响吗?
A: 存取数据的时间复杂度均为
对存取效率没有影响
队列
Q: 有了顺序队列为什么还要使用循环队列?
A: 顺序队列存在假溢出的情况
使用循环队列来解决顺序队列的假溢出
循环队列使用
队满条件: (Q.rear+1) mod MaxSize==Q.front
队空条件: Q.front==Q.rear.
队列中元素的个数: (Q.rear-Q.front+MaxSize)8MaxSize.
链式存储队列的优点
用单链表表示的链式队列特别适合于数据元素变动比较大的情形, 而且不存在队列满且产生溢出的问题
栈和队列的逻辑结构相同
主要区别在于插入, 删除操作的限定不一样
用单链表实现队列时, 队头总是设在链表的队头的位置
栈
Q: 如何利用栈实现中缀表达式转后缀表达式?
A: 操作数: 不入栈
运算符: 入栈
If 优先级高于栈中的所有运算符
Then 入栈
else 弹出所有优先级高于或等于该运算符, 直到遇到优先级更低或者界限符 (
Then 入栈
界限符:
(: 直接入栈
): 弹出到 ( 为止
可以将递归算法转换为非递归算法, 通常需要借助{栈}(某种数据结构)来实现这种转换.
栈的应用:
递归, 表达式求值, 括号匹配
队列的应用:
缓冲区, 图和树的层次遍历
Q: 消除递归一定需要使用栈吗?
A: 使用栈可以模拟递归的过程, 以此来消除递归, 但对于单向递归和尾递归而言, 可以用迭代
的方式来消除递归