数据结构

1 说说一个算法有哪些时间复杂度？归并算法时间复杂度是多少？⭐⭐⭐⭐⭐

一个算法的时间复杂度通常包括以下常见类型及对应典型算法示例‌：

‌O(1)‌

常数时间复杂度

示例：数组随机访问、绝对值计算（如 abs(x)）

‌O(n)‌

线性时间复杂度

示例：线性查找、计数排序、基数排序

‌O(n²)‌

平方时间复杂度

示例：冒泡排序、插入排序、选择排序

‌O(logn)‌

对数时间复杂度

示例：二分查找、最大公约数计算（如 __gcd(a,b)）

‌O(n logn)‌

线性对数时间复杂度

示例：快速排序（平均情况）、归并排序、堆排序

‌O(2ⁿ)‌

指数时间复杂度

示例：穷举法解决子集问题

‌归并排序的时间复杂度‌为 ‌O(n logn)‌，具体分析如下‌：

• 分治策略‌：归并排序将数组递归拆分为两半，拆分次数为 log₂n 层。
• ‌合并操作‌：每层合并需要 O(n) 时间遍历所有元素。
• ‌总复杂度‌：O(n) × O(logn) = O(n logn)。

其时间复杂度在所有情况下（最好/平均/最坏）均保持稳定，是高效且稳定的排序算法。

2 说说数组时间复杂度，什么场景下使用？⭐⭐⭐

一、数组的时间复杂度分析

数组作为线性数据结构，其时间复杂度主要取决于操作类型：

‌随机访问‌：通过下标直接访问元素，时间复杂度为 ‌O(1)‌（如 array[i]）‌。

‌插入/删除‌：

在数组末尾操作，时间复杂度为 ‌O(1)‌（如动态扩容前的追加操作）‌。

在中间或开头操作，需移动后续元素，时间复杂度为 ‌O(n)‌（如插入到第k个位置）‌。

‌遍历操作‌：遍历所有元素的时间复杂度为 ‌O(n)‌‌。

二、数组的适用场景

数组因其内存连续、访问高效的特点，适用于以下场景：

‌存储固定大小的数据集合‌

如存储学生成绩、用户信息等已知数量的同类型数据‌。

示例：Java中静态初始化 int[] scores = {90, 85, 78};‌。

‌需要高频随机访问的场景‌

如算法中的二分查找、快速排序等依赖下标快速定位的场景‌。

示例：Arrays.binarySearch() 实现依赖于数组的随机访问特性‌。

‌多维数据表示‌

如矩阵运算、图像像素存储等需要多维结构的场景‌。

示例：二维数组表示棋盘 int[][] chessBoard = new int;‌。

‌缓存优化与性能敏感场景‌

内存连续特性可提高CPU缓存命中率，适用于底层开发（如网络框架）‌。

‌批量数据操作‌

如遍历统计、批量修改等需要顺序访问的场景（如计算平均分）‌。

三、总结

数组在‌随机访问性能强、数据规模固定、内存连续‌的场景下表现优异，但插入/删除效率低且扩容成本高‌。实际开发中需根据需求权衡其优缺点，例如在需要动态扩容时，可结合链表或 ArrayList 使用。

3 说说vector的实现原理⭐⭐⭐⭐

vector 是 C++ 标准模板库（STL）中的一个容器，它实现了动态数组的功能。以下是 vector 的实现原理的详细介绍：

数据存储

vector 内部使用一块连续的内存空间来存储元素。这就像在内存中开辟了一段连续的 “线性空间”，元素按照顺序依次存放，这种连续存储的方式使得 vector 可以像数组一样通过下标快速访问元素，时间复杂度为 O (1)。

动态增长机制

vector 能够根据需要动态地调整自身的大小。当向 vector 中插入元素时，如果当前的内存空间已满，vector 会自动分配一块更大的内存空间，通常是当前容量的两倍，然后将原来的元素复制到新的内存空间中，最后释放原来的内存空间。

以一个初始容量为 5 的 vector 为例，当插入第 6 个元素时，vector 会分配一块容量为 10 的新内存空间，将前 5 个元素复制到新空间，再插入第 6 个元素，然后释放原来容量为 5 的内存空间。

迭代器

vector 提供了迭代器来访问和遍历容器中的元素。迭代器在 vector 中的工作原理类似于指针，它可以指向 vector 中的某个元素，通过迭代器的移动操作，可以顺序访问 vector 中的每个元素。

可以使用 begin () 函数获取指向 vector 第一个元素的迭代器，使用 end () 函数获取指向 vector 最后一个元素的下一个位置的迭代器。

元素插入和删除

插入操作：当在 vector 的任意位置插入元素时，需要将插入位置之后的元素依次向后移动，为新元素腾出空间，然后将新元素插入到指定位置。如果插入位置是 vector 的末尾，直接将元素插入到末尾即可，时间复杂度通常为 O (1)；但如果是在 vector 的开头或中间插入元素，时间复杂度为 O (n)，n 为 vector 中元素的个数。

删除操作：删除 vector 中的元素时，需要将删除位置之后的元素依次向前移动，填补被删除元素的位置，以保持内存的连续性。同样，如果删除的是 vector 的末尾元素，时间复杂度为 O (1)；如果删除的是开头或中间的元素，时间复杂度为 O (n)。

内存管理

vector 负责管理自己的内存空间，在创建 vector 对象时，会根据初始容量分配一定大小的内存空间。当 vector 对象被销毁时，会自动释放其所占用的内存空间，防止内存泄漏。

在 vector 的大小发生变化时，它会合理地申请和释放内存，以确保在满足存储需求的同时，尽可能地提高内存的使用效率。

4 总结一下数组与链表的区别⭐⭐⭐⭐

存储结构：数组是连续存储，链表是节点式的非连续存储。

访问方式：数组可通过下标随机访问，时间复杂度为 O (1)；链表需顺序访问，时间复杂度为 O (n)。

插入删除操作：数组在中间或头部插入删除需移动大量元素，时间复杂度为 O (n)；链表只需修改指针，时间复杂度一般为 O (1)。

内存分配：数组静态分配内存，大小固定；链表动态分配内存，大小可灵活变化。

5 栈和队列的区别⭐⭐⭐⭐

栈和队列的区别主要体现在：

数据进出原则：栈遵循后进先出（LIFO）原则，如同弹夹，最后压入的子弹最先弹出；队列遵循先进先出（FIFO）原则，类似排队，先到的先处理。

操作方式：栈的插入和删除操作都在栈顶进行；队列的插入在队尾，删除在队头。

应用场景：栈常用于函数调用、表达式求值等；队列常用于任务调度、缓存管理等。

6 说说二叉堆⭐⭐⭐

二叉堆是一种基于完全二叉树的数据结构，常用于实现优先队列。以下是关于二叉堆的详细说明：

一、核心概念

1. 定义完全二叉树：除最后一层外，其他层节点填满，且最后一层节点从左到右排列。堆性质：最大堆：每个节点的值 ≥ 其子节点的值。最小堆：每个节点的值 ≤ 其子节点的值。
2. 存储方式使用数组存储，无需额外指针。节点 i 的子节点为 2i+1（左）和 2i+2（右），父节点为 (i-1)/2。

二、关键操作

1. 插入（以最小堆为例）将元素添加到数组末尾。向上调整（Shift Up）：若新元素小于父节点，与父节点交换，重复直到满足堆性质。
2. 删除（以最小堆为例）删除根节点（最小值）。用最后一个元素填补根节点位置。向下调整（Shift Down）：若当前节点大于子节点，与较小子节点交换，重复直到满足堆性质。
3. 堆化（Heapify）将普通数组转换为堆结构。从最后一个非叶子节点开始，逐个节点向下调整。

三、应用场景

1. 优先队列：快速获取最大 / 最小值。
2. 堆排序：通过堆结构实现高效排序。
3. 图算法：如 Dijkstra 算法（求最短路径）。
4. 找第 K 大 / 小元素：用堆优化时间复杂度。

7 说说哈希表⭐⭐⭐

哈希表（Hash Table）是一种通过哈希函数实现快速查找、插入和删除的数据结构，其核心思想是将键映射到存储位置。以下是关于哈希表的详细说明：

一、核心概念

1. 定义哈希表由 键值对（Key-Value） 组成，通过哈希函数将键转换为存储索引（哈希值）。理想情况下，每个键对应唯一索引，操作时间复杂度为 O(1)。
2. 哈希函数将任意长度的键映射为固定范围的整数（哈希值）。要求：计算高效、分布均匀（减少冲突）。
3. 冲突处理链地址法（Separate Chaining）：冲突时将相同哈希值的键值对存入链表或数组。开放寻址法（Open Addressing）：冲突时寻找下一个可用位置（如线性探测、二次探测）。

二、工作原理

1. 插入操作计算键的哈希值，确定存储位置。若位置被占用，根据冲突处理策略解决（如链地址法添加到链表）。
2. 查找操作计算键的哈希值，直接定位存储位置。遍历链表（链地址法）或探测相邻位置（开放寻址法）匹配目标键。
3. 删除操作需标记已删除节点（开放寻址法）或从链表中移除（链地址法）。

8 说说堆排序的时间复杂度，建堆的时间复杂度⭐⭐⭐⭐

堆排序的时间复杂度为 O(n log n)，而建堆的时间复杂度为 O(n)。以下是详细分析：

一、堆排序的时间复杂度

堆排序分为两个阶段：

1. 建堆阶段：将数组调整为最大堆（或最小堆），时间复杂度为 O(n)。
2. 排序阶段：每次取出堆顶元素（最大值），并将剩余元素重新调整为堆，共执行 n-1 次，每次调整时间复杂度为 O(log n)。因此，排序阶段总时间复杂度为 O(n log n)。

综上，堆排序的总时间复杂度为 O(n log n)。

二、建堆的时间复杂度（O (n)）

建堆通常采用 自底向上的下沉（sift-down） 操作：

1. 步骤：从最后一个非叶子节点开始（位置为 n/2 - 1），依次对每个节点执行下沉操作，确保以该节点为根的子树满足堆的性质。
2. 数学证明：对于完全二叉树，每个节点的下沉次数等于其高度（即该节点到叶子节点的路径长度）。总共有 n/2 个非叶子节点，每个节点的下沉次数为 O(log n)。但实际总和为 O(n)，因为每个层级的节点数与该层级的高度相乘的总和为线性关系。例如：叶子节点（第 h 层）无需调整。倒数第二层（第 h-1 层）每个节点最多下沉 1 次，共有 2^{h-1} 个节点，总操作次数为 2^{h-1} × 1。倒数第三层（第 h-2 层）每个节点最多下沉 2 次，共有 2^{h-2} 个节点，总操作次数为 2^{h-2} × 2。以此类推，总和为 2^{h-1} × 1 + 2^{h-2} × 2 + ... + 2^0 × h，最终结果为 O(n)。

9 哈希表如何解决哈希冲突⭐⭐⭐⭐

哈希表解决哈希冲突主要有以下方法：

开放寻址法：当冲突发生时，通过探测函数在哈希表中寻找下一个空位置来存储数据。

链地址法：将所有哈希值相同的元素存储在一个链表中，哈希表每个位置存储链表头指针。

再哈希法：使用多个哈希函数，当第一个哈希函数产生冲突时，用下一个哈希函数计算地址。

建立公共溢出区：专门开辟一个溢出区，存储冲突的数据。

10 哈希表的初始数组容量一般为多少，为什么？⭐⭐⭐⭐

哈希表的初始数组容量通常选择2 的幂次（如 16、32、64 等），而非任意数值或质数。这一设计决策主要基于以下原因：

一、初始容量选择 2 的幂次的原因

1. 高效哈希计算

• 位运算优化：现代哈希表（如 Java 的HashMap、C++ 的unordered_map）普遍通过位运算替代取模运算来确定索引。例如，索引计算为 hash & (capacity - 1)，当容量为 2 的幂时，capacity - 1 是全 1 的二进制数（如 16→15→0b1111），能最大化哈希值的低位分布，减少冲突。
• 避免除法开销：取模运算（hash % capacity）涉及除法，在 CPU 中效率低于位运算。

2. 扩容策略的连贯性

• 倍增扩容：哈希表扩容时通常将容量翻倍（如 16→32→64），保持容量为 2 的幂次。扩容后，只需重新计算哈希值的高位即可确定新索引（无需重新哈希所有元素），降低扩容成本。

3. 内存对齐与性能

• 2 的幂次便于内存分配和对齐，减少碎片化，提升缓存利用率。

二、为何不选择质数？

虽然质数在某些哈希函数（如取模法）中可减少冲突，但现代哈希表设计已通过以下方式优化：

1. 哈希函数的优化如 FNV 哈希、MurmurHash 等算法本身已能将键均匀分布，削弱了质数对冲突的影响。
2. 动态扩容机制哈希表通过负载因子（如默认 0.75）触发扩容，而非依赖初始容量的质数特性。

三、典型编程语言的初始容量

11 哈希表的负载因子为什么是0.75？⭐⭐⭐

哈希表的负载因子（Load Factor）是哈希表中已存储元素数量与哈希表容量的比值。常见的默认负载因子为 0.75，这一选择是时间与空间效率的折中，具体原因如下：

一、冲突与性能的平衡

哈希表的核心问题是哈希冲突（不同键映射到同一位置）。负载因子过高时：

• 每个桶（Bucket）的链表或红黑树会变长，导致查找、插入、删除的时间复杂度上升。
• 例如，当负载因子为 1.0 时，每个桶平均有 1 个元素，但实际分布可能不均匀，导致某些桶的链表很长。

负载因子过低时：

• 哈希表的空间利用率低，浪费内存。

0.75 的选择：

• 经过数学分析和实际测试，当负载因子为 0.75 时，链式哈希表（如 Java 的 HashMap）的平均链表长度约为 0.75，此时冲突概率较低，且空间利用率较高。

二、动态扩容的成本

哈希表通常采用动态扩容策略：当元素数量超过 负载因子 × 容量 时，触发扩容（容量翻倍并重新哈希）。扩容的代价是 O (n) 时间复杂度。

0.75 的优势：

• 避免频繁扩容：若负载因子设为 1.0，扩容频率降低，但每次扩容需处理更多元素。
• 减少扩容触发次数：负载因子设为 0.75 时，扩容触发的频率与单次扩容的成本达到平衡。

12 什么是平衡树？⭐⭐⭐

平衡树（Balanced Tree）是一种自平衡的二叉搜索树（BST），通过调整节点位置和结构，确保树的高度在合理范围内，从而将操作的时间复杂度稳定控制在 O(log n)。其核心目标是避免普通二叉搜索树在极端情况下退化为链表，导致性能下降。

一、平衡树的核心特性

1. 平衡条件：左右子树的高度差不超过某个阈值（如 AVL 树要求高度差≤1）。通过旋转（Rotation）操作维持平衡。
2. 时间复杂度：搜索、插入、删除均为 O(log n)。
3. 常见类型：AVL 树、红黑树、B 树、B + 树、Splay Tree 等。

二、主流平衡树对比

13 说说红黑树⭐⭐⭐⭐

红黑树是一种自平衡二叉查找树，具有以下特点：

• 节点颜色非红即黑，根节点为黑色，叶节点（外部节点）为黑色。
• 每个红色节点的两个子节点都是黑色，从任一节点到其每个叶子节点的所有路径上都包含相同数目的黑色节点。
• 这些特性保证了红黑树的高度平衡，其插入、删除、查找操作的时间复杂度均为，在数据结构和算法领域应用广泛，如 Java 的 TreeMap等。

14 说说什么是稳定的排序？⭐⭐⭐

稳定排序（Stable Sort）是指在排序过程中，相同元素的相对顺序保持不变的排序算法。例如，对序列 [2a, 3, 2b] 进行稳定排序后，2a 仍会在 2b 之前。

一、核心特性

1. 相同元素顺序不变：若两个元素的值相等，排序后它们的相对顺序与排序前一致。例如：排序前 A 在 B 前面，排序后 A 仍在 B 前面。
2. 适用场景：当排序键相同但需要保留原有顺序时（如多条件排序、保留优先级）。例如：学生成绩排序，总分相同的学生需保持原有名次。

二、稳定排序算法

以下是常见的稳定排序算法：

15 说说动态规划算法⭐⭐⭐⭐

动态规划（Dynamic Programming，简称 DP）是一种通过把原问题分解为相对简单的子问题，并保存子问题的解来避免重复计算，从而解决复杂问题的算法策略。以下从多个方面详细介绍动态规划算法：

核心思想

动态规划的核心思想在于 “分治” 与 “最优子结构”。它将一个复杂的问题分解为一系列相互关联的子问题，通过求解子问题并保存其解，避免对相同子问题的重复计算，以此提高算法效率。具体来说，该算法具备以下两个关键特性：

• 最优子结构：问题的最优解包含其子问题的最优解。也就是说，可以通过子问题的最优解推导出原问题的最优解。
• 重叠子问题：在求解过程中，会多次遇到相同的子问题。动态规划利用这一特性，将子问题的解存储起来，避免重复计算。

解题步骤

运用动态规划算法解决问题时，一般可遵循以下步骤：

1. 定义状态：明确问题的状态表示，即找到一个合适的方式来描述子问题。通常用一个或多个变量来表示状态，状态的定义要能够准确反映问题的特征和子问题之间的关系。
2. 确定状态转移方程：根据问题的最优子结构性质，找出状态之间的转移关系。状态转移方程描述了如何从已知的子问题解推导出当前问题的解，它是动态规划算法的核心。
3. 初始化边界条件：确定问题的边界情况，即最小子问题的解。这些边界条件是状态转移的起点，没有它们就无法进行后续的递推计算。
4. 计算顺序：根据状态转移方程，确定计算的顺序，通常是从边界条件开始，逐步计算出所有子问题的解，最终得到原问题的解。

16 快排最差时间复杂度，堆排最差时间复杂度？⭐⭐⭐⭐

快排平均时间复杂度为O(nlogn)。而被排序的数组刚好是倒序的情况下，最差时间复杂度为O(n^2)

建堆的时间复杂度为O(n)。堆排平均时间复杂度为O(nlogn)。最差时间复杂度为O(nlogn)，也即每个结点都进行了一次比较。

17 说说各排序算法的时间复杂度？⭐⭐⭐⭐⭐

常见排序算法的时间复杂度如下表所示：

其中，n为数据规模，k为数据范围，d为最大位数，r为基数。

基础算法

1 实现一个vector⭐⭐⭐⭐

#include <iostream>
#include <stdexcept>

template <typename T>
class MyVector {
private:
    T* data;  // 指向动态分配数组的指针
    size_t size_;  // 当前元素的数量
    size_t capacity_;  // 当前数组的容量

    // 重新分配内存，扩大容量
    void reserve(size_t newCapacity) {
        if (newCapacity <= capacity_) return;

        T* newData = new T[newCapacity];
        for (size_t i = 0; i < size_; ++i) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity_ = newCapacity;
    }

public:
    // 默认构造函数
    MyVector() : data(nullptr), size_(0), capacity_(0) {}

    // 析构函数
    ~MyVector() {
        delete[] data;
    }

    // 获取当前元素的数量
    size_t size() const {
        return size_;
    }

    // 获取当前数组的容量
    size_t capacity() const {
        return capacity_;
    }

    // 判断向量是否为空
    bool empty() const {
        return size_ == 0;
    }

    // 在向量末尾添加一个元素
    void push_back(const T& value) {
        if (size_ == capacity_) {
            if (capacity_ == 0) {
                reserve(1);
            } else {
                reserve(2 * capacity_);
            }
        }
        data[size_++] = value;
    }

    // 移除向量末尾的元素
    void pop_back() {
        if (size_ > 0) {
            --size_;
        }
    }

    // 访问指定位置的元素
    T& operator[](size_t index) {
        if (index >= size_) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }

    const T& operator[](size_t index) const {
        if (index >= size_) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }
};

// 测试代码
int main() {
    MyVector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;

    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;

    vec.pop_back();
    std::cout << "Size after pop_back: " << vec.size() << std::endl;

    return 0;
}

2 来手写一个链表⭐⭐⭐⭐

#include <iostream>

// 定义链表节点类
template <typename T>
class Node {
public:
    T data;         // 节点存储的数据
    Node<T>* next;  // 指向下一个节点的指针

    // 构造函数
    Node(T value) : data(value), next(nullptr) {}
};

// 定义链表类
template <typename T>
class LinkedList {
private:
    Node<T>* head;  // 链表头指针

public:
    // 构造函数，初始化头指针为 nullptr
    LinkedList() : head(nullptr) {}

    // 析构函数，释放链表中所有节点的内存
    ~LinkedList() {
        while (head != nullptr) {
            Node<T>* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // 在链表头部插入一个新节点
    void insertAtHead(T value) {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = head;
        head = newNode;
    }

    // 在链表尾部插入一个新节点
    void insertAtTail(T value) {
        Node<T>* newNode = new Node<T>(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node<T>* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // 删除链表头部节点
    void deleteAtHead() {
        if (head == nullptr) {
            return;
        }
        Node<T>* temp = head;
        head = head->next;
        delete temp;
    }

    // 删除链表尾部节点
    void deleteAtTail() {
        if (head == nullptr) {
            return;
        }
        if (head->next == nullptr) {
            delete head;
            head = nullptr;
            return;
        }
        Node<T>* temp = head;
        while (temp->next->next != nullptr) {
            temp = temp->next;
        }
        delete temp->next;
        temp->next = nullptr;
    }

    // 打印链表中的所有元素
    void printList() {
        Node<T>* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    LinkedList<int> list;

    // 在链表尾部插入元素
    list.insertAtTail(1);
    list.insertAtTail(2);
    list.insertAtTail(3);

    // 打印链表
    std::cout << "After inserting at tail: ";
    list.printList();

    // 在链表头部插入元素
    list.insertAtHead(0);

    // 打印链表
    std::cout << "After inserting at head: ";
    list.printList();

    // 删除链表头部元素
    list.deleteAtHead();

    // 打印链表
    std::cout << "After deleting at head: ";
    list.printList();

    // 删除链表尾部元素
    list.deleteAtTail();

    // 打印链表
    std::cout << "After deleting at tail: ";
    list.printList();

    return 0;
}

Node 类：定义了链表的节点，包含一个数据成员 data 和一个指向下一个节点的指针 next。

LinkedList 类：

head：链表的头指针，指向链表的第一个节点。

构造函数：初始化头指针为 nullptr。

析构函数：释放链表中所有节点的内存，防止内存泄漏。

insertAtHead：在链表头部插入一个新节点。

insertAtTail：在链表尾部插入一个新节点。

deleteAtHead：删除链表头部节点。

deleteAtTail：删除链表尾部节点。

printList：打印链表中的所有元素。

main 函数：创建一个链表对象，进行插入和删除操作，并打印链表的内容。

通过上述代码，你可以了解如何使用 C++ 实现一个简单的链表，并对链表进行基本的操作。

3 用数组或链表来实现一个栈⭐⭐⭐⭐⭐

实现的原理都是类似的，用游标变量来控制元素的位置。

栈只需要设置一个游标变量来控制栈顶元素的位置

大家一定要掌握，面试很容易手撕代码。

使用数组实现栈

#include <iostream>
#include <stdexcept>

template <typename T, size_t MAX_SIZE>
class ArrayStack {
private:
    T data[MAX_SIZE];
    int topIndex;

public:
    ArrayStack() : topIndex(-1) {}

    // 判断栈是否为空
    bool empty() const {
        return topIndex == -1;
    }

    // 判断栈是否已满
    bool full() const {
        return topIndex == static_cast<int>(MAX_SIZE - 1);
    }

    // 入栈操作
    void push(const T& value) {
        if (full()) {
            throw std::overflow_error("Stack overflow");
        }
        data[++topIndex] = value;
    }

    // 出栈操作
    void pop() {
        if (empty()) {
            throw std::underflow_error("Stack underflow");
        }
        --topIndex;
    }

    // 获取栈顶元素
    T top() const {
        if (empty()) {
            throw std::underflow_error("Stack is empty");
        }
        return data[topIndex];
    }
};


int main() {
    ArrayStack<int, 5> stack;
    try {
        stack.push(1);
        stack.push(2);
        stack.push(3);
        std::cout << "Top element: " << stack.top() << std::endl;
        stack.pop();
        std::cout << "Top element after pop: " << stack.top() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}

ArrayStack 类使用一个固定大小的数组 data 来存储栈中的元素，topIndex 表示栈顶元素的索引。

empty 方法通过检查 topIndex 是否为 -1 来判断栈是否为空。

full 方法通过检查 topIndex 是否达到数组的最大索引来判断栈是否已满。

push 方法在栈未满时将元素添加到栈顶，并更新 topIndex。

pop