【刷题日记】622. 设计循环队列

一、题目描述：

今天来做一个循环队列设计相关的题，可不仅仅是刷一个算法题哦，这设计到基本简单的设计

二、这道题考察了什么思想？你的思路是什么？

本题是考查咱们的简单设计能力，对于循环队列的简单设计，先保证功能，再考虑优化和优雅，好程序都是迭代出来

题目要求我们自己实现一个队列，需要有如下功能点：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

分析

根据题目的要求，我们要先明确队列的特性，队列是先入先出的 FIFO，那么循环队列是什么呢，就是首尾连接成环，简单来说就是队尾的下一个是队头

对于一个循环队列，我们至少需要哪些元素呢？

• 基本的数据节点对象，队列对象
• 队列的最大容量和队列的当前已有数据量
• 队列的头 和 队列的尾

设计一个基本的循环队列，能够满足上述条件，就可以完成本题的基本设计了，我们可以这样来设定标准：

• 对于构造器

MyCircularQueue(k)，实际上就是咱们就是初始化一个队列的对象，初始化整个队列的容量

• Front: 从队首获取元素

即我们读取对头的数据即可，如果队列为空，则直接返回 -1 即可

• Rear: 获取队尾元素

同理，咱们直接读取队列尾巴的元素即可，若队尾尾空，则返回 -1

• enQueue(value)

元素入队，这里我们就要考虑三种情况

• 当队列里面是空的时候入队

直接将数据做成节点，让队列的 head 和 tail 都指向这个节点即可，并且把队列的 size +1

• 队列里面已经有元素的时候入队

若队列未满，则正常将数据做成节点，让尾指针指向最新的节点即可，并且把队列的 size +1

• 以及队列里面已经满了的情况入队

若校验到队列已满，则禁止入队，返回 false

• deQueue()

出队，刚才有说到，队列是 FIFO 的，上述入队是从尾巴加入，那么出队就是从头出去，咱们需要考虑 2 种情况

• 队列为空的情况

这个时候无数据出队，则返回 false

• 队列不为空

则正常从取出当前 head 的值，并将 head 的指针向下移动一个，此时的 size -1

• 那么判断队列为空，则直接判断队列的 size 是否为 0 即可
• 判断队列是否为满，同理，直接判断当前的 size 是否等于 队列的容量 cap 即可

那么实际上编码就是将上述逻辑进行一个翻译就可以了，另外，此处如果是要访问 tail 的下一个指针，其实我们是知道就是要访问 head 的，因此此处没有显示的将 tail 指针指向 head

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码如下：

type MyCircularQueue struct {
    head, tail     *ListNode
    cap, size int
}
func Constructor(n int) MyCircularQueue {
    return MyCircularQueue{cap: n}
}
func (q *MyCircularQueue) EnQueue(value int) bool {
    if q.IsFull() {
        return false
    }
    node := &ListNode{Val: value}
    if q.head == nil {
        q.head = node
        q.tail = node
    } else {
        q.tail.Next = node
        q.tail = node
    }
    q.size++
    return true
}
func (q *MyCircularQueue) DeQueue() bool {
    if q.IsEmpty() {
        return false
    }
    q.head = q.head.Next
    q.size--
    return true
}
func (q MyCircularQueue) Front() int {
    if q.IsEmpty() {
        return -1
    }
    return q.head.Val
}
func (q MyCircularQueue) Rear() int {
    if q.IsEmpty() {
        return -1
    }
    return q.tail.Val
}
func (q MyCircularQueue) IsEmpty() bool {
    return q.size == 0
}
func (q MyCircularQueue) IsFull() bool {
    return q.size == q.cap
}

四、总结：

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~