Java教程
多种语言实现数据结构之稀疏数组和队列
本文主要是介绍多种语言实现数据结构之稀疏数组和队列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
前言
一部分有工作经验的老司机对数据结构是很熟悉了，而一部分刚参加工作或者刚入行的人对数据结构是略懂一二甚至是感到陌生，希望本篇文章可以让老司机更熟悉数据结构的实现，不懂数据结构的小白对数据结构的实现有一定的了解。
本系列文章使用多种语言实现常用的数据结构，包括目前使用最多的 Java，21 世纪兴起的 Go，前端领域的 JavaScript，目的是尽可能的让更多的人能够看的懂、看的明白。整体上采用文字、图和代码的方式进行介绍，代码默认使用 Go 语言版本，其它语言请参考完整的源代码。
本篇为多种语言实现数据结构的第一节。
稀疏数组
各种语言实现代码：Go Java JavaScript
默认使用 Go 语言实现。
简介
在二维数组中，如果值为 0 的元素数目远远大于非 0 元素的数目，并且非 0 元素的分布没有规律，则该数组被称为稀疏数组。如果非 0 元素数目占大多数，则称该数组为稠密数组。数组的稠密度指的是非零元素的总数比上数组所有元素的总数。
下图是一个 0 值远大于非 0 值的二维数组
稀疏数组可以看做是一个压缩的数组，稀疏数组的好处有：
- 原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少
- 压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高 IO 效率
采用稀疏数组的存储方式为第一行存储原始数据总行数，总列数，默认值 0，接下来每一行都存储非0数所在行，所在列，和具体值。上图中的二维数组转成稀疏数组后如下：
下面使用稀疏数组存储上述的二维数组，把稀疏数组保存在文件中，并且可以重新恢复成二维数组。
创建二维数组并初始化
func printArray(array [5][5]int) {
for i := 0; i < len(array); i++ {
for j := 0; j < len(array[i]); j++ {
fmt.Print(array[i][j], "\t")
}
fmt.Print("\n")
}
}
func main() {
// 定义一个二维数组
var array [5][5]int
// 初始化 3，6， 1，5
array[0][2] = 3
array[1][3] = 6
array[2][1] = 1
array[3][3] = 5
fmt.Println("原二维数组：")
printArray(array)
}
复制代码输出：
原二维数组： 0 0 3 0 0 0 0 0 6 0 0 1 0 0 0 0 0 0 5 0 0 0 0 0 0 复制代码
二维数组转稀疏数组
// 二维数组转稀疏数组
func toSparseArray(array [5][5]int) [][3]int {
// Go 语言这样写无法编译通过
// var sparseArray [count + 1][]int
// 使用切片来定义
var sparseArray = make([][3]int, 0)
sparseArray = append(sparseArray, [3]int{ 5, 5, 0})
for i := 0; i < len(array); i++ {
for j := 0; j < len(array[i]); j++ {
if array[i][j] != 0 {
// 保存 row, col, val
sparseArray = append(sparseArray, [3]int{ i, j, array[i][j]})
}
}
}
return sparseArray
}
func printArray(array [5][5]int) {
for i := 0; i < len(array); i++ {
for j := 0; j < len(array[i]); j++ {
fmt.Print(array[i][j], "\t")
}
fmt.Print("\n")
}
}
func printSparseArray(sparseArray [][3]int) {
for i := 0; i < len(sparseArray); i++ {
for j := 0; j < 3; j++ {
fmt.Print(sparseArray[i][j], "\t")
}
fmt.Print("\n")
}
}
func main() {
// 定义一个二维数组
var array [5][5]int
// 初始化 3，6， 1，5
array[0][2] = 3
array[1][3] = 6
array[2][1] = 1
array[3][3] = 5
fmt.Println("原二维数组：")
printArray(array)
// 转成稀疏数组
sparseArray := toSparseArray(array)
fmt.Println("转换后的稀疏数组：")
printSparseArray(sparseArray)
}
复制代码输出：
原二维数组： 0 0 3 0 0 0 0 0 6 0 0 1 0 0 0 0 0 0 5 0 0 0 0 0 0 转换后的稀疏数组： 5 5 0 0 2 3 1 3 6 2 1 1 3 3 5 复制代码
存储和读取稀疏数组
var sparseArrayFileName = "./sparse.data"
// 存储稀疏数组
func storageSparseArray(sparseArray [][3]int) {
file, err := os.Create(sparseArrayFileName)
defer file.Close()
if err != nil {
fmt.Println("创建文件 sparse.data 错误:", err)
return
}
// 存储矩阵格式
for i := 0 ; i < len(sparseArray); i++ {
content := ""
for j := 0; j < 3; j++ {
content += strconv.Itoa(sparseArray[i][j]) + "\t"
}
// 行分隔符
content += "\n"
_, err = file.WriteString(content)
if err != nil {
fmt.Println("写入内容错误:", err)
}
}
}
// 读取稀疏数组
func readSparseArray() [][3]int {
file, err := os.Open(sparseArrayFileName)
defer file.Close()
if err != nil {
fmt.Println("打开文件 sparse.data 错误:", err)
return nil
}
sparseArray := make([][3]int, 0)
reader := bufio.NewReader(file)
for {
// 分行读取
content, err := reader.ReadString('\n')
if err == io.EOF {
break
}
arr := strings.Split(content, "\t")
row, _ := strconv.Atoi(arr[0])
col, _ := strconv.Atoi(arr[1])
val, _ := strconv.Atoi(arr[2])
sparseArray = append(sparseArray, [3]int { row, col, val})
}
return sparseArray
}
func main() {
// 定义一个二维数组
var array [5][5]int
// 初始化 3，6， 1，5
array[0][2] = 3
array[1][3] = 6
array[2][1] = 1
array[3][3] = 5
fmt.Println("原二维数组：")
printArray(array)
// 转成稀疏数组
sparseArray := toSparseArray(array)
fmt.Println("转换后的稀疏数组：")
printSparseArray(sparseArray)
// 存储稀疏数组
storageSparseArray(sparseArray)
// 读取稀疏数组
sparseArray = readSparseArray()
fmt.Println("读取的稀疏数组：")
printSparseArray(sparseArray)
}
复制代码运行以上代码后，打开 sparse.data 文件，内容如下：
5 5 0 0 2 3 1 3 6 2 1 1 3 3 5 复制代码
输出：
... 读取的稀疏数组： 5 5 0 0 2 3 1 3 6 2 1 1 3 3 5 复制代码
稀疏数组转二维数组
// 稀疏数组转二维数组
func toArray(sparseArray [][3]int) [5][5]int {
var array [5][5]int
// 从稀疏数组中第二行开始读取数据
for i := 1; i < len(sparseArray); i++ {
row := sparseArray[i][0]
col := sparseArray[i][1]
val := sparseArray[i][2]
array[row][col] = val
}
return array
}
func main() {
// 定义一个二维数组
var array [5][5]int
// 初始化 3，6， 1，5
array[0][2] = 3
array[1][3] = 6
array[2][1] = 1
array[3][3] = 5
fmt.Println("原二维数组：")
printArray(array)
// 转成稀疏数组
sparseArray := toSparseArray(array)
fmt.Println("转换后的稀疏数组：")
printSparseArray(sparseArray)
// 存储稀疏数组
storageSparseArray(sparseArray)
// 读取稀疏数组
sparseArray = readSparseArray()
fmt.Println("读取的稀疏数组：")
printSparseArray(sparseArray)
// 转成二维数组
array = toArray(sparseArray)
fmt.Println("转换后的二维数组：")
printArray(array)
}
复制代码输出：
... 转换后的二维数组： 0 0 3 0 0 0 0 0 6 0 0 1 0 0 0 0 0 0 5 0 0 0 0 0 0 复制代码
队列(queue)
各种语言实现代码：Go Java JavaScript
默认使用 Go 语言实现。
简介
队列是一种特殊的线性表，它只允许在线性表的前端进行删除操作，在表的后端进行插入操作，所以队列又称为先进先出（FIFO—first in first out）的线性表。进行插入操作的一端叫做队尾，进行删除操作的一端叫做队头。队列的数据元素叫做队列元素，在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。
顺序队列
顺序队列类似数组，它需要一块连续的内存，并有两个指针，一个是队头指针 front，它指向队头元素，另一个是队尾指针 rear，它指向下一个入队的位置。在队尾插入一个元素时，队尾指针加一，在队头删除一个元素时，队头指针加一。不断的进行插入和删除操作，队列元素在不断的变化，当队头指针等于队尾指针时，队列中没有任何元素，没有元素的队列称为空队列。对于已经出队列的元素所占用的空间，顺序队列无法再次利用。
队列可以使用数组结构或者链表结构来实现，这里使用数组来实现队列。
用数组来实现顺序队列的思路：
- 定义数组，存储队列元素
- 定义队列最大大小 maxSize
- 定义队头指针 front，初始化为 0
- 队尾指针 rear，初始化为 0
- 入队方法 put
- 出队方法 take
定义顺序队列结构体和创建结构体实例函数：
type IntQueue struct {
array []int // 存放队列元素的切片（数组无法使用变量来定义长度）
maxSize int // 最大队列元素大小
front int // 队头指针
rear int // 队尾指针
}
func NewQueue(size int) *IntQueue {
return &IntQueue{
array: make([]int, size),
maxSize: size,
front: 0,
rear: 0,
}
}
复制代码入队方法：
func (q *IntQueue) Put(elem int) error {
// 队尾指针不能超过最大队列元素大小
if q.rear >= q.maxSize {
return errors.New("queue is full")
}
q.array[q.rear] = elem
q.rear++ // 队尾指针加一
return nil
}
复制代码出队方法：
func (q *IntQueue) Take() (int, error) {
// 队头指针等于队尾指针表示队列为空
if q.front == q.rear {
return 0, errors.New("queue is empty")
}
elem := q.array[q.front]
q.front++ // 队头指针加一
return elem, nil
}
复制代码为了方便查看输出结果，重新定义 String 方法：
// 重新定义 String 方法，方便输出
func (q *IntQueue) String() string {
str := "["
for i := q.front; i < q.rear; i++ {
str += strconv.Itoa(q.array[i]) + " "
}
str += "]"
return str
}
复制代码测试代码如下：
func main() {
intQueue := NewQueue(3)
_ = intQueue.Put(1)
_ = intQueue.Put(2)
_ = intQueue.Put(3)
_ = intQueue.Put(4) // 队列已满，无法放入数据
fmt.Println("intQueue:", intQueue)
num, _ := intQueue.Take()
fmt.Println("取出一个元素:", num)
num, _ = intQueue.Take()
fmt.Println("取出一个元素:", num)
num, _ = intQueue.Take()
fmt.Println("取出一个元素:", num)
num, takeErr := intQueue.Take()
fmt.Println("取出一个元素:", num)
if takeErr != nil {
fmt.Println("出队失败:", takeErr)
}
// 此时队列已经用完，无法放数据
putErr := intQueue.Put(4)
if putErr != nil {
fmt.Println("入队失败:", putErr)
}
fmt.Println("intQueue:", intQueue)
}
复制代码测试以上代码，输出：
intQueue: [1 2 3 ] 取出一个元素: 1 取出一个元素: 2 取出一个元素: 3 取出一个元素: 0 出队失败: queue is empty 入队失败: queue is full intQueue: [] 复制代码
循环队列
在实际使用队列时，顺序队列空间不能重复使用，需要对顺序队列进行改进。不管是插入或删除，一旦 rear 指针增 1 或 front 指针增 1 时超出了队列所分配的空间，就让它指向起始位置。当 MaxSize - 1增 1变到 0，可用取余运算获取队头或者队尾指针增加 1 后的位置，队尾指针计算方法为 rear % MaxSize，队尾指针计算方法为 front % MaxSize。这种循环使用队列空间的队列称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。
使用数组实现循环队列思路：
- 定义数组，存储队列元素
- 定义队列最大大小 maxSize
- 定义队头指针 front，初始化为 0，删除元素后，重新计算值，计算公式为：(front + 1) % maxSize
- 队尾指针 rear，初始化为 0，插入元素后，重新计算值，计算公式为：(q.rear + 1) % q.maxSize
- 判断队列是否为空的方法，判断 front 等于 rear 判断即可
- 判断队列是否已满的方法，判断 (rear + 1) % maxSize 是否等于 front
- 获取队列元素大小方法，计算公式：(rear + maxSize - front) % maxSize
- 入队方法 put
- 出队方法 take
定义循环队列结构体和创建结构体实例函数：
type IntQueue struct {
array []int // 存放队列元素的切片（数组无法使用变量来定义长度）
maxSize int // 最大队列元素大小
front int // 队头指针
rear int // 队尾指针
}
func NewQueue(size int) *IntQueue {
return &IntQueue{
array: make([]int, size),
maxSize: size,
front: 0,
rear: 0,
}
}
复制代码判断队列是否为空：
func (q *IntQueue) isEmpty() bool {
// 队头指针等于队尾指针表示队列为空
return q.front == q.rear
}
复制代码判断队列是否已满：
func (q *IntQueue) isFull() bool {
// 空出一个位置，判断是否等于队头指针
// 队尾指针指向的位置不能存放队列元素，实际上会比 maxSize 指定的大小少一
return (q.rear + 1) % q.maxSize == q.front
}
复制代码获取队列元素大小：
func (q *IntQueue) size() int {
return (q.rear + q.maxSize - q.front) % q.maxSize
}
复制代码入队方法：
func (q *IntQueue) Put(elem int) error {
if q.isFull() {
return errors.New("queue is full")
}
q.array[q.rear] = elem
// 循环累加，当 rear + 1 等于 maxSize 时变成 0，重新累加
q.rear = (q.rear + 1) % q.maxSize
return nil
}
复制代码出队方法：
func (q *IntQueue) Take() (int, error) {
if q.isEmpty() {
return 0, errors.New("queue is empty")
}
elem := q.array[q.front]
q.front = (q.front + 1) % q.maxSize
return elem, nil
}
复制代码重新定义的 String 方法：
func (q *IntQueue) String() string {
str := "["
tempFront := q.front
for i := 0; i < q.size(); i++ {
str += strconv.Itoa(q.array[tempFront]) + " "
// 超过最大大小，从 0 开始
tempFront = (tempFront + 1 ) % q.maxSize
}
str += "]"
return str
}
复制代码测试代码如下：
func main() {
intQueue := NewQueue(5)
_ = intQueue.Put(1)
_ = intQueue.Put(2)
_ = intQueue.Put(3)
_ = intQueue.Put(4)
_ = intQueue.Put(5) // 队列已满，无法放入数据，实际上只能放 4 个元素
fmt.Println("intQueue:", intQueue)
num, _ := intQueue.Take()
fmt.Println("取出一个元素:", num)
num, _ = intQueue.Take()
fmt.Println("取出一个元素:", num)
num, _ = intQueue.Take()
fmt.Println("取出一个元素:", num)
num, _ = intQueue.Take()
fmt.Println("取出一个元素:", num)
num, takeErr := intQueue.Take()
fmt.Println("取出一个元素:", num)
if takeErr != nil {
fmt.Println("出队失败:", takeErr)
}
// 取出数据后可以继续放入数据
_ = intQueue.Put(5)
fmt.Println("intQueue:", intQueue)
}
复制代码测试以上代码，输出：
intQueue: [1 2 3 4 ] 取出一个元素: 1 取出一个元素: 2 取出一个元素: 3 取出一个元素: 4 取出一个元素: 0 出队失败: queue is empty intQueue: [5 ] 复制代码
这篇关于多种语言实现数据结构之稀疏数组和队列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
栏目导航
