涪陵区小城镇建设管理处网站,h5怎么生成二维码,wordpress文章添加seo标题,wordpress 凌风目录 队列数组队列的“假溢出”现象循环队列三种判断队列空和满的方法无下标#xff08;链式#xff09;有下标#xff08;顺序#xff09;长度标记 go用顺序表实现一个循环队列队列的链式存储结构 队列
队列#xff08;queue#xff09;是只允许在一端进行插入操作链式有下标顺序长度标记 go用顺序表实现一个循环队列队列的链式存储结构 队列
队列queue是只允许在一端进行插入操作在另一端进行删除操作的线性表简称“队”。
队列是一种先进先出First In First Out的线性表简称FIFO。
允许插入的一端称为队尾rear允许删除的一端称为队头(front)。
向队列中插入新的数据元素称为入队新入队的元素就成为了队列的队尾元素。
从队列中删除队头元素称为出队其后继元素成为新的队头元素。 队列有很多种按照存储结构划分有链式队列循环队列单向队列双端队列。实现队列的方式也有很多种如基于链式存储结构的链接队列又称链队列基于顺序存储结构的队列。
数组队列的“假溢出”现象
在队列的顺序存储结构中除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外还需要设置头尾两个指针front和rear分别指示队列头元素及队尾元素的位置。
初始化建立空队列时令frontrear0每当插入新的队尾元素时“尾指针增1”每当删除队头元素时“头指针增1”在非空队列中头指针始终指向队列头元素尾指针始终指向队列尾元素的下一个位置 在入队和出队的操作中头尾指针只增加不减小致使被删除元素的空间永远无法重新利用因此尽管队列中实际的元素个数远远小于向量空间的规模但也可能由于尾指针巳超出向量空间的上界而不能做入队操作该现象称为假溢出。
解决办法将顺序队列臆造为一个环状的空间称之为循环队列
循环队列 队列的头尾相接的顺序存储结构称为循环队列。
问题当循环对列为空或满时都是队尾指针等于队头指针即rearfront 。当rearfront时该是判满还是判空呢
解决方案 方案一设置一个计数器开始时计数器设为0新元素入队时计数器加1元素出队计数器减1。当计数器MAXSIZE时队满计数器0时队空。 方案二保留一个元素空间当队尾指针指的空闲单元的后继单元是队头元素所在单元时队满。
三种判断队列空和满的方法
无下标链式 当队列为空时条件rear front
当队列满时条件为rear1 front
有下标顺序 当队列为空时条件rear front
当队列满时条件为rear1% maxsize front
长度标记
设置一个标记位
队列为空时count 0
当有元素入队时count当count和队列的maxsize相等时代表队列已满
go用顺序表实现一个循环队列
初始化结构体
type LoopQueue struct {mem []int// length capcap int// indexfront, rear int
}func Queue(size int) *LoopQueue {return LoopQueue{mem: make([]int, size),cap: size,front: 0,rear: 0,}
}判空判满
func (q *LoopQueue) IsEmpty() bool {return q.front q.rear
}func (q *LoopQueue) IsFull() bool {return (q.rear1)%q.cap q.front
}push,pop操作
func (q *LoopQueue) Push(val int) error {if q.IsFull() {return errors.New(queue is full)}q.mem[q.rear] val// 当尾达到最大index就不能简单自增而是要循环q.rear (q.rear 1) % q.capreturn nil
}func (q *LoopQueue) Pop() (int, error) {if q.IsEmpty() {return -1, errors.New(empty queue)}pop : q.mem[q.front]// 当头达到最大index就不能简单自增而是要循环q.front (q.front 1) % q.capreturn pop, nil
}队列的链式存储结构
采用链式存储结构实现的队列称为链队列。
为了使操作更加方便将队头指针指向链队列的头结点而队尾指针指向终端结点。 用链表实现的队列也有“假溢出”的现象所以go提供了Ring数据结构只要导入container/ring就可以使用循环链表。
type Ring struct {next, prev *RingValue any // for use by client; untouched by this library
}func New(n int) *Ring {if n 0 {return nil}r : new(Ring)p : rfor i : 1; i n; i {p.next Ring{prev: p}p p.next}// 头尾相连p.next rr.prev preturn r
}
