Python中如何实现循环队列

2023-04-11 00:00:00 队列循环如何实现

循环队列实现的关键是如何在数组中实现队列的循环操作，即队列满时如何将元素加入到队首。一种常用的方法是将队列尾部的下一个位置作为队首，即将下一个位置视为“循环回起点”。这样当队列满时，插入在队尾将导致队列绕一圈到达队首。另外，队列为空时队首和队尾重合，可以通过设定一个变量来判断队列是否为空。

代码演示如下：

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.head = 0
        self.tail = 0
        self.size = 0

    def enqueue(self, item):
        if self.is_full():
            raise Exception("Queue is full")
        self.queue[self.tail] = item
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        item = self.queue[self.head]
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return item

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacity

    def __len__(self):
        return self.size

# 示例
q = CircularQueue(6)
q.enqueue("pidan")
q.enqueue("code")
q.enqueue("com")
q.enqueue("is")
q.enqueue("a")
q.enqueue("website")
print(len(q)) # 输出 6
try:
    q.enqueue("oops")
except Exception as e:
    print(str(e))  # 输出 "Queue is full"
print(q.dequeue()) # 输出 "pidan"
print(q.dequeue()) # 输出 "code"
print(q.dequeue()) # 输出 "com"
print(len(q)) # 输出 3
print(q.dequeue()) # 输出 "is"
print(q.dequeue()) # 输出 "a"
print(q.dequeue()) # 输出 "website"
try:
    print(q.dequeue())
except Exception as e:
    print(str(e))  # 输出 "Queue is empty"

相关文章