golang 基于数组、切片、链表实现队列
2023-12-14 00:10:23
数组
package main
import (
"errors"
"fmt"
)
func main() {
// 创建一个简单队列
// 如果head == tail 队列空
// 如果tail == len(array) - 1
// 整体做迁移 如果head == 0 队列满
stack1 := createQueue[int]()
err := stack1.push(1)
// 处理错误 后面的就不处理了
if err != nil {
return
}
stack1.push(2)
stack1.push(3)
stack1.push(4)
stack1.push(5)
popData1 := stack1.pop()
fmt.Printf("出队列元素%+v\n", *popData1)
popData2 := stack1.pop()
fmt.Printf("出队列元素%+v\n", *popData2)
stack1.push(6)
stack1.push(7)
stack1.push(8)
stack1.push(9)
stack1.pop()
err = stack1.push(10)
// 处理错误 后面的就不处理了
if err != nil {
fmt.Printf(err.Error() + "\n")
}
stack1.forEach()
}
// 默认小一点的空间 size 为5 数组空间=size+1
type queue[T int | string | map[string]string] struct {
data [6]T
head int
tail int
}
func createQueue[T int | string | map[string]string]() *queue[T] {
return &queue[T]{
data: [6]T{},
}
}
func (s *queue[T]) push(item T) error {
// len(s.data) - 1 这里固定为5
if len(s.data)-1 == s.tail {
if s.head == 0 {
return errors.New("队列满！")
}
// 做迁移
currentTail := s.tail - s.head
// 队列整体往前移动
for i := 0; i < currentTail; i++ {
s.data[i] = s.data[i+s.head]
}
s.head = 0
s.tail = currentTail
}
s.data[s.tail] = item
s.tail++
return nil
}
// 数组头部出队列
func (s *queue[T]) pop() *T {
// 队列为空
if s.head == s.tail {
return nil
}
res := &s.data[s.head]
s.head++
return res
}
func (s *queue[T]) forEach() {
fmt.Printf("遍历队列：\n")
for i := s.head; i < s.tail; i++ {
fmt.Printf("当前队列元素%+v\n", s.data[i])
}
}
切片
package main
import (
"fmt"
)
func main() {
// 创建一个简单队列
// 如果head == tail 队列空
// 如果tail == len(array) - 1
// 整体做迁移 如果head == 0 队列满
stack1 := createQueue[int](5)
err := stack1.push(1)
// 处理错误 后面的就不处理了
if err != nil {
return
}
stack1.push(2)
fmt.Printf("队列容量%+v\n", cap(stack1.data))
stack1.push(3)
stack1.push(4)
stack1.push(5)
popData1 := stack1.pop()
fmt.Printf("出队列元素%+v\n", *popData1)
popData2 := stack1.pop()
fmt.Printf("出队列元素%+v\n", *popData2)
stack1.forEach()
stack1.push(6)
stack1.push(7)
stack1.push(8)
stack1.push(9)
// 看是否自动扩容
fmt.Printf("队列容量%+v\n", cap(stack1.data))
popData3 := stack1.pop()
fmt.Printf("出队列元素%+v\n", *popData3)
err = stack1.push(10)
// 处理错误 后面的就不处理了
if err != nil {
fmt.Printf(err.Error() + "\n")
}
stack1.forEach()
}
type queue[T int | string | map[string]string] struct {
data []T
}
func createQueue[T int | string | map[string]string](len int) *queue[T] {
return &queue[T]{
data: make([]T, 0, len),
}
}
func (s *queue[T]) push(item T) error {
s.data = append(s.data, item)
return nil
}
// 数组头部出队列
func (s *queue[T]) pop() *T {
// 队列为空
if len(s.data) == 0 {
return nil
}
res := &s.data[0]
s.data = s.data[1:]
return res
}
func (s *queue[T]) forEach() {
fmt.Printf("遍历队列：\n")
for _, datum := range s.data {
fmt.Printf("当前队列元素%+v\n", datum)
}
}
链表
package main
import (
"errors"
"fmt"
)
func main() {
// 双向循环链表实现队列
linkedObj := getLinked[int](5)
err := linkedObj.headPush(6)
if err != nil {
fmt.Printf(err.Error())
}
err = linkedObj.headPush(5)
if err != nil {
fmt.Printf(err.Error())
}
err = linkedObj.headPush(4)
if err != nil {
fmt.Printf(err.Error())
}
err = linkedObj.headPush(3)
if err != nil {
fmt.Printf(err.Error())
}
err = linkedObj.headPush(2)
if err != nil {
fmt.Printf(err.Error())
}
err = linkedObj.headPush(1)
if err != nil {
fmt.Printf(err.Error())
}
err = linkedObj.headPush(0)
if err != nil {
fmt.Printf(err.Error())
}
//fmt.Printf("当前节点: %+v\n", linkedObj)
//fmt.Printf("当前节点: %+v\n", linkedObj.head.next.data)
item := linkedObj.tailPop()
fmt.Printf("弹出节点: %+v\n", *item)
item = linkedObj.tailPop()
fmt.Printf("弹出节点: %+v\n", *item)
linkedObj.headForeach()
err = linkedObj.headPush(-1)
if err != nil {
fmt.Printf(err.Error())
}
linkedObj.tailForeach()
}
type linked[T int | string | map[string]string] struct {
head *node[T]
length int
limit int
}
type node[T int | string | map[string]string] struct {
data *T
next *node[T]
prev *node[T]
}
func getLinked[T int | string | map[string]string](limit int) *linked[T] {
return &linked[T]{
head: nil,
length: 0,
limit: limit,
}
}
func createNode[T int | string | map[string]string](data T) *node[T] {
return &node[T]{
data: &data,
next: nil,
prev: nil,
}
}
// 从头部插入
func (l *linked[T]) headPush(data T) error {
if l.length >= l.limit {
return errors.New("当前队满\n")
}
newNode := createNode(data)
if l.head == nil {
l.head = newNode
l.length++
newNode.next = newNode
newNode.prev = newNode
return nil
}
currentNode := l.head
// 头结点位置
headNodePos := l.head
l.head = newNode
newNode.next = currentNode
currentNode.prev = newNode
// 找尾结点
for {
if currentNode.next == headNodePos {
break
}
currentNode = currentNode.next
}
if l.length >= l.limit {
currentNode.prev.next = newNode
newNode.prev = currentNode.prev
} else {
currentNode.next = newNode
newNode.prev = currentNode
l.length++
}
return nil
}
// 尾部弹出
func (l *linked[T]) tailPop() *T {
if l.head == nil {
return nil
}
currentNode := l.head
// 头结点位置
headNodePos := l.head
// 找尾结点
for {
if currentNode.next == headNodePos {
break
}
currentNode = currentNode.next
}
// 将尾结点的前一个节点作为尾节点
currentNode.prev.next = headNodePos
headNodePos.prev = currentNode.prev
l.length--
return currentNode.data
}
// 从头部遍历
func (l *linked[T]) headForeach() {
headNode := l.head
headNodPos := headNode
fmt.Printf("从头结点遍历：\n")
for {
fmt.Printf("当前节点: %+v\n", *headNode.data)
if headNode.next == headNodPos {
break
}
headNode = headNode.next
}
}
// 从尾部遍历
func (l *linked[T]) tailForeach() {
endNode := l.head
endNodePos := endNode
fmt.Printf("从尾结点遍历：\n")
for {
fmt.Printf("当前节点: %+v\n", *endNode.prev.data)
if endNode.prev == endNodePos {
break
}
endNode = endNode.prev
}
}
链表加锁实现线程安全
package main
import (
"errors"
"fmt"
"sync"
)
func main() {
// 双向循环链表实现队列 加锁实现并发安全
linkedObj := getLinked[int](5)
syncGroup := sync.WaitGroup{}
syncGroup.Add(1050)
for i := 0; i < 1000; i++ {
i := i
go func() {
err := linkedObj.headPush(i)
if err != nil {
fmt.Printf(err.Error())
}
syncGroup.Done()
}()
}
for i := 0; i < 50; i++ {
go func() {
data := linkedObj.tailPop()
if data != nil {
fmt.Println(*data)
}
syncGroup.Done()
}()
}
//fmt.Printf("当前节点: %+v\n", linkedObj)
//fmt.Printf("当前节点: %+v\n", linkedObj.head.next.data)
syncGroup.Wait()
linkedObj.headForeach()
}
type linked[T int | string | map[string]string] struct {
head *node[T]
length int
limit int
headLock sync.Mutex
tailLock sync.Mutex
}
type node[T int | string | map[string]string] struct {
data *T
next *node[T]
prev *node[T]
}
func getLinked[T int | string | map[string]string](limit int) *linked[T] {
return &linked[T]{
head: nil,
length: 0,
limit: limit,
headLock: sync.Mutex{},
tailLock: sync.Mutex{},
}
}
func createNode[T int | string | map[string]string](data T) *node[T] {
return &node[T]{
data: &data,
next: nil,
prev: nil,
}
}
// 从头部插入
func (l *linked[T]) headPush(data T) error {
l.headLock.Lock()
defer l.headLock.Unlock()
if l.length >= l.limit {
return errors.New("当前队满\n")
}
newNode := createNode(data)
if l.head == nil {
l.head = newNode
l.length++
newNode.next = newNode
newNode.prev = newNode
return nil
}
currentNode := l.head
// 头结点位置
headNodePos := l.head
l.head = newNode
newNode.next = currentNode
currentNode.prev = newNode
// 找尾结点
for {
if currentNode.next == headNodePos {
break
}
currentNode = currentNode.next
}
if l.length >= l.limit {
currentNode.prev.next = newNode
newNode.prev = currentNode.prev
} else {
currentNode.next = newNode
newNode.prev = currentNode
l.length++
}
return nil
}
// 尾部弹出
func (l *linked[T]) tailPop() *T {
l.tailLock.Lock()
defer l.tailLock.Unlock()
if l.head == nil {
return nil
}
currentNode := l.head
// 头结点位置
headNodePos := l.head
// 找尾结点
for {
if currentNode.next == headNodePos {
break
}
currentNode = currentNode.next
}
//currentNode.prev.next = headNodePos
//headNodePos.prev = currentNode.prev
if currentNode == headNodePos {
// The list has only one element
l.head = nil
} else {
currentNode.prev.next = headNodePos
headNodePos.prev = currentNode.prev
}
l.length--
return currentNode.data
}
// 从头部遍历
func (l *linked[T]) headForeach() {
if l.head == nil {
fmt.Printf("队空：\n")
return
}
headNode := l.head
headNodPos := headNode
fmt.Printf("从头结点遍历：\n")
for {
fmt.Printf("当前节点: %+v\n", *headNode.data)
if headNode.next == headNodPos {
break
}
headNode = headNode.next
}
}
// 从尾部遍历
func (l *linked[T]) tailForeach() {
if l.head == nil {
fmt.Printf("队空：\n")
return
}
endNode := l.head
endNodePos := endNode
fmt.Printf("从尾结点遍历：\n")
for {
fmt.Printf("当前节点: %+v\n", *endNode.prev.data)
if endNode.prev == endNodePos {
break
}
endNode = endNode.prev
}
}
cas 实现 无锁队列
// todo
文章来源:https://blog.csdn.net/u012914309/article/details/134983278
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！