# data-structure

**Repository Path**: he-boxuan/data-structure

## Basic Information

- **Project Name**: data-structure
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-10-11
- **Last Updated**: 2025-12-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 稀疏数组sparsearray
## 实际需求

<img src="img/img10.png"/>

说明：1代表黑棋，2代表蓝棋

## 稀疏数组基本介绍
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是:
1)记录数组一共有几行几列，有多少个不同的值
2)把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

<img src="img/img11.png"/>

## 代码实现
<img src="img/20251016_105141.png"/>

代码：[AparseArray.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Fsparsearray%2FAparseArray.java)

# 队列

## 队列介绍

<img src="img/20251016_140854.png"/>

## 使用数组模拟队列（有bug）
![img.png](img/img2.png)
![img.png](img/img1.png)
代码：[ArrayQueue.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Fqueue%2FArrayQueue.java)

问题：目前数组使用一次就不能用，没有达到复用的效果

解决：使用环形数组

## 环形队列（环形数组）
![img.png](img/img3.png)
代码：[CircleArray.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Fqueue%2FCircleArray.java)

# 单链表
## 单链表介绍
![img.png](img/img4.png)
![img.png](img/img5.png)

## 单链表应用实例
![img.png](img/img6.png)
代码：[SingleLinkedList.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Flinkedlist%2Fsingled%2FSingleLinkedList.java)
## 单链表练习
（1）获取单链表的有效节点的个数（如果是带头节点的链表，不统计头节点）

（2）新浪面试题：查找单链表中的倒数第k个节点

（3）腾讯面试题：单链表的反转

（4）百度面试题：从尾到头打印单链表

代码：[SingleLinkedList.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Flinkedlist%2Fsingled%2FSingleLinkedList.java)

（5）课后练习题：合并两个有序的单链表，合并之后的链表依然有序

代码：[SingleLinkedListDemo.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Flinkedlist%2Fsingled%2FSingleLinkedListDemo.java)

# 双向链表
## 双向链表应用实例
 ![img.png](img/img7.png)
 代码：[DoubleLinkedList.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Flinkedlist%2Fdoubled%2FDoubleLinkedList.java)
 
# 单向循环链表
## 单向循环链表介绍
![img.png](img/img9.png)
## 单向循环链表应用场景
![img.png](img/img8.png)

代码：[JosefuTest.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Flinkedlist%2Fjosepful%2FJosefuTest.java)

# 栈

## 栈的应用实例

![img.png](img/img12.png)

## 栈的介绍

![img_1.png](img/img13.png)

## 栈的应用场景

![img_2.png](img/img14.png)

## 栈的快速入门

![img.png](img/img15.png)

数组栈代码：[ArrayStack.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Fstack%2FArrayStack.java)

链表栈代码：[LinkedStack.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Fstack%2FLinkedStack.java)

## 使用栈实现中缀表达式

![img.png](img/img16.png)

代码：[Calculator.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Fcalculator%2FCalculator.java)

## 前缀表达式

![img.png](img/img17.png)

![img.png](img/img18.png)

## 后缀表达式

![img_1.png](img/img19.png)

![img.png](img/img20.png)

代码：[PolandNotation.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Fpolandnotation%2FPolandNotation.java)

## 中缀表达式转为后缀表达式

![img.png](img/img22.png)

代码：[PolandNotation.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Fpolandnotation%2FPolandNotation.java)


# 递归
## 递归的概念

简单的说，递归就是方法自己调用自己，每次调用是传入不同的变量。递归有助于编程者解决复杂的问题，
同时可以让代码变得简洁。

## 递归复习

[RecursionTest.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Frecursion%2FRecursionTest.java)

## 递归能解决什么样的问题

1）各种数学问题如：八皇后问题、汉诺塔、阶乘问题、迷宫问题

2）各种算法中也会使用到递归，比如快排、归并排序、二分查找、分治算法等

3）用栈解决的问题-->递归代码比较简洁

## 递归需要遵守的规则

1）执行一个方法时，就创建一个新的受保护的独立空间(栈空间)

2）方法的局部变量是独立的，不会相互影响，比如n变量

3）如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据

4）递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError

5）当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

## 递归-迷宫问题

![img_1.png](img/img21.png)

代码：[Maze.java](src%2Fmain%2Fjava%2Fcom%2Fatguigu%2Fmaze%2FMaze.java)

思考题：求最短路径

## 递归-八皇后问题（回溯算法）

![img_1.png](img/img23.png)

![img.png](img/img24.png)

说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题。
arr[8]// 对应arr下标表示第几行，即第几个皇后，arr[i]=val，val表示第i+1个皇后，放在第i+行的
第val+1列