【刷题日记】641. 设计循环双端队列-阿里云开发者社区

【刷题日记】641. 设计循环双端队列

2023-07-19 50

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【刷题日记】641. 设计循环双端队列

本次刷题日记的第 93 篇，力扣题为：641. 设计循环双端队列

一、题目描述：

咱今天来做一个设计类的题目，641. 设计循环双端队列

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

还记得之前我们写过设计循环队列的题目【刷题日记】622. 设计循环队列，本次我们来设计循环双端队列，实际上这俩题咱们的实现思路差不多，不过我们还是来巩固一下链表的使用吧

题目要求我们设计一个双端队列，双端队列，咱们需要实现如下功能

构造基本双端队列
将数据从队列头插入
从队列尾部插入数据
删除队头
删除队尾
获取队头元素
获取队尾元素
判断队列是否为空
判断队列是否满

分析

对于一个队列来说，我们使用链表来实现循环双端队列，先来简单快速的温习一下链表的基本知识

咱们的链表是由一个节点一个节点的串起来的，串起来之后就是是一个链表了

咱们的一个节点有指针域和值域，例如下面这样，这是一个简单的节点

前向指针（指针域）	节点本身的值（值域）	后向指针（指针域）

那么多个节点连接起来就是这个样子的

这个时候，如果是要加上头指针和指针，那就是这样的

咱们这个时候，要是想获取队列头那就就是直接读取 head 指向的节点值即可，同理，要是想读取队列尾部的值，那么就直接读取 tail 指向的节点值即可

那么对于判断一个队列是空，或者是满，咱们直接判断队列的 size 和 cap 的关系就可以了

判断队列为空，即判断 size 是否为 0 即可，判断队列是否为满，则判断 size 和 cap 是否相等即可

对于从队头插入数据和队尾插入数据，我们可以这样来插入

新建一个节点，节点的 next 指针指向 head
head 的 prev 指向新的节点
head 指针指向新节点的地址上
size++

从尾部插入一个节点，原理也是一样的，去操作 tail 指针就可了

最后，我们来看一下如何移除链表头和移除链表尾呢？

咱们删除队列头的话，我们可以这样来删除：

Head 指针指针 head 的下一个节点
此时 head 指针的 prev 指针指向空，即 nil
size--

同样的道理，删除尾巴指针的节点，我们也是这样的做法，只用去操作 tail 指针对应的节点就可以了

至此，咱们就可以按照上面的思路，进行编码的实现代码就可以，来撸代码就可以了

三、编码

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

在插入数据，删除数据的时候，注意队列为空，队列为满的时候，我们需要特殊处理一下

编码如下：

type node struct {
    prev, next *node
    val        int
}
type MyCircularDeque struct {
    head, tail     *node
    capacity, size int
}
func Constructor(k int) MyCircularDeque {
    return MyCircularDeque{capacity: k}
}
func (q *MyCircularDeque) InsertFront(value int) bool {
    if q.IsFull() {
        return false
    }
    node := &node{val: value}
    if q.IsEmpty() {
        q.head = node
        q.tail = node
    } else {
        node.next = q.head
        q.head.prev = node
        q.head = node
    }
    q.size++
    return true
}
func (q *MyCircularDeque) InsertLast(value int) bool {
    if q.IsFull() {
        return false
    }
    node := &node{val: value}
    if q.IsEmpty() {
        q.head = node
        q.tail = node
    } else {
        q.tail.next = node
        node.prev = q.tail
        q.tail = node
    }
    q.size++
    return true
}
func (q *MyCircularDeque) DeleteFront() bool {
    if q.IsEmpty() {
        return false
    }
    q.head = q.head.next
    if q.head != nil {
        q.head.prev = nil
    }
    q.size--
    return true
}
func (q *MyCircularDeque) DeleteLast() bool {
    if q.IsEmpty() {
        return false
    }
    q.tail = q.tail.prev
    if q.tail != nil {
        q.tail.next = nil
    }
    q.size--
    return true
}
func (q MyCircularDeque) GetFront() int {
    if q.IsEmpty() {
        return -1
    }
    return q.head.val
}
func (q MyCircularDeque) GetRear() int {
    if q.IsEmpty() {
        return -1
    }
    return q.tail.val
}
func (q MyCircularDeque) IsEmpty() bool {
    return q.size == 0
}
func (q MyCircularDeque) IsFull() bool {
    return q.size == q.capacity
}