第3章：栈与队列详解 - LIFO/FILO原理与顺序/链式实现

第3章主要探讨了栈和队列这两种基本但极其重要的数据结构。栈和队列是操作受限的线性数据结构，具有独特的操作规则，分别为栈的“后进先出”（LIFO）原则和队列的“先进先出”（FIFO）原则。 **栈** 1. **栈的基本定义**：栈是一种特殊的线性表，其特点是只允许在一端进行插入（进栈，压栈）和删除（出栈，退栈）操作。栈顶代表元素的插入和删除位置，栈底则不可进行这些操作。例如，一个栈可以被想象成一个堆叠的盘子，只能在顶部添加或移除盘子。 2. **顺序存储与链式存储**：顺序栈通常使用数组实现，通过数组的连续存储单元存储元素，栈顶由一个附加的top指针指示。链式存储则利用链表，每个节点包含数据和指向下一个节点的指针。 3. **应用与递归实现**：栈在计算机科学中有广泛应用，如函数调用堆栈、表达式求值、括号匹配等。递归算法中，栈用于保存函数调用的状态。 **队列** 1. **队列的基本定义**：队列也是一种线性结构，但与栈不同的是，队列在两端都允许插入（入队）和删除（出队）操作。队列类似于排队等候，先进队列的元素先出队。 2. **链式存储**：队列同样可以用链表实现，通过头指针和尾指针控制元素的进出。 3. **循环队列与顺序存储**：顺序队列如果采用数组实现，可能会遇到溢出问题，这时引入循环队列，通过数组的边界处理，使得队列可以在数组的一端无限循环。 **栈和队列的抽象数据类型（ADT）**： ADTStack定义了栈的数据结构，包括数据对象（D）、数据关系（R）以及一系列基本操作，如初始化、销毁、清空、检查是否为空、获取栈长度、查看栈顶元素、入栈和出栈，以及遍历栈等。 总结来说，本章详细介绍了栈和队列的概念、操作特性和实现方式，对于理解计算机数据结构的基础理论和实际应用至关重要。掌握栈和队列有助于解决许多算法问题，比如动态规划中的状态转移、图形遍历等场景。同时，了解它们的实现原理也有助于设计高效的软件和数据结构优化。