03栈,队列和数组

栈

Q: 对于 n 个不同的元素, 其所有可能的出栈序列有多少种? 被叫作什么?
A: 共有 种可能的出栈序列.
可能的出栈序列数量 被称为卡特兰数 (Catalan number).

Q: 共享栈, 相对于顺序栈对存取效率有影响吗?
A: 存取数据的时间复杂度均为
对存取效率没有影响

队列

Q: 有了顺序队列为什么还要使用循环队列?
A: 顺序队列存在假溢出的情况
使用循环队列来解决顺序队列的假溢出

Q: 与顺序队列相比, 链式队列有哪些主要优点?
A: 1. 特别适合于数据元素变动比较大的情形.
2. 不存在队列满而产生的上溢问题, 只要内存允许, 就可以一直入队.

栈

Q: 如何利用栈实现中缀表达式转后缀表达式?
A: 遍历中缀表达式的每个元素, 根据以下规则操作:

1. 遇到操作数: 直接输出到后缀表达式.
2. 遇到运算符:
   • 若栈为空, 或栈顶元素为 (, 或当前运算符优先级高于栈顶运算符, 则直接入栈.
   • 否则, 不断弹出栈顶运算符并输出, 直到栈顶运算符的优先级低于当前运算符, 然后将当前运算符入栈.
3. 遇到界限符:
   • 遇到 (: 直接入栈.
   • 遇到 ): 依次弹出栈内运算符并输出, 直到遇到 (. (注意: ( 不输出).
4. 遍历结束: 将栈中所有剩余运算符依次弹出并输出.

可以将递归算法转换为非递归算法, 通常需要借助{栈}(某种数据结构) 来实现这种转换.

Q: 消除递归一定需要使用栈吗?
A: 使用栈可以模拟递归的过程, 以此来消除递归, 但对于单向递归和尾递归而言, 可以用迭代
的方式来消除递归

数组和特殊矩阵