# 深入浅出 快速认识JAVA常用数据结构【栈, 队列, 链表, 数组】

快速认识JAVA常用数据结构【栈, 队列, 链表】

前言 什么是数据结构

一种用来存储和组织数据的方法，描述了数据之间的关系和操作方式。通过合理选择和使用数据结构，可以大幅提高程序的运行效率、存储效率以及代码可维护性。

数据结构的重要性

数据结构决定了数据的存储和访问方式。选择合适的数据结构可以：

• 优化性能：降低时间复杂度和空间复杂度。

  • 时间复杂度是什么

    • 代码进入数据结构计算阶段 (算法执行) 的运行时间和 数据规模 的增长关系,
      简单来说就是 随数据规模增长的运行时间

  • 空间复杂度是什么

    • 代码进入数据结构计算阶段 (算法执行) 的运行所需额外内存空间随数据规模的变化关系。
      简单来说就是 随数据规模增长的额外内存空间

• 提高操作效率：快速查找、插入、删除等操作，可以显著提升程序的执行速度。

• 解决复杂问题：数据结构在java中相当于一套为算法逻辑设计的高效 API，提供基础操作（如插入、删除、查找等）来支撑复杂问题的解决。

常见数据结构

1. 栈 (Stack)

• 定义与特性：
  栈是一种遵循 先进后出 原则的线性数据结构。它限制了数据的访问方式，只能在一端（栈顶）进行插入和删除操作，类似“弹匣装子弹”的过程。最后装的子弹最先射出

  • 栈顶：新数据从栈顶进入，称为“进栈”。
  • 栈底：当数据被移除时，从栈顶弹出，称为“弹栈”。

• 应用场景：

  1. 函数调用：栈用于存储函数的调用顺序及其局部变量。

  • 局部变量与栈的关系
    前置知识 : 什么是栈帧
    函数调用时在栈中分配的一块内存区域，用于存储该函数的运行 状态, 和函数信息 (参数, 局部变量, 返回地址, 其他状态… )

    1. 每次函数调用会分配一个栈帧，其中包含该函数的局部变量、参数和返回地址等信息。

    2. 局部变量是在函数的作用域内分配的，生命周期跟随函数的调用过程——调用开始时创建，调用结束后在栈中被释放。

    3. 等待被使用

       • 栈中存储的局部变量和状态，并不直接“运行”，而是为当前函数提供“可用的环境”。
       • 如果当前函数调用另一个函数，当前函数的栈帧会 暂时被挂起（停止运行），直到被调用的函数执行完成后，当前函数暂停状态恢复并继续执行。
  2. 表达式求值 (自行拓展)：用于实现中缀表达式转后缀表达式的计算。

  中缀表达式转后缀表达式 缀 : 运算符

  ​ 像 3 + 4 * 5 就属于中缀表达式, 需要考虑运算符优先级和括号，计算复杂。
  ​ 通过栈，可以把中缀表达式转换成后缀表达式（如 3 4 5 * +），计算更简 单。

  ​ 为什么?

  • 后缀表达式规则：

    • 从左到右扫描，遇到数字就压入栈。

    • 遇到操作符时，从栈中弹出 最近压入的两个数字 进行计算，再将结果压入栈。

  • 计算步骤：

    • 表达式：3 4 5 * +

    • 初始化一个空栈。

    开始计算

    1. 遇到 3，数字，压入栈。
       栈：[3]

    2. 遇到 4，数字，压入栈。
       栈：[3, 4]

    3. 遇到 5，数字，压入栈。
       栈：[3, 4, 5]

    4. 遇到 *，是操作符：

       • 从栈中弹出 5 和 4，计算 4 * 5 = 20。

       • 将结果 20 压入栈。
         栈：[3, 20]

    5. 遇到 +，是操作符：

       • 从栈中弹出 20 和 3，计算 3 + 20 = 23。

       • 将结果 23 压入栈。
         栈：[23]

  3. 浏览器回退与前进：通过两个栈实现页面的前进和后退功能。

• **图示 **:

  栈结构图解：

  ┌─────────┐│   数据4  	  栈顶（Top） ← 从这里进栈（Push）├─────────┤  │   数据3  │  	  ├─────────┤  │   数据2  │  	  ├─────────┤  │   数据1  │        └─────────┘栈底（Bottom）
  

  关键操作说明：

  1. 进栈 (Push)：

     • 将数据压入栈中，新数据总是位于栈顶。
     • 图示：

       进栈 数据5：┌─────────┐│   数据5    ← 新栈顶├─────────┤│   数据4  │	├─────────┤│   数据3  │	├─────────┤│   数据2  └─────────┘
       

  2. 弹栈 (Pop)：

     • 从栈顶移除数据，弹出的数据是最后压入的数据。
     • 图示：

       弹栈 数据5：┌─────────┐│   数据4    ← 新栈顶├─────────┤│   数据3 │├─────────┤│   数据2 │└─────────┘
       

  3. 函数调用栈：

     函数A 调用 函数B，函数B调用 函数C：
     ┌─────────┐
     │ 函数C局部   ← 当前执行
     ├─────────┤
     │ 函数B局部│
     ├─────────┤
     │ 函数A局部│
     └─────────┘
     

队列 (Queue)

• 介绍：
  队列是一种遵循 先进先出 原则的线性数据结构，数据只能从队尾插入，从队头取出，类似排队买票的过程。

  • 入队：数据从队尾进入。
  • 出队：数据从队头移出。

• 存储顺序：

  • 数据顺序存储

  • 新数据从队尾加入

  • 旧数据从队头取出
    这种方式保证了数据处理的顺序性和公平性。

    队头                 队尾  ↓                   ↓  
    [1] -> [2] -> [3] -> [4]  ↑  取出  
    

数组 (Array)

定义与特性
数组是一种基于连续内存空间的线性数据结构，其中每个元素通过索引直接访问。所 有元素共享相同的内存地址偏移量，存取速度快。

示例：

数组:  A   B   C   D   E   F   G  
索引:  0   1    2   3    4  5    6  

• 优点

  1. 快速访问
     • 通过索引直接访问元素，时间复杂度为 O(1) -> 直接访问。
  2. 数据独立性
     • 每个元素在数组中独立存在，无需依赖其他元素，方便管理和操作。

• 缺点

  1. 插入和删除效率低
     • 需要移动大量元素，时间复杂度为 O(n) -> 一次操作多次移动元素位置。
  2. 固定大小
     • 数组长度在初始化时需要确定，后期无法动态扩展。

​

• 应用场景

  1. 频繁查找的场景

     • 如哈希表的底层存储，利用数组的快速索引特性。

优化后的图表：

优点	描述
快速访问	支持通过索引直接访问，效率高 O(1)。
数据独立性	每个元素独立存在，操作简单，不依赖其他元素。

缺点	描述
插入效率低	需要移动元素，插入和删除操作成本高 O(n)。
固定大小	初始化后长度固定，扩展性差，无法灵活调整容量。

结构图示：

数组:  A   B   C   D   E   F   G  
索引:  0   1   2   3   4   5   6  插入操作（在索引3处插入X）：  
移动后的数组:  A   B   C   X   D   E   F   G  

链表（Linked List）

• 介绍
  链表是一种由节点构成的线性数据结构，每个节点包含以下两部分

  • 数据域：存储节点自身的数据。

  • 指针域：存储下一个节点（或前后节点）的地址。

分类

类型	特性
单向链表	每个节点只包含一个指向下一个节点的指针。
双向链表	每个节点包含两个指针，分别指向前一个节点和后一个节点。
循环链表	最后一个节点的指针指向第一个节点，形成闭环结构。

优点

1. 动态扩展：链表不需要连续的内存空间，内存利用率高。
2. 高效插入与删除：仅需修改指针即可完成操作，无需移动数据，效率高。

缺点

1. 查询效率低：链表无法通过索引直接访问，需要从头逐一遍历，耗时较多。
2. 额外存储开销：需要额外的指针域存储地址，占用更多内存。

图示

1. 单向链表

   [数据 | 指针] -> [数据 | 指针] -> [数据 | 指针] -> NULL
   

2. 双向链表

   NULL <- [指针 | 数据 | 指针] <-> [指针 | 数据 | 指针] <-> NULL
   

3. 循环链表
   链式存储结构，链表的尾节点指向头节点，形成一个首尾相连的环状结构。根据节点指针的数量，循环链表可以分为以下两种类型：

   1. 单向循环链表：每个节点仅包含一个指针域，指向下一个节点，最后一个节点的指针回指到头节点。
   2. 双向循环链表：每个节点包含两个指针域，分别指向前一个节点和后一个节点，头节点和尾节点通过指针互相连接。

   特点：

   • 可以从任意节点开始访问整个链表。

   优点： 高效利用尾节点与头节点的连接，无需特殊处理末尾条件。
   缺点： 实现和维护较普通链表复杂。

总结

链表在灵活性和动态扩展方面具有显著优势，但查询效率较低，不过频繁插入和删除的场景中表现较好。

总结

• 查询频繁，数据量较小：优先选择数组，支持快速访问。
• 插入和删除频繁：优先选择链表，避免大量数据移动。
• 队列场景：需要依赖先进先出的规则时使用队列。

如果这篇文章帮到你, 帮忙点个关注呗, 点赞或收藏也行鸭 ～ (｡•ᴗ-)✧

^ '(இ﹏இ`｡)