队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

一、队列的常用操作

一、入队（Enqueue）

1. 操作含义

        将元素添加到队列的末尾。

     2.示例（以Python为例，使用列表来简单模拟队列）

• queue = []
  element = 10
  queue.append(element)
  print(queue)  # [10]

二、出队（Dequeue）

1. 操作含义
   • 移除队列头部的元素，并返回该元素的值。
2. 示例（以Python为例）

   • queue = [10, 20, 30]
     front_element = queue.pop(0)
     print(front_element)  # 10
     print(queue)  # [20, 30]

三、查看队首元素（Peek）

1. 操作含义
   • 返回队列头部的元素，但不移除它。
2. 示例（以Python为例）

   • queue = [10, 20, 30]
     front_element = queue
     print(front_element)  # 10
     print(queue)  # [10, 20, 30]

四、判断队列是否为空（Is Empty）

1. 操作含义
   • 检查队列中是否有元素，如果没有元素则返回True，否则返回False。
2. 示例（以Python为例）

   • queue = []
     is_empty = len(queue)==0
     print(is_empty)  # True
     queue = [10]
     is_empty = len(queue)==0
     print(is_empty)  # False

五、获取队列大小（Size）

1. 操作含义
   • 返回队列中元素的数量。
2. 示例（以Python为例）

   • queue = [10, 20, 30]
     size = len(queue)
     print(size)  # 3

 二、具体实现

1.基于链表的实现 

# 首先定义链表节点类
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass LinkedListQueue:""" 基于链表实现的队列"""def __init__(self):""" 构造方法"""self._front = None  # 头节点frontself._rear = None   # 尾节点rearself._size = 0def size(self) -> int:""" 获取队列的长度"""return self._sizedef is_empty(self) -> bool:""" 判断队列是否为空"""return self._size == 0def push(self, num: int):""" 入队"""# 在尾节点后添加numnode = ListNode(num)# 如果队列为空，则令头、尾节点都指向该节点if self._front is None:self._front = nodeself._rear = nodeelse:self._rear.next = nodeself._rear = nodeself._size += 1def pop(self) -> int:""" 出队"""if self.is_empty():raise IndexError("队列为空")num = self._front.val# 删除头节点self._front = self._front.nextself._size -= 1if self._front is None:self._rear = Nonereturn numdef peek(self) -> int:""" 访问队首元素"""if self.is_empty():raise IndexError("队列为空")return self._front.valdef to_list(self) -> list[int]:""" 转化为列表用于打印"""queue = []temp = self._frontwhile temp:queue.append(temp.val)temp = temp.nextreturn queue

2.基于数组的实现 

在数组中删除首元素的时间复杂度为 𝑂(𝑖) ，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。
我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义
rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。
 

class ArrayQueue:""" 基于环形数组实现的队列"""def __init__(self, size: int):""" 构造方法"""self._nums =  * size# 用于存储队列元素的数组self._front = 0# 队首指针，指向队首元素self._size = 0# 队列长度def capacity(self) -> int:""" 获取队列的容量"""return len(self._nums)def size(self) -> int:""" 获取队列的长度"""return self._sizedef is_empty(self) -> bool:""" 判断队列是否为空"""return self._size == 0def push(self, num: int):""" 入队"""if self._size == self.capacity():raise IndexError("队列已满")# 计算队尾指针，指向队尾索引 + 1# 通过取余操作实现 rear 越过数组尾部后回到头部rear = (self._front + self._size) % self.capacity()# 将 num 添加至队尾self._nums[rear] = numself._size += 1def pop(self) -> int:""" 出队"""if self.is_empty():raise IndexError("队列为空")num = self.peek()# 队首指针向后移动一位，若越过尾部，则返回到数组头部self._front = (self._front + 1) % self.capacity()self._size -= 1return numdef peek(self) -> int:""" 访问队首元素"""if self.is_empty():raise IndexError("队列为空")return self._nums[self._front]def to_list(self) -> list[int]:""" 返回列表用于打印"""res = []index = self._frontfor _ in range(self._size):res.append(self._nums[index])index = (index + 1) % self.capacity()return res