• 【641. 设计循环双端队列】

    来源：力扣（LeetCode）

    描述：

    设计实现双端队列。

    实现 MyCircularDeque 类:

    • MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
    • boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
    • boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
    • boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
    • boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
    • int getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
    • int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
    • boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
    • boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

    示例 1：

    输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);			        // 返回 true
circularDeque.insertLast(2);			        // 返回 true
circularDeque.insertFront(3);			        // 返回 true
circularDeque.insertFront(4);			        // 已经满了，返回 false
circularDeque.getRear();  						// 返回 2
circularDeque.isFull();				        	// 返回 true
circularDeque.deleteLast();			        	// 返回 true
circularDeque.insertFront(4);			        // 返回 true
circularDeque.getFront();						// 返回 4

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    提示：

    • 1 <= k <= 1000
    • 0 <= value <= 1000
    • insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于 2000 次

    方法一：链表

    我们可以使用双向链表来模拟双端队列，实现双端队列队首与队尾元素的添加、删除。双向链表实现比较简单，双向链表支持 O(1) 时间复杂度内在指定节点的前后插入新的节点或者删除新的节点。
    1
    循环双端队列的属性如下:

    • head：队列的头节点；
    • tail：队列的尾节点
    • capacity：队列的容量大小。
    • size：队列当前的元素数量。

    循环双端队列的接口方法如下：

    • MyCircularDeque(int k)：初始化队列，同时初始化队列元素数量 size 为 0。head,tail 初始化为空。
    • insertFront(int value)：队列未满时，在队首头结点 head 之前插入一个新的节点，并更新 head，并更新 size。
    • insertLast(int value)：队列未满时，在队尾节点tail 之后插入一个新的节点，并更新 tail，并更新 size。
    • deleteFront()：队列不为空时，删除头结点 head，并更新head 为 head 的后一个节点，并更新 size。
    • deleteLast()：队列不为空时，删除尾结点 tail，并更新tail 为 tail 的前一个节点，并更新 size。
    • getFront()：返回队首节点指向的值，需要检测队列是否为空。
    • getRear()：返回队尾节点指向的值，需要检测队列是否为空。
    • isEmpty()：检测当前 size 是否为 0。
    • isFull()：检测当前 size 是否为 capacity。

    代码：

    struct DLinkListNode {
    int val;
    DLinkListNode *prev, *next;
    DLinkListNode(int _val): val(_val), prev(nullptr), next(nullptr) {

    }
};

class MyCircularDeque {
private:
    DLinkListNode *head, *tail;
    int capacity;
    int size;

public:
    MyCircularDeque(int k): capacity(k), size(0), head(nullptr), tail(nullptr) {
        
    }

    bool insertFront(int value) {
        if (size == capacity) {
            return false;
        }
        DLinkListNode *node = new DLinkListNode(value);
        if (size == 0) {
            head = tail = node;
        } else {
            node->next = head;
            head->prev = node;
            head = node;
        }
        size++;
        return true;
    }

    bool insertLast(int value) {
        if (size == capacity) {
            return false;
        }
        DLinkListNode *node = new DLinkListNode(value);
        if (size == 0) {
            head = tail = node;
        } else {
            tail->next = node;
            node->prev = tail;
            tail = node;
        }
        size++;
        return true;
    }

    bool deleteFront() {
        if (size == 0) {
            return false;
        }
        DLinkListNode *node = head;
        head = head->next;
        if (head) {
            head->prev = nullptr;
        }
        delete node;
        size--;
        return true;
    }

    bool deleteLast() {
        if (size == 0) {
            return false;
        }
        DLinkListNode *node = tail;
        tail = tail->prev;
        if (tail) {
            tail->next = nullptr;
        }
        delete node;
        size--;
        return true;
    }

    int getFront() {
        if (size == 0) {
            return -1;
        }
        return head->val;
    }

    int getRear() {
        if (size == 0) {
            return -1;
        }
        return tail->val;
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101

    执行用时：32 ms, 在所有 C++ 提交中击败了13.15%的用户
    内存消耗：16.5 MB, 在所有 C++ 提交中击败了18.52%的用户
    复杂度分析
    时间复杂度：初始化和每项操作的时间复杂度均为 O(1)。
    空间复杂度：O(k)，其中 k 为给定的队列元素数目。

    方法二：数组

    可以参考循环队列：「622. 设计循环队列」，我们利用循环队列实现双端队列。在循环队列中的基础上，我们增加 insertFront 和 deleteFront 函数实现即可。根据循环队列的定义，队列判空的条件是 front = rear，而队列判满的条件是 front = (rear + 1)modcapacity。

    对于一个固定大小的数组，只要知道队尾 rear 与队首 front，即可计算出队列当前的长度：

    (rear − front + capacity)modcapacity

    循环双端队列与循环队列的属性一致:

    • elements：一个固定大小的数组，用于保存循环队列的元素。
    • capacity：循环队列的容量，即队列中最多可以容纳的元素数量。
    • front：队列首元素对应的数组的索引。
    • rear：队列尾元素对应的索引的下一个索引。

    循环双端队列的接口方法如下：

    • MyCircularDeque(int k)：初始化队列，同时base 数组的空间初始化大小为 k + 1。front,rear 全部初始化为 0。
    • insertFront(int value)：队列未满时，在队首插入一个元素。我们首先将队首 front 移动一个位置，更新队首索引为 front 更新为 (front − 1 + capacity)modcapacity。
    • insertLast(int value)：队列未满时，在队列的尾部插入一个元素，并同时将队尾的索引 rear 更新为 (rear + 1)modcapacity。
    • deleteFront()：队列不为空时，从队首删除一个元素，并同时将队首的索引 front 更新为(front + 1)modcapacity。
    • deleteLast()：队列不为空时，从队尾删除一个元素。并同时将队尾的索引 rear 更新为 (rear − 1 + capacity)modcapacity。
    • getFront()：返回队首的元素，需要检测队列是否为空。
    • getRear()：返回队尾的元素，需要检测队列是否为空。
    • isEmpty()：检测队列是否为空，根据之前的定义只需判断 rear 是否等于 front。
    • isFull()：检测队列是否已满，根据之前的定义只需判断 front 是否等于 (rear + 1)modcapacity。

    代码：

    class MyCircularDeque {
private:
    vector<int> elements;
    int rear, front;
    int capacity;

public:
    MyCircularDeque(int k) {
        capacity = k + 1;
        rear = front = 0;
        elements = vector<int>(k + 1);
    }

    bool insertFront(int value) {
        if (isFull()) {
            return false;
        }
        front = (front - 1 + capacity) % capacity;
        elements[front] = value;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }   

    bool isEmpty() {
        return rear == front;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    执行用时：20 ms, 在所有 C++ 提交中击败了90.42%的用户
    内存消耗：16.3 MB, 在所有 C++ 提交中击败了67.82%的用户
    复杂度分析
    时间复杂度：初始化和每项操作的时间复杂度均为 O(1)。
    空间复杂度：O(k)，其中 k 为给定的队列元素数目。
    author：LeetCode-Solution

  • 相关阅读:
    虚拟机与主机(win10之间的通信)
    高通8295中国首发！智舱再度上演「军备竞赛」，这次有何不同
    BF算法与KMP模式匹配算法（画图详解，C语言实现）
    Spring注解中的@DependsOn是什么意思
    CNN卷积神经网络Python实现
    深入浅出Flask PIN
    C#-多线程
    Docker常用安装和推送云库
    ext2文件系统体会-xattr
    MongoDB聚合运算符：$week
  • 原文地址：https://blog.csdn.net/Sugar_wolf/article/details/126341410