Python中如何实现循环双端队列

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

实现循环双端队列需要满足以下几个要点：

  1. 使用数组保存数据；
  2. 维护队头指针front和队尾指针rear；
  3. 队列为空时，front和rear应该指向同一位置；
  4. 在队列满时，需要进行扩容或缩容操作；
  5. 在插入和删除元素时，需要判断队列是否为空或已满。

下面是一个Python实现的循环双端队列代码示例：

class CircularDeque:
    def __init__(self, k: int):
        self.k = k  # 队列的容量
        self.q = [0] * k  # 使用数组存储数据
        self.front = 0  # 队头指针
        self.rear = 0  # 队尾指针

    def insertFront(self, value: int) -> bool:
        # 插入元素到队头
        if self.isFull():
            return False
        self.front = (self.front - 1 + self.k) % self.k  # 改变队头指针
        self.q[self.front] = value
        return True

    def insertLast(self, value: int) -> bool:
        # 插入元素到队尾
        if self.isFull():
            return False
        self.q[self.rear] = value
        self.rear = (self.rear + 1) % self.k  # 改变队尾指针
        return True

    def deleteFront(self) -> bool:
        # 删除队头元素
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.k
        return True

    def deleteLast(self) -> bool:
        # 删除队尾元素
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1 + self.k) % self.k
        return True

    def getFront(self) -> int:
        # 获取队头元素
        if self.isEmpty():
            return -1
        return self.q[self.front]

    def getRear(self) -> int:
        # 获取队尾元素
        if self.isEmpty():
            return -1
        return self.q[(self.rear - 1 + self.k) % self.k]

    def isEmpty(self) -> bool:
        # 判断队列是否为空
        return self.front == self.rear

    def isFull(self) -> bool:
        # 判断队列是否已满
        return (self.rear + 1) % self.k == self.front

可以通过以下代码进行测试：

deque = CircularDeque(3)
print(deque.insertLast("pidancode.com"))  # True
print(deque.insertLast("皮蛋编程"))  # True
print(deque.insertLast("test"))  # False，队列已满

print(deque.getFront())  # pidancode.com
print(deque.getRear())  # 皮蛋编程

print(deque.deleteLast())  # True
print(deque.getRear())  # pidancode.com

print(deque.deleteFront())  # True
print(deque.getFront())  # 皮蛋编程

相关文章