### 顺序循环队列的实现 顺序循环队列是一种基于数组实现的队列，通过取模操作实现了队列首尾相连的效果。以下是使用 Python 实现顺序循环队列的基本运算代码： ```python class CircularQueue: def __init__(self, capacity): self.queue = [None] * capacity # 初始化固定长度的列表作为队列容器 self.front = 0 # 队头指针初始化为0 self.rear = 0 # 队尾指针初始化为0 self.size = 0 # 当前队列中元素的数量 def is_empty(self): # 判断队列是否为空 return self.size == 0 # 如果size等于0，则返回True[^1] def is_full(self): # 判断队列是否已满 return self.size == len(self.queue) # 如果当前数量等于容量，则返回True[^1] def enqueue(self, item): # 入队操作 if not self.is_full(): # 若未满则执行入队逻辑 self.queue[self.rear] = item self.rear = (self.rear + 1) % len(self.queue) # 更新rear并考虑循环特性 self.size += 1 # 增加队列中的元素计数器 else: # 否则抛出异常表示溢出 raise Exception('Queue is full') def dequeue(self): # 出队操作 if not self.is_empty(): # 若不为空则执行出队逻辑 item = self.queue[self.front] self.queue[self.front] = None # 清除该位置上的值 self.front = (self.front + 1) % len(self.queue) # 更新front并考虑循环特性 self.size -= 1 # 减少队列中的元素计数器 return item # 返回被移除的元素 else: # 否则抛出异常表示下溢 raise Exception('Queue is empty') ``` --- ### 链队列的实现 链队列是基于链表实现的一种动态队列结构，能够自动扩展存储空间而无需预先设定容量。以下是使用 Python 实现链队列的基本运算代码： ```python class Node: def __init__(self, data=None): self.data = data # 节点数据域 self.next = None # 下一节点引用 class LinkedListQueue: def __init__(self): self.head = None # 头结点初始为空 self.tail = None # 尾结点初始为空 self.size = 0 # 记录队列中元素的数量 def is_empty(self): # 判断队列是否为空 return self.size == 0 # 如果size等于0，则返回True[^1] def enqueue(self, item): # 入队操作 new_node = Node(item) # 创建新节点 if self.tail is None: # 如果tail为空说明队列为空 self.head = new_node # 新节点成为head和tail self.tail = new_node else: # 否则将新节点连接到tail后面 self.tail.next = new_node self.tail = new_node # 并更新tail指向新的尾部 self.size += 1 # 增加队列中的元素计数器 def dequeue(self): # 出队操作 if not self.is_empty(): # 如果队列非空 removed_item = self.head.data # 获取要删除的头部节点的数据 self.head = self.head.next # 移动head至下一节点 if self.head is None: # 如果此时head变为空，则也需置tail为空 self.tail = None self.size -= 1 # 减少队列中的元素计数器 return removed_item # 返回被移除的元素 else: # 否则抛出异常表示下溢 raise Exception('Queue is empty') ``` --- ### 性能分析 对于顺序循环队列而言，由于其依赖于固定的数组大小，在扩容方面不如链队灵活；然而它的存取速度较快，适合处理规模相对稳定的场景。 而对于链队列来说，它具有更好的灵活性，可以随时增加或减少节点来适应需求变化，但是每次新增或者释放内存都会带来一定的开销[^2]。 此外需要注意的是，无论是哪种类型的队列实现方式都应关注算法的时间复杂度以及稳定性等问题[^3]。 --- ####