leetcode链表之设计循环队列

622、设计循环队列

题目：

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

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

---

思路：

使用数组加下标实现

代码：

class MyCircularQueue:
        # 设计k大小的数组，count是当前队列的实际大小，headIndex是当前头指针位置
    def __init__(self, k: int):
        self.queue = [0] * k
        self.headIndex = 0
        self.count = 0
        self.capacity = k


    def enQueue(self, value: int) -> bool:
        if self.count == self.capacity:
            return False
        # 往队尾添加数据，队尾到队首的距离为 count - 1
        # 从队首往后移count位置，即是要插入的位置
        self.queue[(self.headIndex + self.count) % self.capacity] = value
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.count == 0:
            return False
        # 从队首删除数据，此时只需要将队首往后移一位，并将实际大小减一即可
        self.headIndex = (self.headIndex + 1) % self.capacity
        self.count -= 1
        return True


    def Front(self) -> int:
        if self.count == 0:
            return -1
        # 获取队首元素
        return self.queue[self.headIndex]

    def Rear(self) -> int:
        if self.count == 0:
            return -1
        # 获取队尾元素，由于队尾和队首的距离是count - 1
        return self.queue[(self.headIndex + self.count - 1) % self.capacity]
        pass

    def isEmpty(self) -> bool:
        return self.count == 0


    def isFull(self) -> bool:
        return self.count == self.capacity

641、设计循环双端队列

题目：

设计实现双端队列。

实现 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 。

---

思路：

class MyCircularDeque:
        # 初始化和循环队列一样
    def __init__(self, k: int):
        self.queue = [0] * k
        self.count = 0
        self.capacity = k
        self.headIndex = 0

    def insertFront(self, value: int) -> bool:
        if self.count == self.capacity:
            return False
        # 这里要注意，如果队首结点在0下标，此时往队首插入数据，那么新的队首就是整个数组的队尾了
        # 原始写法
        # if self.headIndex == 0:
        #     self.headIndex = self.capacity - 1
        # else:
        #     self.headIndex = self.headIndex - 1
        self.headIndex = (self.headIndex or self.capacity) - 1
        self.queue[self.headIndex] = value
        self.count += 1
        return True
        # 队尾插入元素和循环队列enQueue一样
    def insertLast(self, value: int) -> bool:
        if self.count == self.capacity:
            return False
        self.queue[(self.headIndex + self.count) % self.capacity] = value
        self.count += 1
        return True
        # 删除队首元素，需要将队首往后移动意味，实际大小减一
    def deleteFront(self) -> bool:
        if self.count == 0:
            return False
        self.headIndex = (self.headIndex + 1) % self.capacity
        self.count -= 1
        return True
        # 删除队尾数据，只需要将实际大小减一即可，队首不用移动
    def deleteLast(self) -> bool:
        if self.count == 0:
            return False
        self.count -= 1
        return True

    def getFront(self) -> int:
        if self.count == 0:
            return -1
        return self.queue[self.headIndex]

    def getRear(self) -> int:
        if self.count == 0:
            return -1
        return self.queue[(self.headIndex + self.count - 1) % self.capacity]

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.capacity