1. Toy模板网首页
  2. > Toy博客

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

10月前 作者：拥 分类：Toy博客 阅读(42) 违法举报

这篇具有很好参考价值的文章主要介绍了golang 基于数组、切片、链表实现队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数组

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://www.toymoban.com/news/detail-757579.html

到了这里，关于golang 基于数组、切片、链表实现队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 王道408用数组，链表以及双向链表实现栈、队列

    我在电脑上敲了一遍，又在纸上模拟了一遍 下面记录在电脑上敲的:    

    2024年02月14日
    浏览(37)
  • 数据结构：队列(链表和数组模拟实现)

    数据结构：队列(链表和数组模拟实现)

    目录 1.何为队列 2.链表模拟实现 2.1 节点和队列创建 2.2 初始化队列 2.3 入队操作 2.4 出队操作 2.5 遍历队列 2.6 获取队首和队尾元素 2.7 判断队列是否为空 2.8 完整实现 3. 数组模拟实现 3.1 创建队列 3.2 入队和出队操作 3.3 遍历队列 3.4 获取队首和队尾元素  3.5 判断队列是否为空

    2024年02月03日
    浏览(54)
  • 【Golang】Golang进阶系列教程--Go 语言数组和切片的区别

    【Golang】Golang进阶系列教程--Go 语言数组和切片的区别

    在 Go 语言中，数组和切片看起来很像，但其实它们又有很多的不同之处，这篇文章就来说说它们到底有哪些不同。 数组和切片是两个常用的数据结构。它们都可以用于存储一组相同类型的元素，但在底层实现和使用方式上存在一些重要的区别。 Go 中数组的长度是不可改变的

    2024年02月15日
    浏览(61)
  • Golang教程一（环境搭建，变量，数据类型，数组切片map）

    Golang教程一（环境搭建，变量，数据类型，数组切片map）

    目录 一、环境搭建 1.windows安装 2.linux安装  3.开发工具 二、变量定义与输入输出 1.变量定义 2.全局变量与局部变量 3.定义多个变量 4.常量定义 5.命名规范 6.输出 格式化输出 7.输入  三、基本数据类型 1.整数型 2.浮点型 3.字符型 4.字符串类型 转义字符 多行字符串 5.布尔类型

    2024年04月16日
    浏览(49)
  • 【数据结构和算法】使用数组的结构实现链表（单向或双向）

    【数据结构和算法】使用数组的结构实现链表（单向或双向）

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现，我们或许在其他老师的教学中，只学到了用结构体的形式来实现链表、队列、栈等数据结构，本文我想告诉你的是，我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(74)
  • 数据结构——线性数据结构（数组，链表，栈，队列）

    数据结构——线性数据结构（数组，链表，栈，队列）

    数组（Array） 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。 我们直接可以利用元素的索引（index）可以计算出该元素对应的存储地址。 数组的特点是： 提供随机访问 并且容量有限。 2.1. 链表简介 链表（LinkedList） 虽然是

    2024年02月11日
    浏览(44)

  • C++数据结构与算法详解：链表、栈、队列、树、二叉树和图结构的实现与应用

    链表是一种常见的数据结构由一系列节点按顺序连接而成，一般每个节点包含一个数据元素和一个指向下一个节点的引用。 链表有多种类型： 单向链表：每个节点只有一个指向下一个节点的引用 双向链表：每个节点有一个指向前一个节点和一个指向后一个节点的引用 循环链

    2024年02月04日
    浏览(52)
  • 【SystemVerilog 之数据类型】~ 数据类型、Logic 类型、数组（定宽数组、动态数组、队列、关联数组、链表）

    【SystemVerilog 之数据类型】~ 数据类型、Logic 类型、数组（定宽数组、动态数组、队列、关联数组、链表）

    四值变量 ：（0、1、x、z）四种状态 四值逻辑类型 ：integer、logic、reg、net-type（如 wire、tri）、time（64bit的无符号整数）； SV 并不太常用变量类型是 wire(assign 语句中)还是 reg(initial 和 always 语句中)。logic 用的比较多。可以被连续赋值语句驱动，可用在 assign、initial、always 语句

    2024年01月22日
    浏览(40)

  • 数据结构之线性表的类型运用Linear Lists: 数组，栈，队列，链表

    定义 一个最简单，最基本的数据结构。一个线性表由多个相同类型的元素穿在一次，并且每一个元素都一个前驱（前一个元素）和后继（后一个元素）。 线性表的类型 常见的类型：数组、栈、队列、链表 这些不同数据结构的特性可以解决不同种类的问题 题面 题目描述 有

    2024年02月12日
    浏览(47)
  • Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率 栈 队列 数组 链表 二叉树 二叉查找树 平衡二叉树 红黑树... 后进先出，先进后出 数据进入栈模型的过程称为

    2024年02月07日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包