Go数据机构

#Go数据机构| 来源: 网络整理| 查看: 265

一、栈Stack和队列Queue

我们日常生活中，都需要将物品排列，或者安排事情的先后顺序。更通俗地讲，我们买东西时，人太多的情况下，我们要排队，排队也有先后顺序，有些人早了点来，排完队就离开了，有些人晚一点，才刚刚进去人群排队。

数据是有顺序的，从数据 1 到数据 2，再到数据 3，和日常生活一样，我们需要放数据，也需要排列数据。

在计算机的世界里，会经常听见两种结构，栈（stack）和队列 (queue)。它们是一种收集数据的有序集合（Collection），只不过删除和访问数据的顺序不同。

栈：先进后出，先进队的数据最后才出来。在英文的意思里，stack 可以作为一叠的意思，这个排列是垂直的，你将一张纸放在另外一张纸上面，先放的纸肯定是最后才会被拿走，因为上面有一张纸挡住了它。

队列：先进先出，先进队的数据先出来。在英文的意思里，queue 和现实世界的排队意思一样，这个排列是水平的，先排先得。

现在我们尝试使用链表：（可连续和不连续的将数据与数据进行关联起来的结构），数组（连续的，可以按索引取值）来实现栈（Stack）和队列（Queue）

数组实现：能快速随机访问存储的元素，通过下标 index 访问，支持随机访问，查询速度快，但存在元素在数组空间中大量移动的操作，增删效率低。

链表实现：只支持顺序访问，在某些遍历操作中查询速度慢，但增删元素快。

二、实现数组栈ArrayStack

一种数组形式的下压栈：先进后出

主要实现采用可变长数组来实现：

//数组栈，先进后出 type ArrayStack struct{ array []string // }

因此对其进行对应的操作的实现：

package main import "sync" // 数组形式的下压栈 type ArrayStack struct { array []string //底层切片 size int //栈的元素数量 lock sync.Mutex //为了并发安全使用的锁 } // 入栈 func (stack *ArrayStack) Push(v string) { stack.lock.Lock() defer stack.lock.Unlock() //然后将元素放入数组最后面 stack.array = append(stack.array, v) //此时栈中元素数量+1 stack.size += 1 } // 出栈操作 func (stack *ArrayStack) Pop() string { stack.lock.Lock() defer stack.lock.Unlock() //首先必须进行对应的判断，栈空！！！ if stack.size == 0 { panic("empty!!") } //栈顶元素 v := stack.array[stack.size-1] //切片收缩，但可能占用的空间越来越大 //stack.array=stack.array[0:stack.size-1] //创建新的数组，空间占用不会越来越大，但可能移动元素次数过多 newArray := make([]string, stack.size-1, stack.size-1) for i := 0; i //栈中元素已空 if stack.size == 0 { panic("empty!!") } //栈顶元素值 v := stack.array[stack.size-1] return v } // 获取栈大小和判断是否为空 // 栈大小 func (stack *ArrayStack) Size() int { return stack.size } // 栈是都为空 func (stack *ArrayStack) IsEmpty() int { return stack.size }

最后进行测试的实现

func main() { arrayStack := new(ArrayStack) arrayStack.Push("1") arrayStack.Push("2") arrayStack.Push("3") fmt.Println("size:", arrayStack.Size()) //获取大小 fmt.Println("Pop操作：", arrayStack.Pop()) //输出出栈的元素 fmt.Println("size:", arrayStack.Size()) arrayStack.Push("4") }

输出结果为：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZJnberRf-1683727233815)(C:\Users\27198\AppData\Roaming\Typora\typora-user-images\image-20230510215705134.png)]

【本文地址】

公司简介

联系我们