本文共 1907 字，大约阅读时间需要 6 分钟。

第三章：栈和队列

3.1 栈的基本概念

栈是计算机科学中一个非常重要的数据结构，它本身是一种线性表，但其特点是只允许在一端（称为栈顶）进行插入和删除操作。栈的底部是固定的，通常不允许插入或删除元素，而栈顶则是可以灵活操作的端点。栈的核心特性是后进先出（Last-In-First-Out，LIFO），意味着最后进入栈的元素会先被删除。

栈的定义非常简单：它是一种线性表，规定只能在栈顶端进行插入和删除操作。这种结构决定了栈在许多算法和应用中都有独特的优势。

栈的特点可以总结为以下几点：

栈在算法中广泛应用，例如括号匹配、表达式求值、递归算法等。栈的核心优势在于其高效的操作特性，允许在O(1)时间复杂度内完成入栈和出栈操作。

3.2 栈的顺序存储结构

栈的顺序存储结构与数组或链表类似，但由于栈的特性，存储结构需要有一些特殊的规则。常见的栈存储方式有两种：连续存储和分块存储。

在连续存储中，栈使用一个连续的内存块，栈顶指针始终指向栈顶元素的下一个位置。这种方式简单且效率高，适合处理大量数据。连续栈的实现需要考虑动态扩展内存空间，当栈已满时需要重新分配更大的内存块。

分块存储则是将栈分成多个固定大小的块，每个块内部维护一个栈顶指针。这种方式在处理大数据量时效率更高，但实现复杂度较高。

3.3 栈的链式存储结构

链栈是一种基于链表的栈实现，其核心特点是每个节点只包含数据和指向下一个节点的指针。链栈的实现方式与链表类似，但为了提高读取效率，通常会将链表的起点指针作为栈顶指针。

链栈的优势在于其灵活性，能够轻松处理动态数据扩展。这种结构在某些高级算法中表现出色，但由于链表的访问效率较低，通常在处理大量数据时会选择连续栈。

3.4 队列的基本概念

队列是一种允许在一端插入数据，另一端删除数据的线性表。队列的特点是先进先出（First-In-First-Out，FIFO），与栈的后进先出原则相反。

队列的基本定义非常简单：只允许在队头端进行删除操作，而在队尾端进行插入操作。队列在许多实际场景中都有广泛应用，例如资源调度、数据传输等。

队列的特点包括：

3.5 队列的顺序存储结构

队列的顺序存储结构与栈类似，但需要额外的指针来维护队头和队尾。队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。

为了提高效率，队列通常采用循环存储结构，避免“上溢出”问题。当队首指针指向队尾指针的下一个位置时，表示队列已满。解决这种情况的方法有以下几种：

3.6 队列的链式存储结构

链队列是一种基于链表的队列实现，保持了链表的灵活性。链队列由队头指针和队尾指针共同维护，队头指针始终指向队头元素，队尾指针则指向队尾元素的下一个位置。

链队列的实现方式与链栈类似，但队列支持在队尾端插入和删除操作。这种结构在某些高级算法中表现出色，但由于链表的访问效率较低，通常在处理大量数据时会选择数组实现的队列。

3.7 双端队列

双端队列是一种允许在两端进行插入和删除操作的队列。双端队列的应用场景包括多任务调度、资源管理等，能够在两端灵活地进行数据处理。

双端队列的实现方式可以分为两种：

双端队列在处理复杂的数据流时表现出色，能够高效地完成多任务调度。

3.8 栈和队列的应用

栈在括号匹配中的应用最为广泛。通过维护一个栈，可以高效地检查括号是否匹配。例如，输入一个字符串，遍历其中的括号，左括号入栈，右括号出栈，最后栈的状态即可判断括号是否匹配。

栈在表达式求值中的应用同样重要。通过将中缀表达式转换为后缀表达式，再利用栈完成表达式的计算，可以高效地得到结果。栈的优势在于其高效的操作特性，能够在O(1)时间复杂度内完成入栈和出栈操作。

栈在递归中的应用也非常重要。递归算法实际上通过系统栈来实现函数调用和返回，允许程序高效地执行多层函数调用。

队列在层次遍历中的应用可以追溯到二叉树的遍历算法。通过使用队列，可以实现先进先出的遍历方式，例如广度优先搜索（BFS）。

队列在计算机系统中的应用也非常广泛。例如，用于处理网络数据包、任务调度、资源管理等。队列能够有效地解决多线程程序中资源竞争问题，确保数据处理的有序性。