第三章 栈和队列
一些面试题
5. 说说栈和队列的区别。★★
栈和队列都是操作受限的线性表。
栈
对于插入到栈的元素按“后进先出”的规则处理，插入和删除操作都在栈顶进行，一般用定长数组存储栈元素。由于进栈和出栈都是在栈顶进行，因此要有一个size变量来记录当前栈的大小。
队列
允许在一端进行插入另一端进行删除的线性表。队列顾名思义就像排队一样，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。
6. 简要说说共享栈。★
让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。这样能够更有效的利用存储空间，只有在整个存储空间被占满时才发生溢出。
7. 如何区分循环队列是队空还是队满？★★
普通情况下，循环队列队空和队满的判定条件是一样的，都是Q.front == Q.rear。
为了区分可采用两种方法：
方法一：牺牲一个单元来区分队空和队满，这个时候(Q.rear+1)%MaxSize == Q.front才是队满标志。
方法二：类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size == 0；队满的条件为Q.size == MaxSize。
8. 说说栈在括号匹配中的算法思想。★★
1）出现的凡是左括号，则进栈；
2）出现的是右括号，如果栈不空而且栈顶元素是左括号，那么相匹配，否则不匹配。
3）表达式检验结束时，如果栈空则表明表达式中匹配正确，否则表明“左括号”有余。
9. 说说栈在后缀表达式求值的算法思想。★★
例如ABCD-*+ED/-。
顺序扫描表达式的每一项，然后根据它的类型做如下相应操作：
- 若该项是操作数，则将其压入栈中；
- 若该项是操作符，则连续从栈中退出两个操作数y 和x，形成运算指令XY，并将计算结果重新压入栈中。
- 当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。
10. 说说栈在计算机系统中的应用。★★
- 函数调用：栈在函数调用中扮演着重要角色。每当一个函数被调用时，函数的参数、局部变量和返回地址等信息都会被保存在栈中的帧中。函数执行完毕后，相应的帧会被从栈中弹出，恢复上一个函数的执行。
- 表达式求值：编译器和解释器通常使用栈来求解表达式。例如，中缀表达式转换为后缀表达式时，使用栈来调整操作符的顺序。
- 括号匹配：栈也常用于括号匹配的问题。通过遍历输入字符串并将左括号入栈，当遇到右括号时，检查栈顶元素是否与之匹配。可以利用栈的后进先出（LIFO）特性来快速判断括号是否匹配。
11. 说说队列在计算机系统中的应用。★★
- 任务调度：操作系统中的任务调度器通常使用队列数据结构来管理和调度进程或线程。
- 缓冲区管理：网络通信、磁盘I/O等场景中常需要使用队列来处理数据的缓冲区。
- 消息传递：消息队列是实现异步通信和解耦的重要方式。多个组件之间通过将消息放入队列来进行通信，接收者可以从队列中取出并处理消息。
来源：
计算机保研/考研面试题——数据结构与算法篇_计算机保研面试 csdn-CSDN博客
侵删