严蔚敏《数据结构》栈与队列解析

的八进制、十六进制表示。此问题可以利用栈来解决。首先，将十进制数除以基数（8或16），然后对每次除法的余数进行收集，余数从低位到高位依次入栈。当十进制数除以基数得到的商为0时，停止除法。接下来，依次弹出栈中的元素，这些元素就是对应的八进制或十六进制表示的各位数字。 例二、表达式求值 中缀表达式（如2+3*4）的求值通常采用逆波兰表示法（后缀表达式，如2 3 4 * +），也就是将运算符放在操作数之后。通过栈，我们可以很容易地实现这个转换和求值过程。首先，遍历中缀表达式，遇到数字就压入栈，遇到运算符则比较栈顶两个元素进行运算，结果再入栈。最后栈中剩下的元素就是表达式的结果。 例三、括号匹配 在编译原理中，括号的匹配也是一个经典的栈应用。遍历字符串，遇到左括号就入栈，遇到右括号时检查栈顶是否为匹配的左括号，如果是则弹出栈顶元素，否则表示括号不匹配。遍历结束后，如果栈为空则表示括号匹配，否则表示有未配对的括号。 3.3 队列的类型定义 与栈类似，队列也是线性数据结构，但其特点是“先进先出”（FIFO）。队列的数据对象和数据关系与栈相同，但其基本操作有所不同： - InitQueue(&Q): 构造一个空队列Q。 - DestroyQueue(&Q): 队列Q已存在，将其销毁。 - ClearQueue(&Q): 队列Q已存在，将其清空。 - QueueEmpty(Q): 队列Q已存在，判断是否为空，为空则返回TRUE，否则FALSE。 - QueueLength(Q): 返回队列Q的元素个数，即队列的长度。 - GetFront(Q, &e): 队列Q非空，返回队首元素e，但不删除。 - EnQueue(&Q, e): 向队列Q尾部插入元素e。 - DeQueue(&Q, &e): 队列Q非空，删除队首元素并返回其值e。 3.4 队列的应用 队列广泛应用于操作系统中的任务调度、打印机任务队列以及网络数据包传输等场景。例如，在操作系统中，多个进程或线程等待CPU执行时，会形成一个等待队列，系统会按照先进先出的原则分配CPU时间片。 3.5 循环队列与链式队列 循环队列是为了解决顺序存储队列在满和空时带来的边界问题，通过巧妙的索引处理，使得队列可以在数组内循环使用。链式队列则通过链表结构实现，具有更好的动态扩展性。 总结： 数据结构中的栈和队列是两种基础但极其重要的线性数据结构。栈遵循“后进先出”原则，常用于实现递归、表达式求值、括号匹配等问题；而队列遵循“先进先出”原则，常见于任务调度、资源分配等场景。理解并熟练掌握这两种数据结构及其操作，是深入学习数据结构和算法的基础。