golang环形队列实现代码示例

Summary

  • 什么是环形队列
  • 实现环形队列图示过程
  • golang版本代码实现过程
  • 参考全部代码

什么是环形队列

在一个指定大小的数组里循环写入数据,借用二个指针分别实现入队标记与出队标记.也体现了指针的大好用处,请深入体会.大有裨益.

如图所示,一个环形队列.含有二个指针: 队列头指针,队列尾指针.

实现环形队列图示过程

初始化一个数组大小为6的环形队列, 头指针front=0, 尾指针rear=0, 刚好front=rear =0的状态,表示环形队列为空.

2.向环形队列里插入1个元素,则rear指针移动一格,front=0,rear=1

3.继续添加a2,a3,a4,a5元素,rear指针指到末尾处,front=0, reat=5

4.如果再继续添加a6元素,则rear=6,大于数组大小,发生数组溢出.

5.如上图所示添加a6时,rear指针发生溢出.我们使用一个小技巧,当rear=6时与数组大小6进行取模, (rear+1) % maxLen,让rear指针回到开始处rear=0,问题来了,我们无法判断数组是否满?因为初始化时front=rear=0, 现在数组满也是front=rear=0

6.解决以上问题有三种办法,我们采用第3种方法实现.

使用第3种方法: 即当(rear+1) % maxLen == front时,判断环形数组满,则无法添加元素

golang版代码实现过程

a. 定义环形数据结构

type CycleQueue struct {
 data []interface{} //存储空间
 front int      //前指针,前指针负责弹出数据移动
 rear int      //尾指针,后指针负责添加数据移动
 cap  int      //设置切片最大容量
}

b.初始化环形队列

func NewCycleQueue(cap int) *CycleQueue {
 return &CycleQueue{
  data: make([]interface{}, cap),
  cap:  cap,
  front: 0,
  rear: 0,
 }
}

c. 入队操作

//入队操作
//判断队列是否队满,队满则不允许添加数据
func (q *CycleQueue) Push(data interface{}) bool {
 //check queue is full
 if (q.rear+1)%q.cap == q.front { //队列已满时，不执行入队操作
  return false
 }
 q.data[q.rear] = data     //将元素放入队列尾部
 q.rear = (q.rear + 1) % q.cap //尾部元素指向下一个空间位置,取模运算保证了索引不越界（余数一定小于除数）
 return true
}

d.出队操作

//出队操作
//需要考虑: 队队为空没有数据返回了
func (q *CycleQueue) Pop() interface{} {
 if q.rear == q.front {
  return nil
 }
 data := q.data[q.front]
 q.data[q.front] = nil
 q.front = (q.front + 1) % q.cap
 return data
}

e:求当前的环形队列长度

//因为是循环队列, 后指针减去前指针 加上最大值, 然后与最大值 取余
func (q *CycleQueue) QueueLength() int {
 return (q.rear - q.front + q.cap) % q.cap
}

参考全部代码

github

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Go语言的队列和堆栈实现方法

    本文实例讲述了Go语言的队列和堆栈实现方法.分享给大家供大家参考.具体如下: golang,其实我的实现是利用container/list包实现的,其实container/list包很强大. 复制代码 代码如下: package main import (     "fmt"     "container/list" ) func main() {     // 生成队列     l := list.New()     // 入队, 压栈     l.PushBac

  • 用golang实现一个定时器任务队列实例

    用golang实现一个定时器任务队列实例

    很有幸得到公司信任,采用新的语言进行一些底层服务的开发,在实现功能的同时,也获得了一些感悟,因此在这记录一下,方便自己查看也可以共享给大家. golang中定时器 golang中提供了2种定时器timer和ticker(如果JS很熟悉的话应该会很了解),分别是一次性定时器和重复任务定时器. 一般用法: func main() { input := make(chan interface{}) //producer - produce the messages go func() { for i

  • golang环形队列实现代码示例

    Summary 什么是环形队列 实现环形队列图示过程 golang版本代码实现过程 参考全部代码 什么是环形队列 在一个指定大小的数组里循环写入数据,借用二个指针分别实现入队标记与出队标记.也体现了指针的大好用处,请深入体会.大有裨益. 如图所示,一个环形队列.含有二个指针: 队列头指针,队列尾指针. 实现环形队列图示过程 初始化一个数组大小为6的环形队列, 头指针front=0, 尾指针rear=0, 刚好front=rear =0的状态,表示环形队列为空. 2.向环形队列里插入1个元素,则r

  • java编程队列数据结构代码示例

    java编程队列数据结构代码示例

    队列是一种特殊的线性表,只允许在表的前端进行删除,在表的后端进行插入,表的前端称为(front)队头,表的后端称为(rear)队尾. 所以队列跟生活的场景很是相似,在电影院买电影票,人们排成一排,第一个人进入队尾最先到达队头后买票进入影院,后面排队的人按照排队的次序买到票后进入影院. 所以 队列是一种先进先出的数据结构(FIFO). 编程实现对循环链队列的入队和出队操作. ⑴根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列(循环链队列),并且只设一个尾指针来指向尾结点,然后输出

  • java实现队列数据结构代码详解

    什么是队列结构 一种线性结构,具有特殊的运算法则[只能在一端(队头)删除,在另一端(队尾)插入]. 分类: 顺序队列结构 链式队列结构 基本操作: 入队列 出队列 给出一些应用队列的场景 1):当作业被送到打印机的时候,就可以按到达的顺序排起来,因此每一份作业是队列的节点. 2):售票口的人买票的顺序的按照先来先买的顺序售票. 3):当所有的终端被占用,由于资源有限,来访请求需要放在一个队列中等候. 队列是先进先出的! 我们设置一个叫做LinkQueue<T>的泛型集合类,该类里面有 Node

  • java中用数组实现环形队列的示例代码

    java中用数组实现环形队列的示例代码

    本篇文章主要讲述了使用数组实现环形队列的思路以及具体代码 一.队列是什么 我们先来看下百科的解释: 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头. 总结起来两点: 1.一种线性表 2.添加操作只能在表尾,删除操作在表头(先进先出) 二.实现队列的思路 1.初始化一个空队列 初始化一个大小固定的数组,并将头指针,尾指针都指向下表为0的位置,但其

  • GoLang 中的随机数的示例代码

    随机数我们都知道,就是计算机通过某种算法,"随机"的生成一个数字.很多编程语言都有内置的方法来生成随机数,那么 GoLang 中是怎样一种情况呢? 伪随机数 我们都知道"随机数"在现实生活中的概念,可能你随手抛一个硬币,就可以说其结果是随机的,但是在计算机中要确定一个"随机数"真的是"随机数",那可是有标准的,不是你随随便便说是就是. 根据密码学原理,要想对一个"随机数"进行随机性检验有以下几个标准: 统计

  • golang之JWT实现的示例代码

    什么是JSON Web Token? JSON Web Token(JWT)是一个开放标准(RFC 7519),它定义了一种紧凑且自包含的方式,用于在各方之间以JSON方式安全地传输信息.由于此信息是经过数字签名的,因此可以被验证和信任.可以使用秘密(使用HMAC算法)或使用RSA或ECDSA的公钥/私钥对对JWT进行签名. 直白的讲jwt就是一种用户认证(区别于session.cookie)的解决方案. 出现的背景 众所周知,在jwt出现之前,我们已经有session.cookie来解决用户登

  • golang如何优雅的编写事务代码示例

    前言 新手程序员大概有如下特点 if嵌套经常超过3层.经常出现重复代码.单个函数代码特别长. 只会crud,对语言特性和语言的边界不了解. 不懂面向对象原则和设计模式,以为copy代码就算学会了,常见的是代码职责不明确或者写出万能类 不知道数据结构和算法的重要性,以为靠硬件能解决运行慢的问题 架构不懂,搭建框架不会,搭建环境不会,使用的软件底层原理一问三不知 其实吧,很多人干了很多年,看似是老手,平时工作看似很忙,其实做的都是最简单的活. 这就像去锻炼,有的人每天练的很积极,准时打卡,频繁发朋友

  • golang实现数组分割的示例代码

    需求:给定一个数组和一个正整数,要求把数组分割成多个正整数大小的数组,如果不够分,则最后一个数组分到剩余的所有元素. 示例1: 数组:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],正整数:2 期望结果: [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10]] 示例2: 数组:[1, 2, 3, 4, 5, 6, 7, 8, 9],正整数:2 期望结果: [[1, 2], [3, 4], [5, 6], [7, 8], [9]] 下面是我的实现代码:

  • java数组实现队列及环形队列实现过程解析

    java数组实现队列及环形队列实现过程解析

    这篇文章主要介绍了java数组实现队列及环形队列实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码内容 ArrayQueue---用数组实现队列 package com.structure; import java.util.Scanner; /** * @auther::9527 * @Description: 数组模拟队列 * @program: jstl2 * @create: 2019-10-05 08:58 */ pub

  • PHP实现的memcache环形队列类实例

    本文实例讲述了PHP实现的memcache环形队列类.分享给大家供大家参考.具体如下: 这里介绍了PHP实现的memcache环形队列类.没咋学过数据结构,因为业务需要,所以只是硬着头皮模拟的! 参考PHP memcache 队列代码.为使队列随时可入可出,且不受int长度越界危险(单链采取Head自增的话不作处理有越界可能),所以索性改写成环形队列.可能还有BUG,忘见谅! <?php /** * PHP memcache 环形队列类 * 原作者 LKK/lianq.net * 修改 FoxH

随机推荐