Python-数组实现循环队列和非循环队列

什么是队列？  队列就是只能在一端插入，而在另一端删除的线性表，故队列又称为先进先出队列 队列类型有哪些？ 循环队列和顺序队列  队列的存储实现方式有哪些？ 顺序存储（数组）和链式存储（链表），此博文描述的是数组的实现（后续更新链表实现）  代码实现 初始化队列：初始化一个size长度的队列，队列的值都为0 判断队列是否已满：队列满，不可插入队列 判断队列是否为空：队列空，没有数据可以出队 入队：将数据item插入队列 出队：将对头元素从队列中删除并返回的值 class Queue: """非循环队列""" def __init__(self, size): 队列是一种特殊的线性数据结构，它遵循“先进先出”（FIFO，First In First Out）的原则。在队列中，元素只能在队尾进行插入（enqueue）操作，而在队头进行删除（dequeue）操作。根据实现方式，队列可以分为循环队列和非循环队列。 1. **非循环队列**： 非循环队列的实现通常使用数组或链表。在这个例子中，我们看到一个基于数组的非循环队列类`Queue`。该类有以下方法： - `__init__(self, size)`：初始化队列，创建一个长度为`size`的数组，初始状态下队列的前后指针`front`和`rear`均设为-1。 - `enqueue(self, item)`：在队尾插入元素`item`。如果队列已满（`isFull()`返回True），则抛出异常。 - `dequeue(self)`：从队头删除元素并返回其值。如果队列为空（`isEmpty()`返回True），则抛出异常。 - `isFull(self)`：检查队列是否已满，当`rear - front == size`时返回True。 - `isEmpty(self)`：检查队列是否为空，当`rear == front`时返回True。 - `showQueue(self)`：打印队列中的所有元素。 2. **循环队列**： 循环队列在空间利用率上优于非循环队列，它通过利用数组的循环特性来避免队列满或空的情况。这个例子中有一个基于数组的循环队列类`circleQueue`： - `__init__(self, size)`：初始化队列，创建一个长度为`size`的数组，前后指针`front`和`rear`均设为0。 - `enQueue(self, item)`：在队尾插入元素`item`。如果队列已满（`isFull()`返回True），则抛出异常。这里使用了取模运算确保在循环数组中的正确位置插入。 - `deQueue(self)`：从队头删除元素并返回其值。如果队列为空（`isEmpty()`返回True），则抛出异常。同样使用取模运算更新队头指针。 - `isEmpty(self)`：检查队列是否为空，当`rear == front`时返回True。 - `isFull(self)`：检查队列是否已满，当`(rear+1) % size == front`时返回True。 - `showQueue(self)`：打印队列中的所有元素。 测试用例展示了如何使用这些类创建和操作队列，包括插入、删除、检查队列状态以及显示队列内容。 在实际应用中，队列广泛用于任务调度、多线程同步、操作系统内核以及各种算法中。例如，在银行系统中，客户按照到达的顺序排队等待服务，这就是队列的典型应用。在计算机科学中，优先队列（如堆）则用于解决更复杂的问题，如Dijkstra算法或Prim算法。此外，循环队列在处理大数据流或实时系统中尤为有用，因为它可以有效地管理有限的存储资源。