641. Design Circular Deque 设计循环双端队列-6ren

641. Design Circular Deque 设计循环双端队列

转载作者：大佬之路更新时间：2024-01-31 14:18:40

24

4

题目地址：https://leetcode.com/problems/design-circular-deque/description/

题目描述：

Design your implementation of the circular double-ended queue (deque). Your implementation should support following operations:

MyCircularDeque(k): Constructor, set the size of the deque to be k.
insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
getRear(): Gets the last item from Deque. If the deque is empty, return -1.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.

Example:

MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);			// return true
circularDeque.insertLast(2);			// return true
circularDeque.insertFront(3);			// return true
circularDeque.insertFront(4);			// return false, the queue is full
circularDeque.getRear();  				// return 32
circularDeque.isFull();				// return true
circularDeque.deleteLast();			// return true
circularDeque.insertFront(4);			// return true
circularDeque.getFront();				// return 4

Note:

All values will be in the range of [1, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Deque library.

题目大意

实现一个双向环形链表。

解题方法

使用列表

和622. Design Circular Queueopen in new window很类似了，622题要求的是单向的环形链表，这个题要求是双向的。

做法同样是采用和622题目类似的“作弊”做法，用一个list实现类似的环形列表。因为是双向链表，所以可以从头尾插入元素，对应了list的insert和append方法。

特别注意的是，插入元素，无论是在头尾插入，要移动的指针都是rear。

我这个题的做法比622更加成熟一点，622是通过头部指针来实现的，这个题里面是直接操作的头部元素导致后面的元素跟着变化，头部指针没有用到。。

这么一说可以把头部指针删除了23333.

在这么一说发现rear一直指向的是list的结尾，所以也可以删除了23333.

没删除头部指针的代码如下：

class MyCircularDeque(object):

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        :type k: int
        """
        self.queue = []
        self.size = k
        self.front = 0
        self.rear = 0

    def insertFront(self, value):
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.insert(0, value)
            self.rear += 1
            return True
        else:
            return False
        

    def insertLast(self, value):
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.append(value)
            self.rear += 1
            return True
        else:
            return False

    def deleteFront(self):
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop(0)
            self.rear -= 1
            return True
        else:
            return False

    def deleteLast(self):
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop()
            self.rear -= 1
            return True
        else:
            return False

    def getFront(self):
        """
        Get the front item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.front]

    def getRear(self):
        """
        Get the last item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.rear -1]

    def isEmpty(self):
        """
        Checks whether the circular deque is empty or not.
        :rtype: bool
        """
        return self.front == self.rear

    def isFull(self):
        """
        Checks whether the circular deque is full or not.
        :rtype: bool
        """
        return self.rear - self.front == self.size
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

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 102 103 104 105 106 107 108

其实可以删除头指针，因为头指针一直指向0.

删除头部指针的代码如下：

class MyCircularDeque(object):

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        :type k: int
        """
        self.queue = []
        self.size = k
        self.rear = 0

    def insertFront(self, value):
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.insert(0, value)
            self.rear += 1
            return True
        else:
            return False
        

    def insertLast(self, value):
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.append(value)
            self.rear += 1
            return True
        else:
            return False

    def deleteFront(self):
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop(0)
            self.rear -= 1
            return True
        else:
            return False

    def deleteLast(self):
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop()
            self.rear -= 1
            return True
        else:
            return False

    def getFront(self):
        """
        Get the front item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[0]

    def getRear(self):
        """
        Get the last item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.rear -1]

    def isEmpty(self):
        """
        Checks whether the circular deque is empty or not.
        :rtype: bool
        """
        return 0 == self.rear

    def isFull(self):
        """
        Checks whether the circular deque is full or not.
        :rtype: bool
        """
        return self.rear == self.size
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

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 102 103 104 105 106 107

rear 始终等于 len(self.queue)，所以完全可以删除。

删除front和rear指针的代码如下：

class MyCircularDeque(object):

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        :type k: int
        """
        self.queue = []
        self.size = k

    def insertFront(self, value):
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.insert(0, value)
            return True
        else:
            return False
        

    def insertLast(self, value):
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.append(value)
            return True
        else:
            return False

    def deleteFront(self):
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop(0)
            return True
        else:
            return False

    def deleteLast(self):
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop()
            return True
        else:
            return False

    def getFront(self):
        """
        Get the front item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[0]

    def getRear(self):
        """
        Get the last item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[-1]

    def isEmpty(self):
        """
        Checks whether the circular deque is empty or not.
        :rtype: bool
        """
        return 0 == len(self.queue)

    def isFull(self):
        """
        Checks whether the circular deque is full or not.
        :rtype: bool
        """
        return self.size == len(self.queue)
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

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 102

双向链表

上面的解法直接使用了内置数据结构list，在头部插入的效率比较慢，时间复杂度是O(N)！所以我使用了双向链表模拟deque.

维护双向链表的方式和STL的list一样。对啊，可以直接用List。。方法就不仔细讲了。

struct Node {
    Node* prev;
    Node* next;
    int val;
    Node(int v) : val(v) {};
};
struct List {
    Node* dummy;
    int size;
    List() : size(0) {
        dummy = new Node(0);
        dummy->next = dummy;
        dummy->prev = dummy;
    };
};
class MyCircularDeque {
public:
    /** Initialize your data structure here. Set the size of the deque to be k. */
    MyCircularDeque(int k) {
        maxSize = k;
    }
    
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    bool insertFront(int value) {
        if (list.size == maxSize)
            return false;
        Node* cur = new Node(value);
        Node* prev = list.dummy->prev;
        list.dummy->prev = cur;
        cur->prev = prev;
        prev->next = cur;
        cur->next = list.dummy;
        ++list.size;
        return true;
    }
    
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    bool insertLast(int value) {
        if (list.size == maxSize)
            return false;
        Node* cur = new Node(value);
        Node* next = list.dummy->next;
        list.dummy->next = cur;
        cur->next = next;
        next->prev = cur;
        cur->prev = list.dummy;
        ++list.size;
        return true;
    }
    
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    bool deleteFront() {
        if (list.size == 0) return false;
        Node* prev = list.dummy->prev;
        Node* pprev = prev->prev;
        list.dummy->prev = pprev;
        pprev->next = list.dummy;
        --list.size;
        return true;
    }
    
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    bool deleteLast() {
        if (list.size == 0) return false;
        Node* next = list.dummy->next;
        Node* nnext = next->next;
        list.dummy->next = nnext;
        nnext->prev = list.dummy;
        --list.size;
        return true;
    }
    
    /** Get the front item from the deque. */
    int getFront() {
        if (list.size == 0) return -1;
        return list.dummy->prev->val;
    }
    
    /** Get the last item from the deque. */
    int getRear() {
        if (list.size == 0) return -1;
        return list.dummy->next->val;
    }
    
    /** Checks whether the circular deque is empty or not. */
    bool isEmpty() {
        return list.size == 0;
    }
    
    /** Checks whether the circular deque is full or not. */
    bool isFull() {
        return list.size == maxSize;
    }
private:
    List list;
    int maxSize;
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * bool param_1 = obj.insertFront(value);
 * bool param_2 = obj.insertLast(value);
 * bool param_3 = obj.deleteFront();
 * bool param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * bool param_7 = obj.isEmpty();
 * bool param_8 = obj.isFull();
 */

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 102 103 104 105 106 107 108 109 110

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛授权发布，任何组织或个人未经作者授权不得转发

24

4

0

文章推荐： 647. Palindromic Substrings 回文子串

文章推荐： 628. Maximum Product of Three Numbers 三个数的最大乘积

文章推荐： 633. Sum of Square Numbers 平方数之和

文章推荐： 636. Exclusive Time of Functions 函数的独占时间

user-interface - 交互设计、视觉设计、网页设计、UX 设计、UI 设计、UI 开发之间有什么区别？
关闭。这个问题需要更多focused .它目前不接受答案。想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post . 4年前关闭。 Improve this questi
wpf - 仅适用于 VS 设计 View 的 Blend 中的 UnresolvedAssemblyException - 在 VS 设计 View 中工作正常
.NET 框架:4.5.1 我在 Blend for visual studio 2015 中遇到一个奇怪的错误，我找不到它的来源。如果我在 VS 中打开我的 WPF 解决方案，它会加载并运行良好。
web-services - RESTful URL 设计 : public vs private API, 层次结构 API 设计模式，URI 与 URL 设计？
我经常遇到这样的问题，与 Hierarchical RESTful URL design 非常相似假设该服务仅提供用户上传文档。 POST, GET /accounts PUT, DELETE /a
设计，无法登出
在 Rails 应用程序中，我使用 devise 来管理我的用户，而我用来销毁 session 的链接不再有效。它正在工作，现在我添加了事件管理员，但没有。我的链接是 :delete, :clas
设计:更改密码
我已经坚持了超过 24 小时，试图按照此处发布的其他解决方案进行操作，但我无法使其正常工作。我是 Rails 新手，需要帮助! 我想让我的/users/edit 页面正常工作，以便我可以简单地更改用户
设计 - 超时不起作用
Devise 在以下情况下不会使用户超时: 用户登录，关闭选项卡，然后在超时 + X 分钟内重新访问该 URL。用户仍处于登录状态。如果选项卡已打开并且稍后刷新/单击，则超时可以正常工作。这意味着
WPF slider 设计
我想使用这样的 slider 我希望该 slider 根据提供给它的值进行相应调整。到目前为止，我只能应用具有渐变效果的背景，但无法获得这种效果。请通过提供样式代码来帮助我。
WCF 设计 - 一个请求和响应对象还是多个？
您应该为每种方法创建一个请求/响应对象，还是应该为每个服务创建一个？如果我在所有方法中使用它，我的服务请求对象中将只有 5 个不同的东西，因为我对几乎所有方法使用相同的输入。响应对象将只有一个字典
RESTful 设计 - 如何为实体的附件建模
我正在尝试在 REST 中对实体的附件进行建模。假设一个缺陷实体可以附加多个附件。每个附件都有描述和一些其他属性(上次修改时间、文件大小...)。附件本身是任何格式的文件(jpeg、doc ...)
sql - 设计——第六范式
我有以下表格: Blogs { BlogName } BlogPosts { BlogName, PostTitle } 博客文章同时建模一个实体和一个关系，根据 6nf(根据第三个宣言)这是无效的。
OOP 设计 - 许多对象每个都与其他对象的有限子集具有独特的交互
如果 A 类与 B、C 和 D 类中的每一个都有唯一的交互，那么交互的代码应该在 A 中还是在 B、C 和 D 中？我正在编写一个小游戏，其中许多对象可以与其他对象进行独特的交互。例如，EMP点击
设计 + Omniauth + remember_me
关于如何记住我与 Omniauth 一起工作似乎有些困惑。根据这个wiki ，您需要在 OmniauthCallbacksController 中包含以下内容: remember_me(user)
multithreading - 将非线程安全组件与多线程组件一起使用(设计)
设计问题: 使用非线程安全组件(集合，API，...)在/带有多线程成分 ... 例子 : 组件 1 :多线程套接字服务器谁向消息处理程序发送消息... 组件 2 :非线程安全消息处理程序谁
XML 设计 - 如何？
我们目前正在设计一个 RESTful 应用程序。我们决定使用 XML 作为我们的基本表示。我有以下关于在 XML 中设计/建模应用程序数据的问题。在 XML 中进行数据建模的方法有哪些？从头开始然
XSD 设计 - 一个或多个规则
我正在设计一个新的 XSD 来从业务合作伙伴那里获取积分信息。对于每笔交易，合作伙伴必须提供至少一种积分类型的积分值。我有以下几点:
API 设计 - 最佳实践以及如何支持多个版本
设计支持多个版本的 API 的最佳方法是什么。我如何确保即使我的数据架构发生更改(微小更改)，我的 api 的使用者也不会受到影响？任何引用架构、指南都非常有用。最佳答案 Mark Nottingh
文件上传的 REST 设计
关闭。这个问题是opinion-based 。目前不接受答案。想要改进这个问题吗？更新问题，以便 editing this post 可以用事实和引文来回答它。 . 已关闭 4 年前。 Improv
PHP 文件布局/设计
我想用 php 创建一个网站，其工作方式与 https://www.bitcoins.lc/ 相同。确实，就每个页面上具有相同布局但内容会随着您更改链接/页面而改变而言，我如何在 php 中使用lay
Java Swing 设计
我有一个关于编写 Swing UI 的问题。如果我想制作一个带有某些选项的软件，例如在第一个框架上，我有三个按钮(新建、选项、退出)。现在，如果用户单击新按钮，我想将框架中的整个内容更改为其他内容。
docker - Kubernetes建筑/设计/？
我正在尝试找出并学习将应用程序拥有的一堆Docker容器移至Kubernetes的模式和最佳实践。诸如Pod设计，服务，部署之类的东西。例如，我可以创建一个其中包含单个Web和应用程序容器的Pod，但

首页

博学

6Ren·AI

商城