Python Queue 队列 数据结构

Question

单链队列实现

使用 Python 中的列表 List 实现：

enqueue(item) —— 将一个元素入队（在队尾添加元素）

def enqueue(self, item):
  self.data.append(item)

dequeue() —— 将队首的元素出队，若队列为空则报错

def dequeue(self):
  if self.data:
    return self.data.pop(0)
  else:
    raise DequeueError("Queue is empty.")

size() —— 返回队列长度

is_empty() —— 判断队列是否为空

介绍

队列满足先进先出 FIFO 的原则。时间复杂度：出队列使用了列表的 pop(0) 方法，故时间复杂度为 O(n)；入队列采用了列表的 append() 方法，故时间复杂度为 O(1)

采用循环队列（Circular Queue），可以将出队和入队的时间复杂度都降到 O(1)。循环队列有一个最大长度max_size，仍然采用列表实现。两个成员变量front和rear分别为队首元素和下一个入队的元素在列表中的索引。为了区别队列为空和队列为满，列表大小应为length = max_size + 1，列表中最多只能有max_size个队列元素。

当进行入队操作时，先判断队列是否已满：(rear + 1) % length == front，一种方法是已满直接报错，另一种是若队列已满则扩容为原来的两倍。入队时，rear = (rear + 1) % max_size

进行出队操作时，先判断队列是否为空：front == rear，如果为空则报错。出队时，front = (front + 1) % max_size

获得当前队列长度：(rear - front + length) % length

使用循环队列的方法，由于入队和出队操作都是直接通过索引访问列表，所以时间复杂度都是 O(1)

循环队列

class CircularQueue:
  def __init__(self, max_size = 6):
    self.data = [None]*(max_size+1)
    self.front = 0
    self.rear = 0

get_max_size() —— 获得队列的最大长度

def get_max_size(self):
  return len(self.data) - 1

enqueue_strict(item) —— 入队操作，如果队列已满则报错

def enqueue_strict(self, item):
  if (self.rear+1) % len(self.data) == self.front:
    raise SizeError("Queue is full. Unable to enqueue.")
  self.data[self.rear] = item
  self.rear = (self.rear+1) % len(self.data)

dequeue_strict() —— 出队操作，如果队列为空则报错

def dequeue_strict(self):
  if self.front == self.rear:
    raise SizeError("Queue is empty. Unable to dequeue.")
  item = self.data[self.front]
  self.data[self.front] = None
  self.front = (self.front + 1) % len(self.data)

enqueue(item) —— 入队操作，如果已满则扩容为原来队列大小的两倍再入队

def enqueue(self, item):
  if (self.rear+1) % len(self.data) == self.front:
    self.resize(self.get_max_size() * 2)
  self.data[self.rear] = item
  self.rear = (self.rear+1) % len(self.data)

dequeue() —— 出队操作，检测如果队列大小等于列表大小的1/4，并且列表大小大于等于2，则减小列表大小为原来的一半以节省空间开销

def dequeue(self):
  if self.front == self.rear:
    raise SizeError("Queue is empty. Unable to dequeue.")
  item = self.data[self.front]
  self.data[self.front] = None
  self.front = (self.front + 1) % len(self.data)
  if self.size() == self.get_max_size()//4 and len(self.data) >= 2:
    self.resize(self.get_max_size() // 2)
  return item

size() —— 返回队列的当前大小

def size(self):
  return (self.rear - self.front + len(self.data)) % len(self.data)

is_empty() —— 判断队列是否为空

def is_empty(self):
  return self.front == self.rear

双端队列(Deque)

双端队列（Deque）与队列的区别就是，元素可以从两端插入，也可以从两端删除；具备队列与栈的特征，但其中的元素不具备FIFO或者LIFO的顺序，插入和删除操作的规律性需要用户自己维持。

双端队列的一些操作实现，使用Python的列表实现，队首（front）为列表的末尾，队尾（rear）为列表的首部：

class Deque:
  def __init__(self):
    self.data = []

• is_empty()
• size() -- 返回队列的大小
• add_front(item) -- 在队首添加元素: self.data.append(item)
• add_rear(item) -- 在队尾添加元素: self.data.insert(0, item)
• remove_front() -- 从队首删除元素: return self.data.pop()
• remove_rear() -- 从队尾删除元素: return self.data.pop(0)