围棋的数据结构 - [3.2 队列].
3.2 队列
队列与栈有相同的地方,但是也略有不同。本节我们将讲解队列的基本概念及Go
语言实现。
本节代码存放目录为 lesson5
概念及原理
队列是一种线性数据结构,它遵循先进先出(FIFO, First In First Out) 的原则。
也就是说,第一个进入队列的元素会最先被移除。
队列的操作包括:
-
入队(Enqueue):将元素加入队列的尾部。
-
出队(Dequeue):从队列的头部移除元素。
-
查看队首元素(Peek):获取队列头部的元素但不移除它。
队列就像排队一样,第一个排队的人最先离开,而新加入队列的人在最后排队。
队列的插入操作只能在队尾进行,删除操作只能在队首进行,非常适合处理需要按顺序处理的任务。
队列的结构示意图如下所示:
队首 队尾
+-------+ +-------+ +-------+
| 1 | <- | 2 | <- | 3 |
+-------+ +-------+ +-------+
出队方向 <- <- 入队方向
-
入队(Enqueue):将元素
3
加入队尾。 -
出队(Dequeue):移除队首元素
1
。 -
查看队首元素(Peek):获取队首元素
1
,但不移除它。
其操作示意如下所示:
- 入队操作:将元素依次加入队尾。
队首 队尾
+-------+
| 1 |
+-------+
+-------+ +-------+
| 1 | <- | 2 |
+-------+ +-------+
+-------+ +-------+ +-------+
| 1 | <- | 2 | <- | 3 |
+-------+ +-------+ +-------+
- 出队操作:从队首依次移除元素。
队首 队尾
+-------+ +-------+ +-------+
| 1 | <- | 2 | <- | 3 |
+-------+ +-------+ +-------+
+-------+ +-------+
| 2 | <- | 3 |
+-------+ +-------+
+-------+
| 3 |
+-------+
队列在很多应用中都有广泛的使用,特别是在需要按顺序处理的任务中:
-
任务调度:操作系统或任务调度器使用队列来管理任务,按顺序执行任务。
-
消息队列:在消息传递系统中,消息通常按照队列的顺序被处理和传递。
-
广度优先搜索(BFS):在图或树的遍历中,队列用于按层次逐步访问节点。
-
缓存管理:队列常用于缓存系统的缓存替换策略(如
FIFO
缓存算法)。
Go语言的实现
在Go
语言中,通道channel
与队列是有一些类似的,但是也不能算作一个完整的队列。
接下来我们同样使用切片模拟队列的实现,主要包括入队、出队、查看队首元素等,代码如下所示:
type Queue struct {
elements []int
}
func (q *Queue) Enqueue(ele int) {
q.elements = append(q.elements, ele)
}
func (q *Queue) Dequeue() int {
if len(q.elements) == 0 {
fmt.Println("队列为空")
return -1
}
front := q.elements[0]
// 移除队首元素
q.elements = q.elements[1:]
return front
}
func (q *Queue) Peek() int {
if len(q.elements) == 0 {
fmt.Println("队列为空")
return -1
}
return q.elements[0]
}
func (q *Queue) IsEmpty() bool {
return len(q.elements) == 0
}
func main() {
queue := &Queue{}
fmt.Println("queue is empty-> ", queue.IsEmpty())
queue.Enqueue(1)
queue.Enqueue(2)
queue.Enqueue(3)
queue.Dequeue()
fmt.Println("queue peek-> ", queue.Peek())
}
结果输出如下所示:
queue is empty-> true
queue peek-> 2
在上面的代码中,我们通过切片实现了队列的操作,将数组的头部作为队列的头部,添加元素则自动加到数组的末尾,也就是队列的尾部。
在实际的开发过程中,我们可以再增加上锁,即实现了一个支持并发的队列结构。
小结
队列是一种重要的数据结构,它遵循先进先出的原则,同样比较适合按顺序处理的任务场景,与栈结构大同小异。
关于本节总结如下:
-
队列是一种
FIFO
结构,最先入队的元素最先出队。 -
所有的插入操作都在队尾进行,删除操作在队首进行。
-
队列在处理需要顺序执行的任务时表现良好,适合调度、广度优先搜索等场景。
我的GitHub:https://github.com/swxctx
书籍地址:https://gs.golang.website/
书籍代码:https://github.com/YouCanGolang/GoStructedCode
下一篇: 网站设计的安全考虑因素有哪些?
推荐阅读
-
(队列和符号表数据结构的实现 - 2. 无序符号表
-
围棋的数据结构 - [3.2 队列].
-
【2022新手指南】Java编程进阶之路 - 六、技术架构篇 ### MySQL索引底层解析与优化实战 - 你会讲解MySQL索引的数据结构吗?性能调优技巧知多少? - Redis深度揭秘:你知道多少?从基础到哨兵、主从复制全梳理 - Redis持久化及哨兵模式详解,还有集群搭建和Leader选举黑箱打开 - Zookeeper是个啥?特性和应用场景大公开 - ZooKeeper集群搭建攻略及 Leader选举、读写一致性、共享锁实现细节 - 探究ZooKeeper中的Leader选举机制及其在分布式环境中的作用 - Zab协议深入剖析:原理、功能与在Zookeeper中的核心地位 - RabbitMQ全方位解读:工作模式、消费限流、可靠投递与配置策略 - 设计者视角:RabbitMQ过期时间、死信队列与延时队列实践指南 - RocketMQ特性和应用场景揭示:理解其精髓与差异化优势 - Kafka详细介绍:特性及广泛应用于实时数据处理的场景解析 - ElasticSearch实力揭秘:特性概述与作为搜索引擎的广泛应用 - MongoDB认知升级:非关系型数据库的优势阐述,安装与使用实战教学 - BIO/NIO/AIO网络模型对比:掌握它们的区别与在网络编程中的实际应用 - Netty带你飞:理解其超快速度背后的秘密,包括线程模型分析 - 网络通信黑科技:Netty编解码原理与常用编解码器的应用,Protostuff实战演示 - 解密Netty粘包与拆包现象,怎样有效应对这一常见问题 - 自定义Netty心跳检测机制,轻松调整检测间隔时间的艺术 - Dubbo轻骑兵介绍:核心特性概览,服务降级实战与其实现益处 - Dubbo三大神器解读:本地存根与本地伪装的实战运用与优势呈现 ----------------------- 七、结语与回顾
-
理解与操作:队列(queque)的数据结构解析
-
TypeScript里的数据结构与算法(16):详解优先级队列PriorityQueue
-
深入理解:优先级队列与堆在数据结构中的应用
-
堆与优先级队列详解:从数据结构的角度看赫夫曼树与优先处理队列的对比
-
深入理解Golang中的堆(Heap)数据结构:如何用堆来构造优先级队列
-
掌握技巧:深入理解优先级队列(Priority Queue)在数据结构中的应用
-
Python里的 PriorityQueue(优先队列)与 Heap(堆数据结构)