使用Python语言实现一个基于动态数组的序列队列
一、动态数组的实现
- 首先，我们需要创建一个
DynamicArray类，该类将管理我们的动态数组。- 动态数组能够动态地调整其大小，以容纳更多的元素。
目录
一、动态数组的实现
代码示例：
二、序列队列的实现
接下来，我们基于DynamicArray类实现SeqQueue类。序列队列将提供标准的队列操作，如入队、出队、检查队列是否为空等。
-
代码示例：
class DynamicArray: def __init__(self, initial_capacity=10): """初始化动态数组，设置初始容量""" self.capacity = initial_capacity self.size = 0 self.array = [None] * self.capacity def is_empty(self): """检查动态数组是否为空""" return self.size == 0 def is_full(self): """检查动态数组是否已满""" return self.size == self.capacity def resize(self, new_capacity): """调整动态数组的大小""" new_array = [None] * new_capacity for i in range(self.size): new_array[i] = self.array[i] self.array = new_array self.capacity = new_capacity def insert(self, index, data): """在指定索引处插入数据""" if self.is_full(): self.resize(self.capacity * 2) # 扩容 if index < 0 or index > self.size: raise IndexError("Index out of range") for i in range(self.size, index, -1): self.array[i] = self.array[i - 1] self.array[index] = data self.size += 1 def remove(self, index): """移除指定索引处的数据""" if self.is_empty(): raise IndexError("Cannot remove from an empty array") if index < 0 or index >= self.size: raise IndexError("Index out of range") for i in range(index, self.size - 1): self.array[i] = self.array[i + 1] self.array[self.size - 1] = None self.size -= 1 if self.size > 0 and self.size == self.capacity // 4: # 缩容 self.resize(self.capacity // 2) def get(self, index): """获取指定索引处的数据""" if index < 0 or index >= self.size: raise IndexError("Index out of range") return self.array[index] def __len__(self): """返回动态数组的大小""" return self.size二、序列队列的实现
-
接下来，我们基于
DynamicArray类实现SeqQueue类。序列队列将提供标准的队列操作，如入队、出队、检查队列是否为空等。
class SeqQueue: def __init__(self, initial_capacity=10): """初始化序列队列，设置初始容量""" self.queue = DynamicArray(initial_capacity) def is_empty(self): """检查队列是否为空""" return self.queue.is_empty() def enqueue(self, item): """入队操作，将元素添加到队列末尾""" self.queue.insert(self.queue.size, item) def dequeue(self): """出队操作，移除并返回队列的第一个元素""" if self.is_empty(): raise IndexError("Dequeue from an empty queue") return self.queue.remove(0) def size(self): """返回队列中元素的数量""" return len(self.queue) def front(self): """返回队列的第一个元素，但不移除它""" if self.is_empty(): raise IndexError("Queue is empty") return self.queue.get(0) def back(self): """返回队列的最后一个元素，但不移除它""" if self.is_empty(): raise IndexError("Queue is empty") return self.queue.get(self.queue.size - 1)def destroy(self): self.queue = None # 使用示例 max_size = 10 seq_queue = SeqQueue(max_size) # 入队 seq_queue.push("data1") seq_queue.push("data2") # 获取队首元素 print(seq_queue.front()) # 输出: data1 # 获取队尾元素 print(seq_queue.back()) # 输出: data2 # 出队 seq_queue.pop() # 再次获取队首元素 print(seq_queue.front()) # 输出: data2 # 销毁队列 seq_queue.destroy()在这个文件中，
DynamicArray类定义了一个动态数组，而SeqQueue类则定义了一个基于DynamicArray的序列队列。您可以直接运行这个文件来测试这些类的功能。请注意，这个示例假设您希望队列在出队时返回被移除的元素，所以pop方法现在返回被移除的元素。如果您不希望这样，您可以相应地调整pop方法的实现。