设计循环队列

标签: 设计 队列 数组 链表

难度: Medium

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

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

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

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

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4

提示：

  • 所有的值都在 0 至 1000 的范围内；
  • 操作数将在 1 至 1000 的范围内；
  • 请不要使用内置的队列库。

Submission

运行时间: 46 ms

内存: 16.7 MB

class MyCircularQueue:

    def __init__(self, k: int):
        self.li = [0 for _ in range(k)]
        self.begin = 0
        self.end = 0
        self.size = 0
        self.limit = k


    def enQueue(self, value: int) -> bool:
        # 元素入队
        if self.isFull():
            return False
        else:
            # todo
            self.li[self.end] = value
            if self.end == self.limit - 1:
                self.end = 0
            else:
                self.end += 1
            self.size += 1
            return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        else:
            # todo
            if self.begin == self.limit - 1:
                self.begin = 0
            else:
                self.begin += 1
            self.size -= 1
            return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.li[self.begin]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            if self.end == 0:
                return self.li[self.limit-1]
            else:
                return self.li[self.end-1]

    def isEmpty(self) -> bool:
        return self.size == 0
        
    def isFull(self) -> bool:
        return self.size == self.limit


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

Explain

该题解设计了一个循环队列，使用一个固定大小的数组来存储队列元素，通过两个指针（begin和end）和一个size变量来管理队列的状态。当元素入队时，元素被放置在end指针的位置，并根据循环队列的性质调整end指针。当元素出队时，begin指针向前移动。特别地，当指针到达数组末尾时，会循环回数组的开始。通过这种方式，循环队列可以有效地利用数组的空间，避免了在普通队列中因为队列前端的空闲空间而无法继续添加元素的问题。

时间复杂度: O(1)

空间复杂度: O(k)

class MyCircularQueue:

    def __init__(self, k: int):
        self.li = [0 for _ in range(k)]  # 创建固定大小的数组
        self.begin = 0  # 初始化队列开始指针
        self.end = 0  # 初始化队列结束指针
        self.size = 0  # 初始化队列大小为0
        self.limit = k  # 队列的最大容量


    def enQueue(self, value: int) -> bool:
        # 元素入队
        if self.isFull():
            return False
        else:
            self.li[self.end] = value  # 将值存入end指针处
            if self.end == self.limit - 1:
                self.end = 0  # 循环回到数组开始
            else:
                self.end += 1  # 否则向后移动end指针
            self.size += 1  # 队列大小增加
            return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        else:
            if self.begin == self.limit - 1:
                self.begin = 0  # 循环回到数组开始
            else:
                self.begin += 1  # 否则向后移动begin指针
            self.size -= 1  # 队列大小减少
            return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.li[self.begin]  # 返回队首元素

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            if self.end == 0:
                return self.li[self.limit-1]  # 如果end为0，队尾在数组最后一个位置
            else:
                return self.li[self.end-1]  # 否则队尾为end指针前的位置

    def isEmpty(self) -> bool:
        return self.size == 0  # 检查队列是否为空

    def isFull(self) -> bool:
        return self.size == self.limit  # 检查队列是否已满

Explore

数组在实现循环队列时提供了几个优势。首先，使用数组可以通过索引直接访问任何元素，这使得操作如获取队首或队尾元素变得非常快捷和简单。其次，数组的内存是连续的，这有助于提高缓存的效率，从而可能使队列操作更快。相比之下，链表虽然在插入和删除操作时不需要移动其他元素，但每个节点需要额外的空间来存储指针，且节点间可能存在内存碎片，影响性能。因此，数组是一种空间和时间效率较平衡的选择。

在循环队列中，当`end`指针等于`limit - 1`并需要再次入队时，指针会循环回数组的开始。这种情况下，不会覆盖队首元素的保障来自于队列的`isFull`方法。在任何元素入队之前，`isFull`方法会检查队列是否已满（即`size`等于`limit`）。如果队列已满，则不允许入队，因此不会发生覆盖。如果队列未满，即使`end`指针回到数组开头，也意味着从`begin`指针到`end`指针之间还有未使用的空间，所以新元素放置在`end`指针的位置不会影响到队首元素。

在`deQueue`操作中，实际上并不需要将被删除的元素位置设置为特定的初始值或标记。这是因为循环队列的操作依赖于`begin`和`end`指针以及`size`变量来定义队列的有效范围和状态。元素被删除后，只需要正确更新`begin`指针和`size`变量。下次元素入队时，将自然地覆盖旧的、不再需要的值。因此，重置被删除的位置的值既不是必须的，也不影响队列的操作和性能。

在循环队列中，`end`指针指向下一个将要插入元素的位置。因此，如果`end`指针为0，这意味着最后一个元素已经被放在数组的最后一个位置，即`self.limit - 1`。这种设计确保了，不论`end`指针如何移动，`self.li[self.end - 1]`或当`end`为0时`self.li[self.limit - 1]`总是指向当前队列的最后一个有效元素。这样的逻辑保障了即使在循环使用数组的情况下，也能准确地返回队尾元素。