数据结构

• 1: 绪论
• 1.1: 数据结构基本概念
• 1.2: 算法基本概念
• 2: 线性表
• 2.1: 定义和基本操作
• 2.2: 顺序表示
• 2.3: 链式表示
• 3: 线性数据结构
• 3.1: 栈
• 3.2: 队列
• 3.3: 栈和队列的应用
• 3.4: 数组和特殊矩阵
• 4: 字符串
• 4.1: 定义和实现
• 4.2: 模式匹配
• 5: 树与二叉树
• 5.1: 树
• 5.2: 二叉树
• 5.3: 树的应用
• 6: 图
• 6.1: 定义
• 6.2: 算法和应用
• 7: 查找
• 7.1: 数组查找
• 7.2: 树形查找
• 7.3: 散列表查找
• 8: 排序
• 8.1: 内部排序
• 8.2: 外部排序

1 - 绪论

1.1 - 数据结构基本概念

数据结构

数据结构（Data Structure）是 存储、组织和管理数据的方式，它不仅决定了数据的存储形式，也影响数据访问和操作的效率。

分类

mindmap
  root((数据结构<br/>Data Structure))
    线性结构
      数组 Array
        连续内存
        随机访问快
        插入删除慢
      链表 Linked List
        节点指针连接
        插入删除快
        访问慢
      栈 Stack
        后进先出 LIFO
        函数调用
        表达式求值
      队列 Queue
        先进先出 FIFO
        任务调度
      双端队列 Deque
        两端可操作
    树形结构
      二叉树<br/>Binary Tree
      二叉搜索树<br/>BST
      堆 Heap
        优先队列实现
      平衡树
        AVL树
        红黑树
    图结构
      有向图
      无向图
      存储方式
        邻接矩阵
        邻接表
      应用场景
        路径搜索
        社交网络建模
    散列表<br/>Hash Table
      哈希函数
      快速查找
      应用
        字典
        缓存

考试中涉及的数据结构可以分为以下几种：

1. 线性结构（元素之间有顺序关系）
   • 数组（Array）：连续内存，随机访问快，插入删除慢
   • 链表（Linked List）：节点通过指针连接，插入删除快，访问慢
   • 栈（Stack）：后进先出（LIFO），用于函数调用、表达式求值
   • 队列（Queue）：先进先出（FIFO），用于任务调度
   • 双端队列（Deque）：两端都可以操作
2. 树形结构（元素之间有层级关系）
   • 二叉树（Binary Tree）
   • 二叉搜索树（BST）
   • 堆（Heap）：优先队列实现
   • 平衡树（AVL、红黑树）
3. 图结构（元素之间有网络关系）
   • 有向图 / 无向图
   • 邻接矩阵 / 邻接表存储
   • 常用于路径搜索、社交网络建模
4. 散列表（Hash Table）
   • 通过哈希函数实现快速查找
   • 常用于字典、缓存

算法

算法（Algorithm）是 解决问题的一系列步骤或方法，用来操作数据结构，实现具体功能。

数据结构和算法的关系

• 数据结构提供“容器”
• 算法提供“操作方法”
• 好的数据结构可以让算法更高效
• 算法的设计也依赖数据结构特性

💡 举例：

• 用数组实现栈 → 可以快速访问栈顶
• 用链表实现队列 → 插入删除都很快
• 用堆实现优先队列 → 可以快速找最大/最小值
• 用图 + BFS → 可以找最短路径

1.2 - 算法基本概念

什么是算法

算法 (Algorithm) 是一个明确规定了操作步骤的有限指令集，用于计算函数、处理数据、解决一个特定问题或执行某个任务。

算法 的基本属性：

1. 明确性：每一步骤必须有明确且不含糊的定义。
2. 有输入和输出：算法 应有 0 个或更多的 输入 和 1 个或更多的 输出。输入 是在 算法 开始之前提供的，而 输出 是在 算法 结束时产生的。
3. 有限性：如果 算法 在执行完有限步骤后终止，那么它就是 有限的。换句话说，一个 算法 必须总是在执行有限次操作后结束。
4. 可行性：算法 中的每一步都应该是简单且基本的，这样它们可以在有限的时间内完成并由计算机执行。
5. 独立性：算法 的指令应该有普适性，也就是说，它们不应依赖于任何特定的编程语言或模型。相反，算法 应该足够通用，可以在任何编程环境中实现。

效率度量

时间复杂度

时间复杂度（Time Complexity）是计算机科学中衡量一个 算法运行效率 的重要指标。它主要描述了当输入规模（通常记为 $n$ ）不断增大时，算法执行所需的 基本操作次数 的增长趋势。

在算法的时间复杂度分析中， 基本操作次数 指的是一个算法中执行时间固定的 最小操作单元。你可以把它理解为计算机执行一次最基础、最原始的指令所花费的时间。

这些基本操作通常包括：

• 算术运算：例如，加、减、乘、除、取模等。
• 比较运算：例如，小于、大于、等于等。
• 赋值操作：将一个值赋给一个变量。
• 逻辑运算：例如，与、或、非等。

计算方法

设输入规模为 $n$ ，算法执行所需的 基本操作次数 记为 $T(n)$ 。 为了衡量算法效率，我们关心 $T(n)$ 随 $n$ 增大的增长趋势，而不是精确的操作次数。

时间复杂度就是 $T(n)$ 的 渐近上界，常用 大 $O$ 符号 表示为：

其中 $f(n)$ 是能反映 $T(n)$ 增长速度的函数。 换句话说，时间复杂度刻画的是 当 $n$ 趋于无穷大时，算法执行时间随输入规模增长的量级。

常见时间复杂度

常见的 时间复杂度（按增长速度排序）有：

• $O(1)$ ：常数时间。无论 输入 数据有多大，算法 都在恒定的时间内完成。
• $O(\log n)$ ：对数时间。例如：二分搜索。
• $O(n)$ ：线性时间。例如：简单的搜索 算法。
• $O(n\log n)$ ：线性对数时间。例如：高效的排序 算法，如归并排序。
• $O(n^2)$ 、 $O(n^3)$ …：多项式时间。例如：冒泡排序、插入排序和选择排序是 $O(n^2)$ 。
• $O(2^n)$ ：指数时间。例如：计算斐波那契数列的递归实现。
• $O(n!)$ ：阶乘时间。例如：旅行商问题的暴力解决方法。

空间复杂度

空间复杂度（Space Complexity）是衡量 算法执行过程中所需存储空间 随输入数据量增长而变化的指标。它不仅包括算法中用来存放 输入数据 的空间，还包括 辅助变量、递归调用栈 等临时空间。与时间复杂度类似，我们关注的是 增长趋势，通常只关注最高阶的量级，用大 $O$ 符号表示。

组成

1. 固定部分
   • 包括常量、程序代码本身、简单变量、常量数组等。
   • 这一部分的空间大小与输入数据规模无关，通常记为 $O(1)$ 。
2. 可变部分
   • 随着输入数据量的变化而变化的空间，主要包括：
     • 输入数据本身（如数组、链表）
     • 辅助空间（如临时数组、栈、队列等）
     • 递归调用栈（递归深度对空间占用有直接影响）

常见空间复杂度

常见的 空间复杂度（按增长速度排序）有：

2 - 线性表

学习思维导图：

# 线性表

## 线性表的基本概念

## 线性表的实现

- 顺序存储
- 链式存储

## 线性表的应用

2.1 - 定义和基本操作

线性表定义

线性表（Linear List）是 L 数据结构 中的一种基本结构。它是 零个或多个数据元素的有限序列。通常，线性表 中的 数据元素 之间是 有序的，它们之间存在着 前驱和后继的关系。

特点：

• 个数有限
• 表中元素数据类型都相同，每个元素占有 相同大小的存储空间
• 仅讨论 元素间的逻辑关系，表中元素有 先后顺序

顺序表和链表

线性表分为顺序存储结构（又称 顺序表）和链式存储结构（又称为 链表）。

顺序表中的元素存储地址是 连续的（存储在栈中），而链表的元素存储地址是 非连续的（存储在堆中），元素节点中除了存储数据元素之外还存储相邻元素的地址信息。顺序表中数据之间的 逻辑关系 和 物理关系 是一致的，链表中数据元素的逻辑关系和物理关系并不一定一致。

上图中左边为顺序表，右边为链表。顺序表在内存中的地址是连续的，各个元素的下标之间是有规律可循的，通过一个已知下标的元素可以找到顺序表中任意一个其它元素。但是链式表中的元素在内存中的地址是不连续的，所以链式表中的每个元素除了要保存数据信息外，还要保存下一个元素的内存地址，以便形成线性关系。

操作

线性表中的操作包含以下类型，顺序表 和 链表 会各自使用不同的方案实现这些操作：

• 初始化 (InitList): 创建一个 空的线性表。
• 插入 (Insert): 在线性表的 指定位置 插入一个 新的元素。
• 删除 (Delete): 删除线性表中的 指定位置的元素。
• 查找 (LocateElem): 根据 给定的条件 查找线性表中的 元素。
• 获取元素 (GetElem): 获取线性表中 指定位置的元素。
• 设置元素 (SetElem): 修改线性表中 指定位置的元素 的 值。
• 长度 (Length): 返回线性表中的 元素数量。
• 判空 (IsEmpty): 判断线性表是否 为空。
• 清空 (ClearList): 清除线性表中的 所有元素。
• 遍历 (Traverse): 对线性表中的 每个元素 执行 某种操作。

2.2 - 顺序表示

顺序表定义

顺序表（Sequential List） 是一种常见的数据结构，用于存储一组元素，并按照它们在内存中的物理顺序来排列和访问这些元素。顺序表通常由一个 数组 或 列表 构成，其中每个元素都占据一个连续的内存位置，并且可以通过索引值来访问。

假设线性表 A 存储的其实位置为 LOC(A)，每个元素占用的存储空间的大小为 sizeof(Elem)，则 A 所对应的顺序存储结构为：

• 顺序表 优点：
  • 随机访问性强：顺序表支持通过索引直接访问元素，访问速度快，时间复杂度为 O(1)。
  • 空间使用连续：顺序表中的元素存储在连续的内存块中，这有助于提高缓存的局部性，从而提高访问速度。
  • 操作简单：无需处理复杂的指针操作。
• 顺序表 缺点：
  • 固定大小或调整大小的开销：对于静态数组，大小是固定的，如果预分配的空间不足或过大，会导致内存浪费或数组溢出。动态数组可以重新分配大小，但这会增加时间和空间开销。
  • 插入和删除的时间开销：如果要在顺序表的中间插入或删除元素，可能需要移动大量的元素，时间复杂度为 O(n)。

操作

数据结构定义

以下代码定义了一个顺序表 SeqList，它使用 固定大小的数组 data 来存储元素，length 记录当前表的长度。InitList 函数初始化顺序表，设置 长度为 0，表示空表。

#define MAXSIZE 100
typedef struct {
    ElementType data[MAXSIZE];
    int length;
} SeqList;

void InitList(SeqList *L) {
    L->length = 0;
}

插入

在第 pos 个位置 插入新元素 e。首先检查 插入位置合法性 和 空间是否已满，然后从尾部向后移动元素，为插入留出位置，最后将元素插入并更新长度。

bool Insert(SeqList *L, int pos, ElementType e) {
    if (L->length == MAXSIZE || pos < 1 || pos > L->length + 1) {
        return false;
    }
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = e;
    L->length++;
    return true;
}

删除

删除第 pos 个元素，并通过指针返回删除的元素值。删除后将该位置后的所有元素 前移，最后更新长度。

bool Delete(SeqList *L, int pos, ElementType *e) {
    if (pos < 1 || pos > L->length) {
        return false;
    }
    *e = L->data[pos - 1];
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;
    return true;
}

查找操作

在线性表中 顺序查找 第一个值等于 e 的元素，返回其逻辑位置（从 1 开始）；若未找到，返回 0。

int LocateElem(SeqList L, ElementType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}

获取元素

获取顺序表中第 pos 个元素，返回值通过指针 *e 输出。若位置非法则返回 false。

bool GetElem(SeqList L, int pos, ElementType *e) {
    if (pos < 1 || pos > L.length) {
        return false;
    }
    *e = L.data[pos - 1];
    return true;
}

判空

判断顺序表是否为空，直接判断 length 是否为 0。

bool IsEmpty(SeqList L) {
    return L.length == 0;
}

清空

清空顺序表，只需将 length 置 0，无需实际删除元素，等价于逻辑上的清空。

void ClearList(SeqList *L) {
    L->length = 0;
}

长度

返回当前顺序表的长度，即有效元素个数。

int Length(SeqList L) {
    return L.length;
}

2.3 - 链式表示

单链表定义

线性表的 链式表示 通常指的是使用 链表 来实现线性表。链表 是由一系列 结点 组成的，每个 结点 都包含一个 数据元素 和一个指向下一个 结点 的 指针。这种结构允许我们 动态地插入 和 删除元素，而不需要移动其他元素。

与顺序表不同，单链表中每个 结点 的存储空间都是 动态分配 的，即使用 c 语言中的 malloc() 函数或者 c++ 中的 new 操作符。
动态分配 的空间存储在 进程的堆 中，这些 结点 占用的存储空间不是连续的，而是离散的，如下图所示：

由于堆的这种 动态内存分配 特性，单链表 具备如下优点：

• 链表大小可以动态变化：链表的 结点 是在需要时 动态分配 的，因此在使用过程中不需要提前分配固定大小的存储空间，可以随时 插入 或 删除 结点。
• 插入和删除方便：只要知道了某个 结点 的位置，就可以在 O(1) 的时间复杂度内 插入 或 删除 该 结点。而顺序表可能需要移动大量的元素。
• 无需预估数据大小：链表可以灵活地增长，而顺序表需要预先定义一个固定大小，或者使用 动态数组 实现，但重新分配和拷贝的开销可能会很大。

数组（顺序表）与 链表 不同，由于数组一般是直接作为函数的局部变量使用 int a[N] 定义的，所以数组存储在 进程的栈 中，数组中的相邻元素是 连续 地存储在栈上，如下图所示：

由于数组在内存中的存储是 连续 的，这有利于程序的 空间局部性，当访问一个元素时，相邻的元素也会被加载到 CPU 缓存 中，这提高了访问速度。
此外，通过数组的起始地址和一个偏移，我们可以快速地定位到某个数组元素在内存中的地址，实现 随机访问。

相比而言，链表 则不具备以上特性，链表 的缺点如下：

• 随机访问较慢：链表 不支持直接通过索引进行 随机访问，必须从头部开始逐个遍历 结点，直到找到所需的 结点，所以访问 链表 中的元素需要 O(n) 的时间复杂度。
• 空间开销较大：除了 数据元素 的存储外，每个 结点 还需要额外的空间存储一个 指针，这增加了 链表 的存储开销。

操作

链表 的操作经常考察，需要熟练掌握，并且能够手写代码。

数据结构定义

可以使用如下结构体来描述 单链表 中的 结点：

// 链表定义
typedef struct Node {
    int data;
    struct Node *next;
} Node;

其中结构体中包含两个元素，一个是 数据，另一个 指向下一个结点的指针。
通过这种方式，链表 可以在内存中以非连续的方式存储数据，每个 结点 通过 指针 连接起来。

在这个例子中，data 的类型是 int，意味着这个 链表 用于存储整数。但是，你可以根据需要更改 data 的类型，例如 float、char 或者自定义的结构体类型，以存储不同类型的数据。

next 指针的作用是 连接链表中的各个结点。它存储了下一个结点的内存地址。通过 next 指针，我们可以从一个结点访问到下一个结点，从而遍历整个链表。

初始化链表

在 初始化 链表时我们需要为其创建一个 头结点，并将 头结点 的 next 设置为空。

// 初始化
Node* init_linkedlist() {
    Node *head = (Node *)malloc(sizeof(Node));  // 创建头结点
    if (head == NULL) exit(1);  // 内存分配失败
    head->next = NULL;  // 初始为空链表
    return head;
}

头结点 的目的在于 简化空链表的处理 和 统一链表的操作：

• 引入 头结点 后，即使链表为空，头指针 也始终指向 头结点。
• 通过引入 头结点，可以使链表的第一个 结点（实际数据 结点）的操作与其他 结点 的操作保持一致。

判空

如果 头指针 的 next 为空的话，说明 单链表 为空：

bool is_empty(Node *head) {
    return head->next == NULL;
}

插入

对于在 链表 的一个 结点 p 之后插入一个新 结点 n 可以抽象如下操作：

• 插入结点
• 插入值

void insert_node_after(Node *p, Node *n) {
    Node *q = p->next;
    n->next = q;
    p->next = n;
}

void insert_value_after(Node *n, int value) {
    Node *p = malloc(sizeof(Node));
    p->value = value;
    Node *q = n->next;
    n->next = p;
    p->next = q;
}

当然，如果我们想插入一个实际值 value 的话，你需要通过 Node *p = malloc(sizeof(Node)); p->data = value; 来创建一个新 结点，然后再将新创建的 结点 通过以上函数插入。

在实际考察 插入 操作的过程中，可能会涉及到三种情况：在 链表 头部插入、在 链表 尾部插入 或 在任意位置插入。

• 头部插入
• 尾部插入
• 任意位置

void insert_after_head(Node *head, int value) {
    // 调用上文定义的插入函数
    insert_value_after(head, value);
}

void insert_after_tail(Node *head, int value) {
    // 找到链表的尾部结点
    Node *tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    // 在该位置插入
    insert_value_after(tail, value);
}

// 在链表的第 pos 个位置插入（位置从 0 开始计数），返回值 bool 表示插入是否成功
bool insert_at_pos(Node *head, int pos, int value) {
    Node *p = head;
    int i = 0;
    // 找到第 pos-1 个结点
    while (p && i < pos - 1) { 
        p = p->next;
        i++;
    }
    // 如果该位置不存在的话，返回 false
    if (!p || i > pos - 1) return false;

    insert_value_after(p, value);
    return true;
}

删除

假设指针 p 指向 链表 中的某个 结点，如果我们想删除 p 的下一个 结点 的话，可以通过如下代码：

void delete_node_after(Node *p) {
    Node *q = p->next;
    // 需要判断 q 是否存在
    if (q) {
        // 设置 p 的下一个结点跳过 q
        p->next = q->next;
        // 释放 q 的空间
        free(q);
    }
}

如果我们想删除 单链表 中的第 pos 个 结点 的话，可以通过如下代码：

// 返回 true 表示删除成功，返回 false 表示删除失败。
bool delete(Node *head, int pos) {
    Node *p = head;
    int i = 0;
    while (p->next && i < pos - 1) {  // 找到第 pos-1 个结点
        p = p->next;
        i++;
    }
    // 如果 p 是链表中最后一个结点，或者 pos-1 的结点不存在的话，返回 false
    if (!(p->next) || i > pos - 1) return false;

    // 删除下一个结点
    Node *q = p->next;
    p->next = q->next;
    free(q);
    return true;
}

查找

如果要查找 链表 中是否有 结点 存储有 value 的值的话，可以通过如下函数：

// 返回 0 表示未找到
int Find(Node *head, int value) {
    Node *p = head->next;
    int i = 1;
    // 遍历链表判断是否有结点值域 value 相同
    while (p) {
        if (p->data == value) return i;
        p = p->next;
        i++;
    }
    return 0;
}

清空

清空 链表 需要删除 链表 中的每一个 结点，并且将 链表 设置为空，可以通过如下函数：

void ClearList(Node *head) {
    Node *p = head->next, *q;
    head->next = NULL;
    // 遍历每个结点，并且 free 结点
    while (p) {
        q = p->next; // 暂存下一个结点
        free(p);
        p = q;
    }
}

其他链式实现

双向链表

在 双向链表 中，每个节点包含三个部分：数据、前驱指针 prev、后继指针 next。

typedef struct DNode {
    ElementType data;
    struct DNode *prev;  // 指向前驱节点
    struct DNode *next;  // 指向后继节点
} DNode;

双向链表 主要具备以下优势：

• 可以 双向遍历，支持从任意节点向前或向后查找。
• 插入和删除 某个节点时，不需要再查找其前一个节点（与单链表相比更方便）。

插入操作

假设插入 s 到 p 前：

原来：
... ⟷ pre ⟷ p ⟷ ...

插入后：
... ⟷ pre ⟷ s ⟷ p ⟷ ...

具体操作步骤如下：

// 假设 p 是链表中的某个节点，s 是新建节点
s->prev = p->prev;      // 步骤①：新节点 s 的前驱是 p 的前驱
s->next = p;            // 步骤②：新节点 s 的后继是 p
p->prev->next = s;      // 步骤③：p 原前驱节点的 next 改为 s
p->prev = s;            // 步骤④：p 的前驱改为 s

删除操作

假设删除节点 p：

... ⟷ prev ⟷ p ⟷ next ⟷ ...
        ↓ 删除 p
... ⟷ prev ⟷ next ⟷ ...

具体操作步骤如下：

p->prev->next = p->next;  // 步骤①：前驱的 next 指向 p 的后继
p->next->prev = p->prev;  // 步骤②：后继的 prev 指向 p 的前驱
free(p);                  // 步骤③：释放 p 节点

静态链表

静态链表 实际上就是用 顺序表（一个结构体数组）来模拟 链表。结构体中包含两个元素：data 和 next，其中 data 存储数据，next 存储下一个元素的下标（相当于指针的作用）：

#define MAXSIZE 100

typedef struct {
    ElementType data;
    int next;
} SNode;

SNode list[MAXSIZE];

静态链表 使用 next == -1 作为其结束的标志。静态链表 的各种操作和 动态链表 基本一致，只需要修改指针，不需要移动元素。

循环链表

循环链表（Circular Linked List）是一种特殊的 链表 结构，其 最后一个节点的指针指向头节点，使得整个 链表 形成一个 环状结构。因此，从任何一个节点开始遍历，只要不断沿着指针走，就一定会回到起点。

循环链表 可分为两种类型：

3 - 线性数据结构

学习思维导图：

# 栈、队列和数组

## 栈和队列基本概念

## 栈和队列的顺序存储结构

## 栈和队列的链式存储结构

## 多维数组的存储

## 特殊矩阵的压缩矩阵

## 栈、队列和数据的应用

3.1 - 栈

定义

栈 是一个元素的集合，加入元素的操作叫做 “压栈”（push），而移除元素的操作叫做 “出栈”（pop）。它遵循 后进先出（LIFO, Last In First Out） 的原则。这意味着最后被压入栈的元素是第一个被弹出的元素。

基本操作

• push(element): 将元素添加到 栈 的顶部。
• pop(): 移除并返回 栈顶 的元素。如果 栈 为空，这个操作可能会抛出一个错误或返回特定的值（例如 null 或 undefined），具体取决于实现。
• peek() 或 top(): 返回 栈顶 的元素但不移除它。这只是一个查看操作，栈 的内容不会改变。如果 栈 为空，这个操作可能会抛出一个错误或返回特定的值。
• isEmpty(): 判断 栈 是否为空。如果 栈 为空，返回 true；否则返回 false。
• size() 或 length(): 返回 栈 中元素的数量。

实现

栈 的实现方式有两种，顺序栈 和 链式栈。
顺序栈 是在 顺序表 的基础上实现 栈结构，
链式栈 是在 链表 的基础上实现 栈结构。

顺序栈

顺序栈是使用 数组 来实现的 栈，利用数组的索引来模拟 栈 的操作。
与普通的线性表不同，栈 的操作被限制在表的一端进行，这一端被称为 栈顶 (Top)，另一端被称为 栈底 (Bottom)。

顺序栈的关键在于 栈顶指针，栈顶指针是一个整数变量，用于指示 栈顶 元素在 数组 中的位置。其值的变化直接反映了栈中元素的变化。

当 栈空 时，一般将 栈顶指针设置为 1，当 栈满 时，栈顶指针指向 数组 中的最后一个元素。

当元素 入栈 时，将栈顶指针 向后 移动一个位置、然后放置新元素即可。当元素 出栈 时，需要将栈顶指针 向前 移动一个位置。

当然，入栈需要保证栈不满，出栈需要保证栈不空。

• 栈的定义
• 初始化
• 入栈
• 出栈
• 获取栈顶元素
• 判断栈空

#define MAX_SIZE 100 // 定义栈的最大容量

// 定义顺序栈的结构
typedef struct {
    int data[MAX_SIZE]; // 使用数组存储数据
    int top;            // 栈顶指针
} SeqStack;

// 初始化栈
SeqStack* initStack() {
    SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
    if(!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    // 栈顶指针初始化为 -1，表示栈为空
    stack->top = -1; 
    return stack;
}

// 入栈操作
bool push(SeqStack* stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full!\n");
        return false;
    }
    // 先移动栈顶指针，再存放元素
    stack->data[++stack->top] = value;
    return true;
}

// 出栈操作
bool pop(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    // 先取出元素，再移动栈顶指针
    *value = stack->data[stack->top--];
    return true;
}

// 获取栈顶元素
bool peek(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->data[stack->top];
    return true;
}

// 判断栈是否为空
// 当栈中没有元素时，栈顶指针通常指向一个特殊的位置，例如 -1。
bool isEmpty(SeqStack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
// 当栈顶指针指向数组中的最后一个元素时，说明栈已经满了
bool isFull(SeqStack* stack) {
    return stack->top == MAX_SIZE - 1;
}

链式栈

栈的 链式存储结构 利用 单链表 来实现栈的功能。

在 链式栈 实现中，一般 头结点不存放数据，仅作为链表的固定起点。栈顶元素始终为 head->next。这样依然可以保证 入栈 和 出栈 的时间复杂度为 $O(1)$ 。

链式栈具备以下 重要特性：

• head 始终存在，不存储实际数据，只作为哨兵节点。
• 栈顶元素 始终位于 head->next。
• 空栈 时，head->next == NULL。
• 入栈时在 head->next 前插入新节点；出栈时删除 head->next。

• 栈的定义
• 初始化
• 入栈
• 出栈
• 获取栈顶元素
• 判断栈空

// 定义链式栈的节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;

// 定义链式栈（带头结点）
typedef struct {
Node* head;  // 指向头结点
} LinkedStack;

// 初始化栈（带头结点）
LinkedStack* initStack() {
    LinkedStack* stack = (LinkedStack*)malloc(sizeof(LinkedStack));
    if (!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    stack->head = (Node*)malloc(sizeof(Node)); // 创建头结点
    if (!stack->head) {
        printf("Failed to allocate memory for head node\n");
        exit(1);
    }
    stack->head->next = NULL; // 初始为空栈
    return stack;
}

// 入栈操作（头插法）
void push(LinkedStack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Failed to allocate memory for new node\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = stack->head->next;
    stack->head->next = newNode;
}

// 出栈操作
bool pop(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    Node* topNode = stack->head->next;
    *value = topNode->data;
    stack->head->next = topNode->next;
    free(topNode);
    return true;
}

// 获取栈顶元素
bool peek(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->head->next->data;
    return true;
}

// 判断栈是否为空
bool isEmpty(LinkedStack* stack) {
    return stack->head->next == NULL;
}

3.2 - 队列

定义

队列是一种遵循 先入先出 (FIFO, First In First Out) 原则的线性数据结构。元素在 队尾 添加，在 队首 删除。

基本操作

• enqueue(element): 将元素添加到 队列 的尾部。
• dequeue(): 从 队列 的头部移除并返回元素。如果 队列 为空，此操作可能会返回特定的值或引发错误。
• front() 或 peek(): 返回 队首 的元素但不移除它。
• isEmpty(): 判断 队列 是否为空。
• size(): 返回 队列 中元素的数量。

实现

顺序队列

顺序队列通常是指使用固定大小的数组来存储 队列 中的元素。在顺序队列中，通常有两个指标：一个是 队头（front），另一个是 队尾（rear）。当插入（入队）或删除（出队）元素时，这两个指标会移动。

顺序队列有一个明显的问题：随着时间的推移，队列 中的元素可能向数组的末尾移动，即使 队列 并不满，也可能无法再插入新的元素，因为 队尾 已经达到了数组的末尾。这种现象称为 假溢出。

循环队列

为了解决上述问题，可以使用 循环队列（也称为环形队列）。循环队列 是顺序队列的一个变种，它把数组视为一个循环的结构。当 队尾 指标达到数组的最后一个位置并且还需要进一步移动时，它会回到数组的起始位置。

需要注意的是，在 循环队列 中需要牺牲一个存储单元以区分 队空 和 队满 的情况。

• 当 front == rear 时，队列为空
• 当 (rear + 1) % size == front 时，队列为满

• 定义
• 入队
• 出队
• 首尾元素
• 判断队列空或满

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} CircularQueue;

// 初始化队列
void initQueue(CircularQueue* q) {
    q->front = q->rear = 0;
}

// 入队操作
bool enqueue(CircularQueue* q, int value) {
    if (isFull(q)) return false;
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}

// 出队操作
bool dequeue(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return true;
}