数组队列与循环队列详解：原理、时间复杂度与 Python 实现

一、数组队列

1.1 队列特点

1. 队列也是一种线性的数据结构
2. 相比数组，队列操作的也是数组的子集
3. 只能从一端添加元素(队尾)，从另一端取出元素(队首)
4. 队列是一种先进先出的数据结构
5. First In First Out（FIFO）

1.2 队列图示

关于队列的理解可以结合生活中的实例，比如说排队：

1. 定义一个空的队列

2. 从队尾开始向队列中添加元素

3. 从队首取出元素

1.3 数组队列的基本实现

1. 定义队列接口

from abc import ABC, abstractmethod

class Queues(ABC):
    """
    队列接口定义
    """

    @abstractmethod
    def get_size(self):
        """获取队列中元素的个数"""
        pass

    @abstractmethod
    def is_empty(self):
        """判断队列中是否是空的"""
        pass

    @abstractmethod
    def enqueue(self, e):
        """向队列中添加一个元素(入队)"""
        pass

    @abstractmethod
    def dequeue(self):
        """从队列中删除一个元素(出队)"""
        pass

    @abstractmethod
    def get_front(self):
        """获取队首的元素"""
        pass

2. 编写数组队列实现类

from array_module import Array

class ArrayQueues(Queues):
    """
    数组队列实现类
    """

    def __init__(self, capacity=None):
        """
        构造器
        :param capacity: 队列容量
        """
        if capacity is not None:
            self.array = Array(capacity)
        else:
            self.array = Array()

    def get_size(self):
        """获取队列中的元素个数"""
        return self.array.get_size()

    def is_empty(self):
        """判断队列中是否为空"""
        return self.array.is_empty()

    def enqueue(self, e):
        """向队列中插入一个元素"""
        self.array.add_last(e)

    def dequeue(self):
        """从队列中删除一个元素"""
        return self.array.remove_first()

    def get_front(self):
        """查询队首的元素"""
        return self.array.get_first()

    def get_capacity(self):
        """获取队列的容量"""
        return self.array.get_capacity()

    def __str__(self):
        """重写__str__方法"""
        res = "Queues: front ["
        for i in range(self.array.get_size()):
            res += str(self.array.get(i))
            if i != self.array.get_size() - 1:
                res += ", "
        res += "] tail"
        return res

3. 编写测试类

from array_queues import ArrayQueues

def main():
    queues = ArrayQueues()

    for i in range(10):
        queues.enqueue(i)
        print(queues)
        if i % 3 == 2:
            queues.dequeue()
            print(queues)

if __name__ == "__main__":
    main()

---

二、循环队列

2.1 数组队列存在的问题

执行删除操作的时候，调用的是底层数组的删除方法，所有的元素都会发生位移，所以删除操作的时间复杂度将会是O(n)。

2.2 使用循环队列解决数组队列删除方法的时间复杂度问题

1. 解决时间复杂度的问题只需要解决执行删除操作的时候，数组底层发生的位移问题即可

2. 就像图示1那样在删除元素的时候数组底层的元素保持原有的位置不变就可以解决这个问题，这就是接下来要说的循环队列

2.3 循环队列原理图示

1. 创建一个空的队列

2. 维护front，tail两个属性

维护front，tail两个属性（front指向开始的元素；tail指向最后的元素），当front == tail的时候证明此队列是空的。

3. 向此队列中添加一个元素

4. 持续向队列中添加元素

5. 从此队列中删除一个元素

6. 持续删除队列中的元素

可以看到当持续的删除之后，底层数组的元素并没有发生位移，但是这并不能体现循环队列的特性，请往下看。

7. 触发循环队列

当队列中的元素数量已经达到最后数组的最后一个索引的时候，这个时候就会触发循环队列。

8. 维护tail属性

我们需要维护tail属性的执行，让其在到达数组的最大索引时自动指向数组的第一个元素。

9. 持续执行添加操作

在tail属性指向数组最大索引时持续执行添加操作。

10. 队列满的判断条件

当(tail+1) % C == front的时候我们就认为队列已经满了；同时(tail+1) % C == front也是我们在第九步执行循环的重要依据，而且我们在维护循环队列的时候有意识的浪费的一个存储空间。

2.4 循环队列代码实现

class LoopQueues(Queues):
    """
    循环队列实现类
    """

    def __init__(self, capacity=10):
        """
        构造器
        :param capacity: 队列容量，默认为10
        """
        # 声明一个列表作为数据容器
        self.data = [None] * (capacity + 1)

        # 声明front，tail属性，用来维护循环队列
        self.front = 0
        self.tail = 0

        # 声明队列的元素个数属性
        self.size = 0

    def get_capacity(self):
        """获取队列容量（因为有意识的浪费一个空间，所以data长度需要执行-1的操作）"""
        return len(self.data) - 1

    def is_empty(self):
        """判断队列是否为空"""
        return self.front == self.tail

    def enqueue(self, e):
        """入队"""
        if (self.tail + 1) % len(self.data) == self.front:
            self._resize(self.get_capacity() * 2)

        self.data[self.tail] = e
        self.tail = (self.tail + 1) % len(self.data)
        self.size += 1

    def dequeue(self):
        """出队"""
        if self.is_empty():
            raise ValueError("Cannot dequeue from empty queue.")

        ret = self.data[self.front]
        self.data[self.front] = None
        self.front = (self.front + 1) % len(self.data)
        self.size -= 1

        if self.size == self.get_capacity() // 4 and self.get_capacity() // 2 != 0:
            self._resize(len(self.data) // 2)

        return ret

    def get_front(self):
        """获取队首的元素"""
        if self.is_empty():
            raise ValueError("Queue is empty.")
        return self.data[self.front]

    def get_size(self):
        """获取队列中元素的个数"""
        return self.size

    def _resize(self, new_capacity):
        """队列扩容逻辑"""
        # 创建新的容器
        new_data = [None] * (new_capacity + 1)

        # 使用循环进行赋值
        for i in range(self.size):
            new_data[i] = self.data[(i + self.front) % len(self.data)]

        self.data = new_data
        self.front = 0
        self.tail = self.size

    def __str__(self):
        """重写__str__方法"""
        res = f"Queue: size = {self.size} , capacity = {self.get_capacity()}\n"
        res += "front ["

        i = self.front
        while i != self.tail:
            res += str(self.data[i])
            if (i + 1) % len(self.data) != self.tail:
                res += ", "
            i = (i + 1) % len(self.data)

        res += "] tail"
        return res

测试代码

from array_queues import ArrayQueues

def main():
    queues = ArrayQueues()

    for i in range(10):
        queues.enqueue(i)
        print(queues)
        if i % 3 == 2:
            queues.dequeue()
            print(queues)

if __name__ == "__main__":
    main()