641 设计循环双端队列（模拟）

深藏阁楼爱情的钟 2022-08-29 04:30 203阅读 0赞

**1. 问题描述：**

设计实现双端队列。你的实现需要支持以下操作：  
MyCircularDeque(k)：构造函数,双端队列的大小为k。  
insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。  
insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。  
deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。  
deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。  
getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。  
getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。  
isEmpty()：检查双端队列是否为空。  
isFull()：检查双端队列是否满了。

**示例：**

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, 1000\]  
操作次数的范围为 \[1, 1000\]  
请不要使用内置的双端队列库。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/design-circular-deque

**2. 思路分析：**

这道题目与力扣[622][]题是类似的，只是这里多了几个操作，其余的都是类似的，我们使用数组或者列表来模拟循环队列中的添加元素和删除元素的操作即可，若队头与队尾分别为h和t，分情况讨论即可：

*  当h = t的时候，队头与队尾在同一个位置表示队空
 *  当h != t的时候，区间\[h, t - 1\]为队列中的元素，最后一个位置t不存元素
 *  当t = h - 1的时候表示队满

**3. 代码如下：**

class MyCircularDeque:
        h, t = 0, 0
        q = None
    
        def __init__(self, k: int):
            self.q = [0] * (k + 1)
    
        def insertFront(self, value: int) -> bool:
            if self.isFull(): return False
            h = self.get(self.h - 1)
            self.q[h] = value
            self.h = h
            return True
    
        def insertLast(self, value: int) -> bool:
            if self.isFull(): return False
            self.q[self.t] = value
            self.t = self.get(self.t + 1)
            return True
    
        def deleteFront(self) -> bool:
            if self.isEmpty(): return False
            self.h = self.get(self.h + 1)
            return True
    
        def deleteLast(self) -> bool:
            if self.isEmpty(): return False
            self.t = self.get(self.t - 1)
            return True
    
        def getFront(self) -> int:
            if self.isEmpty(): return -1
            return self.q[self.h]
    
        def getRear(self) -> int:
            if self.isEmpty(): return -1
            return self.q[self.get(self.t - 1)]
    
        def get(self, x: int):
            return (x + len(self.q)) % len(self.q)
    
        def isEmpty(self) -> bool:
            return self.get(self.h) == self.get(self.t)
    
        def isFull(self) -> bool:
            return self.get(self.h) == self.get(self.t) + 1

[622]: https://blog.csdn.net/qq_39445165/article/details/119174011