⑴ 数据结构——知识点总结-栈和队列
数据结构：栈与队列的深度解析
栈，这个术语源自拉丁文"staurus"，意为"矛尖"，形象地描绘了其像矛尖一样只允许在一端进出的特点。它是线性数据结构的一种，遵循FILO（First In Last Out，先进后出）原则，如同子弹出膛的顺序。主要有顺序栈和链栈两种实现方式。
与之相对的是队列，它遵循的是FIFO（First In First Out，先进先出）策略，像食堂排队打饭一样，遵循先到先服务。队列同样有两种基础形式，即顺序队列和链队。
理解它们的操作至关重要，包括初始化、基本的入栈与出栈操作，以及满/空状态的判断。栈在括号匹配、中缀/前缀/后缀表达式转换中大显身手，而队列则在共享栈和双端队列的习题中体现其灵活性。
实战挑战
- 体验后进先出的栈操作，如快速解决问题：后进先出。
- 掌握栈与队列的边界管理：实现满、空状态的检测。
- 理解n-i+1的巧妙应用：队列的动态操作。
- 探索未知的可能：在特定情境下，探索不同数据结构的性能差异。
- 在C语言中实践：运用栈实现递归调用和表达式求值。
- 栈的多元素操作：连续push和pop操作。
- 挑战队列的边界操作：更新top元素和调整指针。
- 队列的特殊情况：队尾元素可能需要更新头尾指针。
- 深入理解递归调用：如何用栈来支持递归过程。
- 循环队列的入队魔术：rear位置更新的技巧。
- 队列状态变化后的观察：front和rear的新位置。
- 判断队列是否为空：通过比较front和rear。
- 共享特性：栈与队列都遵循端点操作原则。
习题详解
- 入队序列{a,b,c,d,e}可能的出队序列：D. {e,c,b,a,d}，因为队列遵循先进先出。
- 栈的出栈序列：入栈为{a,b,c,d,e}，可能的出栈序列包括d,e,c,b,a等，但不包括C选项中的顺序。
- 循环队列初始化：front=0, rear=n-1，确保队列有足够空间。
- 中缀表达式到后缀表达式的转换：当有5个操作符时，可能需要转换为后缀表达式。
- 栈的元素转换：入栈n个元素，出栈为3，最多可能有n-1个元素。
栈和队列，这两个看似简单的数据结构，却蕴含着无限的奥秘和应用场景。熟练掌握它们，是数据结构学习旅程中的重要一步。