golang 基于数组、切片、链表实现队列

发布时间：2023年12月17日

数组

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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

golang 基于数组、切片、链表实现队列

数组

切片

链表

链表加锁实现线程安全

cas 实现 无锁队列

cas 实现无锁队列