使用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方法的实现。