算法1

3月 21, 2025

递归、栈、队列与深度优先搜索（DFS）详解

在学习编程时，递归和数据结构如栈（Stack）和队列（Queue）是必不可少的知识点。这些概念被广泛用于解决问题，如深度优先搜索（DFS）。本文将介绍：

递归的工作原理
栈的概念和操作
队列及其与栈的区别
深度优先搜索（DFS） 如何利用递归

1. 递归：许多算法的基础

什么是递归？

递归是一种编程技巧，在其中函数调用自身来解决问题。递归函数通常包含两个部分：

基本情况（Base Case） – 终止递归的条件。
递归情况（Recursive Case） – 调用自身处理更小的问题。

示例：阶乘计算

阶乘（n!）的定义如下：

n! = n × (n-1) × (n-2) × ... × 1

使用 C++ 实现的递归阶乘函数：



int fact(int n) {

    if (n == 0) return 1; 

    return n * fact(n - 1);

}

2. 栈（Stack）：LIFO 数据结构

什么是栈？

栈是一种后进先出（LIFO，Last In, First Out）的数据结构，意味着最后添加的元素最先被移除。

栈的基本操作：

push(x): 将元素压入栈顶。
pop(): 移除栈顶元素。
top(): 查看栈顶元素。

栈的 C++ 代码示例



#include <stack>

#include <iostream>

using namespace std;

int main() {

    stack<int> s;  

    s.push(1);   

    s.push(2);   

    s.push(3);   

    cout << s.top() << endl; // 3

    s.pop();  

    cout << s.top() << endl; // 2

    return 0;

}

3. 队列（Queue）：FIFO 数据结构

什么是队列？

队列是一种先进先出（FIFO，First In, First Out）的数据结构，意味着最先添加的元素最先被移除。

队列的基本操作：

push(x): 将元素添加到队列末尾。
pop(): 移除队列前端的元素。
front(): 查看队列前端的元素。

队列的 C++ 代码示例



#include <queue>

#include <iostream>

using namespace std;

int main() {

    queue<int> q;

    q.push(1);

    q.push(2);

    q.push(3);

    cout << q.front() << endl; // 1

    q.pop();  

    cout << q.front() << endl; // 2

    return 0;

}

栈与队列对比

特性	栈（LIFO）	队列（FIFO）
插入	`push(x)` 添加到顶部	`push(x)` 添加到末尾
移除	`pop()` 移除顶部元素	`pop()` 移除前端元素
顺序	后进先出	先进先出

4. 深度优先搜索（DFS）

什么是 DFS？

深度优先搜索（DFS）是一种遍历树或图的算法。它从一个节点开始，尽可能深入地访问，然后回溯。

DFS 遍历示例

递归实现 DFS



void dfs(int node) {

    visited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {

            dfs(neighbor);

        }

    }

}

总结

递归通过分解问题简化计算。
栈采用 LIFO 规则，常用于递归调用和回溯。
队列采用 FIFO 规则，常用于广度优先搜索（BFS）。
DFS 依赖栈结构，是常见的图遍历算法。

理解这些概念对于掌握算法与数据结构至关重要！欢迎尝试实现这些数据结构，并用于竞赛编程或算法练习。

このブログを検索

Lightning Insights

算法1