在go语言中数据结构之队列链表实现示例代码
Go  /  管理员 发布于 1年前   253
数据结构-队列描述:遵循先进先出原则的线性表,其插入与删除操作分别在表的两端进行,
进行插入操作的是队尾 (back/rear),删除操作的是队首 (front)。
队列链表实现代码示例:
基于单链表实现同样要区分一下哪里是队列头,哪里是队列尾
首先我们需要两个指针,front 与 back 分别指向头与尾
如果是插入操作的话,无论哪一端是队尾都是很简单的
如果头节点是队尾:
queue= &node{
Val:val,
Next:head,
}
如果链表结尾是队尾:
back.Next := &node{
Val:val,
Next:nil,
}
back = back.Next
可见他们都是 O (1) 操作,但是删除操作就不一样了。
假设是头节点为队尾,那么删除操作需要先遍历到队尾前一个节点,随后断开链。
而链尾是队尾的情况只需要让 front = front.Next 就可以轻松断开
所以我们定义这个链表实现的队列,头节点处为队首,尾节点处为队尾
type LinkedQueue struct {
// 指向链首
QueueFront *chainNode
QueueBack *chainNode
QueueSize int
}
type chainNode struct {
Val interface{}
Next *chainNode
}
func (q *LinkedQueue) Empty() bool {
/*
if q.QueueBack == q.QueueBack && q.QueueFront == nil {
return true
}
return false
*/
return q.QueueSize == 0
}
func (q *LinkedQueue) Size() int {
return q.QueueSize
}
func (q *LinkedQueue) Front() (interface{}, bool) {
if q.Empty() {
return nil, false
}
return q.QueueFront.Val, true
}
func (q *LinkedQueue) Back() (interface{}, bool) {
if q.Empty() {
return nil, false
}
return q.QueueBack.Val, true
}
func (q *LinkedQueue) Pop() (interface{}, bool) {
if q.Empty() {
return nil, false
}
val := q.QueueFront.Val
q.QueueFront = q.QueueFront.Next
q.QueueSize--
return val, true
}
func (q *LinkedQueue) Push(val interface{}) bool {
node := &chainNode{
Val: val,
}
if q.Empty() {
q.QueueFront = node
} else {
q.QueueBack.Next = node
}
q.QueueBack = node
q.QueueSize++
return true
}
原梓番博客 在
在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..博主 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..1111 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..路人 在
php中使用hyperf框架调用讯飞星火大模型实现国内版chatgpt功能示例中评论 教程很详细,如果加个前端chatgpt对话页面就完美了..博主 在
科学上网翻墙之v2rayN-Core客户端免费公益节点使用教程中评论 @ mashrdn 多切换几个节点测试,免费ssr是没那么稳..Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号