07 | 理论讲解：堆栈&队列-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 07 | 理论讲解：堆栈&队列

在编程与算法的世界中，堆栈（Stack）和队列（Queue）是两种基础而极其重要的数据结构，它们各自以独特的操作方式支持着数据的存取，是理解和实现复杂算法、系统设计以及解决现实问题的基石。本章将深入剖析堆栈与队列的基本概念、性质、操作原理及其在算法面试中的典型应用。

#### 一、堆栈（Stack）

##### 1.1 定义与性质

堆栈是一种遵循后进先出（Last In, First Out, LIFO）原则的有序集合。在堆栈中，新添加的或待删除的元素都保存在堆栈的同一端，这一端被称为栈顶（Top），而另一端则称为栈底（Bottom）。堆栈的主要操作包括入栈（Push）、出栈（Pop）、查看栈顶元素（Peek/Top）以及判断堆栈是否为空（IsEmpty）。

- **入栈（Push）**：将一个元素添加到堆栈的顶部。
- **出栈（Pop）**：移除并返回堆栈顶部的元素。如果堆栈为空，则此操作可能导致错误。
- **查看栈顶元素（Peek/Top）**：返回堆栈顶部的元素，但不移除它。
- **判断堆栈是否为空（IsEmpty）**：检查堆栈中是否没有元素。

##### 1.2 实现方式

堆栈可以通过数组或链表来实现，每种方式都有其优缺点。

- **基于数组的堆栈**：实现简单，空间连续，但存在数组扩容的开销，且可能存在空间浪费（尤其是在动态扩容时）。
- **基于链表的堆栈**：不需要预先分配固定大小的空间，动态扩展灵活，但每个元素都需要额外的指针空间来存储下一个元素的地址。

##### 1.3 应用场景

- **函数调用栈**：在程序执行过程中，函数调用会形成调用栈，每个函数调用的参数、局部变量等信息都保存在栈上，当函数返回时，这些信息会从栈中弹出，恢复到调用前的状态。
- **括号匹配**：通过堆栈可以高效解决括号匹配问题，每当遇到左括号时压入堆栈，遇到右括号时检查是否与栈顶左括号匹配。
- **表达式求值**：利用两个堆栈（一个用于存储数字，一个用于存储操作符）可以实现中缀表达式到后缀表达式的转换及计算。
- **页面访问历史**：浏览器的页面访问历史可以看作是一个堆栈，最新访问的页面位于栈顶，通过“后退”操作可以依次访问之前的页面。

#### 二、队列（Queue）

##### 2.1 定义与性质

队列是一种遵循先进先出（First In, First Out, FIFO）原则的有序集合。在队列中，元素的添加操作（入队）发生在队列的一端，称为队尾（Rear）；而元素的移除操作（出队）则发生在队列的另一端，称为队头（Front）。队列的主要操作包括入队（Enqueue）、出队（Dequeue）、查看队头元素（Front）以及判断队列是否为空（IsEmpty）。

- **入队（Enqueue）**：将一个元素添加到队列的尾部。
- **出队（Dequeue）**：移除并返回队列头部的元素。如果队列为空，则此操作可能导致错误。
- **查看队头元素（Front）**：返回队列头部的元素，但不移除它。
- **判断队列是否为空（IsEmpty）**：检查队列中是否没有元素。

##### 2.2 实现方式

队列同样可以通过数组或链表来实现，但实现方式及面临的挑战略有不同。

- **基于数组的队列**：需要处理“假溢出”问题，即当数组末尾空间被占满时，即使数组前端仍有空闲空间，也无法继续入队。一种解决方案是使用循环队列（Circular Queue），通过模运算实现队列的循环使用。
- **基于链表的队列**：不需要担心空间限制问题，可以动态扩展，但每个节点同样需要额外的指针空间。

##### 2.3 应用场景

- **任务调度**：在多任务操作系统中，CPU的任务调度常常采用队列来实现，确保先到达的任务先被执行。
- **广度优先搜索（BFS）**：在图的遍历算法中，BFS通过队列来保存待访问的节点，确保按照节点被发现的顺序进行访问。
- **打印机任务队列**：在打印系统中，打印任务按照提交的顺序排队，先提交的任务先被打印。
- **消息队列**：在分布式系统中，消息队列用于解耦服务间的调用，确保消息按顺序传递并被处理。

#### 三、堆栈与队列的比较

虽然堆栈和队列都是线性数据结构，但它们的存取原则和应用场景有着显著的差异：

- **存取原则**：堆栈遵循LIFO原则，适合需要后进先出操作的场景；而队列遵循FIFO原则，适用于需要保持元素顺序的场景。
- **应用场景**：堆栈常用于函数调用、括号匹配、递归实现等场景；队列则广泛应用于任务调度、广度优先搜索、消息传递等场景。
- **操作复杂度**：在理想情况下（不考虑动态扩容或缩容的开销），堆栈和队列的主要操作（入栈/出栈、入队/出队）的时间复杂度均为O(1)。

#### 四、算法面试中的堆栈与队列

在算法面试中，堆栈与队列的应用十分广泛，常常作为考察候选人数据结构与算法基础、逻辑思维及问题解决能力的重要手段。以下是一些常见的面试题目类型：

- **实现堆栈或队列**：要求手写堆栈或队列的实现代码，可能涉及动态数组或链表的应用。
- **堆栈与队列的变种**：如实现一个最小堆栈或最大队列，要求在常数时间内获取到堆栈中的最小元素或队列中的最大元素。
- **利用堆栈或队列解决问题**：如使用两个堆栈实现队列、使用队列实现层次遍历等。
- **算法优化**：在特定算法中引入堆栈或队列来优化性能，如利用堆栈简化递归问题、利用队列实现图的BFS遍历等。

#### 结语

堆栈与队列作为最基础的数据结构之一，不仅在算法设计与分析中扮演着重要角色，也是理解复杂数据结构（如优先队列、栈的变种等）和算法（如递归、动态规划等）的基石。掌握堆栈与队列的基本概念、性质、操作原理及其应用，对于提升编程能力、解决实际问题以及顺利通过算法面试都具有重要意义。希望本章的内容能为读者提供扎实的理论基础和实用的解题技巧。

该分类下的相关小册推荐：

数据结构与算法(下)

业务开发实用算法精讲

编程之道-算法面试(下)

数据结构与算法(上)

编程之道-算法面试(上)

数据结构与算法(中)

数据结构与算法之美