Python----数据结构（队列，顺序队列，链式队列，双端队列）

ops/2025/2/21 6:59:50/

一、队列

1.1、概念 

        队列(Queue)：也是一种基本的数据结构，在队列中的插入和删除都遵循先进先出（First in First out，FIFO）的原则。元素可以在任何时刻从队尾插入，但是只有在队列最前面 的元素才能被取出或者删除。通常将队列中允许插入的一端称为队尾，将允许删除的一 端称为队头。队列不允许在中间部位进行操作！ 

1.2、操作

栈使用两种基本操作：入队(push) 和 出队(pop):

  • 入队：将数据放入队尾
  • 出队：将队首数据移除

 1.3、特点

1.先入先出(FIFO, First In FirstOut)，后入后出(LILO, Last In Last Out)

2.除头尾节点之外，每个元素有一个前驱，一个后继

1.4、队列常用操作 

方法名描述时间复杂度
push( )元素入队，即将元素添加至队尾$O(1)$
pop( )队首元素出队$O(1)$
top( )访问队首元素$O(1)$

python中有现成的队列类queue.Queue 

二、顺序队列

2.1、初始化

python">    def __init__(self):  """初始化一个空队列，使用列表作为存储容器。"""  self.list = []  # 使用列表存储队列元素

2.2、入队

python">    def put(self, data):  """将数据放入队列末尾。  Args:  data: 要放入队列的数据。  """  self.list.append(data)  # 使用列表的 append 方法将数据添加到队列末尾

2.3、出队

python">    def get(self):  """从队列头部取出数据。  Returns:  从队列中取出的数据。  """  if self.is_empty():  # 检查队列是否为空  print("队列为空，无法取出数据。")  # 打印提示信息  return None  # 返回 None，指示无法取出数据  return self.list.pop(0)  # 从列表头部弹出数据，遵循 FIFO 原则

2.4、获取队长度

python">    def size(self):  """返回队列中元素的数量。  Returns:  队列中元素的数量。  """  return len(self.list)  # 使用 len 函数返回列表的长度

2.5、判断是否为空

python">    def is_empty(self):  """检查队列是否为空。  Returns:  如果队列为空返回 True，否则返回 False。  """  return self.list == []  # 检查列表是否为空

2.6、完整代码 

python">class Queue:  def __init__(self):  """初始化一个空队列，使用列表作为存储容器。"""  self.list = []  # 使用列表存储队列元素  def is_empty(self):  """检查队列是否为空。  Returns:  如果队列为空返回 True，否则返回 False。  """  return self.list == []  # 检查列表是否为空  def put(self, data):  """将数据放入队列末尾。  Args:  data: 要放入队列的数据。  """  self.list.append(data)  # 使用列表的 append 方法将数据添加到队列末尾  def get(self):  """从队列头部取出数据。  Returns:  从队列中取出的数据。  """  if self.is_empty():  # 检查队列是否为空  print("队列为空，无法取出数据。")  # 打印提示信息  return None  # 返回 None，指示无法取出数据  return self.list.pop(0)  # 从列表头部弹出数据，遵循 FIFO 原则  def size(self):  """返回队列中元素的数量。  Returns:  队列中元素的数量。  """  return len(self.list)  # 使用 len 函数返回列表的长度  if __name__ == '__main__':  q = Queue()  # 创建一个队列实例  q.put(10)    # 将 10 放入队列  q.put(20)    # 将 20 放入队列  q.put(30)    # 将 30 放入队列  q.put(40)    # 将 40 放入队列  print(q.get())  # 从队列中取出并打印第一个元素（10）  print(q.size())  # 打印队列当前的大小（3）

三、链队列

3.1、初始化

python">class Node:  def __init__(self, data):  """初始化节点，包含数据和指向下一个节点的指针。  Args:  data: 节点存储的数据。  """  self.data = data  # 节点数据  self.next = None  # 初始时，节点的 next 指向 None  
python">    def __init__(self):"""初始化一个空队列，使用头节点作为哨兵。"""self.head = Node(0)  # 哨兵节点，方便操作

3.2、入队

python">    def put(self, data):"""将数据放入队列末尾。Args:data: 要放入队列的数据。"""new_node = Node(data)  # 创建新节点current = self.head.next  # 从第一个有效节点开始if current is None:self.head.next = new_node  # 如果队列为空，直接将新节点作为队头else:# 遍历到队列的末尾while current.next is not None:current = current.nextcurrent.next = new_node  # 将新节点添加到队列末尾

3.3、出队

python">    def get(self):"""从队列头部取出数据。如果队列为空，打印提示信息。Returns:从队列中取出的数据。"""if self.is_empty():  # 检查队列是否为空print("队列为空，无法取出数据。")  # 打印提示信息return None  # 返回 None，指示无法取出数据current = self.head.next  # 获取队列头部元素self.head.next = current.next  # 移动头指针到下一个节点return current.data  # 返回取出的数据

3.4、获取队长度

python">    def size(self):"""返回队列中元素的数量。Returns:队列中元素的数量。"""count = 0current = self.head.next  # 从第一个有效节点开始while current is not None:count += 1current = current.next  # 移动到下一个节点return count  # 返回计数

3.5、判断是否为空

python">    def is_empty(self):"""检查队列是否为空。Returns:如果队列为空返回 True，否则返回 False。"""return self.head.next is None  # 如果头节点的 next 为 None，队列为空

3.6、完整代码 

python">class Node:def __init__(self, data):"""初始化节点，包含数据和指向下一个节点的指针。Args:data: 节点存储的数据。"""self.data = data  # 节点数据self.next = None  # 初始时，节点的 next 指向 Noneclass QueueLink:def __init__(self):"""初始化一个空队列，使用头节点作为哨兵。"""self.head = Node(0)  # 哨兵节点，方便操作def is_empty(self):"""检查队列是否为空。Returns:如果队列为空返回 True，否则返回 False。"""return self.head.next is None  # 如果头节点的 next 为 None，队列为空def put(self, data):"""将数据放入队列末尾。Args:data: 要放入队列的数据。"""new_node = Node(data)  # 创建新节点current = self.head.next  # 从第一个有效节点开始if current is None:self.head.next = new_node  # 如果队列为空，直接将新节点作为队头else:# 遍历到队列的末尾while current.next is not None:current = current.nextcurrent.next = new_node  # 将新节点添加到队列末尾def get(self):"""从队列头部取出数据。如果队列为空，打印提示信息。Returns:从队列中取出的数据。"""if self.is_empty():  # 检查队列是否为空print("队列为空，无法取出数据。")  # 打印提示信息return None  # 返回 None，指示无法取出数据current = self.head.next  # 获取队列头部元素self.head.next = current.next  # 移动头指针到下一个节点return current.data  # 返回取出的数据def size(self):"""返回队列中元素的数量。Returns:队列中元素的数量。"""count = 0current = self.head.next  # 从第一个有效节点开始while current is not None:count += 1current = current.next  # 移动到下一个节点return count  # 返回计数if __name__ == '__main__':q = QueueLink()  # 创建一个队列实例q.put(10)  # 将 10 放入队列q.put(20)  # 将 20 放入队列q.put(30)  # 将 30 放入队列q.put(40)  # 将 40 放入队列print(q.get())  # 从队列中取出并打印第一个元素（10）print(q.size())  # 打印队列当前的大小（3）

四、双端队列

4.1、初始化

python">    def __init__(self):  """初始化一个空双端队列，使用列表作为存储容器。"""  self.list = []  # 使用列表来存储双端队列的元素

4.2、队列前端添加元素

python">    def add_front(self, data):  """在队列前端添加元素。  Args:  data: 要添加到队列前端的数据。  """  self.list.insert(0, data)  # 使用 insert 方法在列表的开头插入新元素

4.3、队列后端添加元素

python">    def add_rear(self, data):  """在队列后端添加元素。  Args:  data: 要添加到队列后端的数据。  """  self.list.append(data)  # 使用 append 方法在列表的末尾添加新元素

4.4、队列前端移除元素

python">    def remove_front(self):  """从队列前端移除并返回元素。  Returns:  被移除的元素，如果队列为空，则会引发异常。  """  if self.is_empty():  # 检查队列是否为空  print("队列为空，无法从前端移除数据。")  return None  # 如果为空，返回 None  return self.list.pop(0)  # 从列表的开头移除并返回元素

4.5、队列后端移除元素

python">    def remove_rear(self):  """从队列后端移除并返回元素。  Returns:  被移除的元素，如果队列为空，则会引发异常。  """  if self.is_empty():  # 检查队列是否为空  print("队列为空，无法从后端移除数据。")  return None  # 如果为空，返回 None  return self.list.pop()  # 从列表的末尾移除并返回元素

4.6、判断是否为空

python">    def is_empty(self):  """检查队列是否为空。  Returns:  如果队列为空返回 True，否则返回 False。  """  return self.list == []  # 检查列表是否为空

4.7、获取队长度

python">    def size(self):  """返回队列中元素的数量。  Returns:  队列中元素的数量。  """  return len(self.list)  # 返回列表的长度

4.8、完整代码

python">class Deque:  def __init__(self):  """初始化一个空双端队列，使用列表作为存储容器。"""  self.list = []  # 使用列表来存储双端队列的元素  def add_front(self, data):  """在队列前端添加元素。  Args:  data: 要添加到队列前端的数据。  """  self.list.insert(0, data)  # 使用 insert 方法在列表的开头插入新元素  def add_rear(self, data):  """在队列后端添加元素。  Args:  data: 要添加到队列后端的数据。  """  self.list.append(data)  # 使用 append 方法在列表的末尾添加新元素  def remove_front(self):  """从队列前端移除并返回元素。  Returns:  被移除的元素，如果队列为空，则会引发异常。  """  if self.is_empty():  # 检查队列是否为空  print("队列为空，无法从前端移除数据。")  return None  # 如果为空，返回 None  return self.list.pop(0)  # 从列表的开头移除并返回元素  def remove_rear(self):  """从队列后端移除并返回元素。  Returns:  被移除的元素，如果队列为空，则会引发异常。  """  if self.is_empty():  # 检查队列是否为空  print("队列为空，无法从后端移除数据。")  return None  # 如果为空，返回 None  return self.list.pop()  # 从列表的末尾移除并返回元素  def is_empty(self):  """检查队列是否为空。  Returns:  如果队列为空返回 True，否则返回 False。  """  return self.list == []  # 检查列表是否为空  def size(self):  """返回队列中元素的数量。  Returns:  队列中元素的数量。  """  return len(self.list)  # 返回列表的长度  if __name__ == '__main__':  dq = Deque()  # 创建一个双端队列实例  dq.add_front(10)  # 在队列前端添加 10  dq.add_front(20)  # 在队列前端添加 20  dq.add_front(30)  # 在队列前端添加 30  dq.add_rear(90)  # 在队列后端添加 90  dq.add_rear(80)  # 在队列后端添加 80  dq.add_rear(70)  # 在队列后端添加 70  print(dq.remove_front())  # 从队列前端移除并打印（30）  print(dq.remove_rear())    # 从队列后端移除并打印（70）  print(dq.size())  # 打印当前队列的大小

五、思维导图


http://www.ppmy.cn/ops/160175.html

相关文章

深入解析：短轮询、长轮询、长连接与WebSocket（原理到实现）

深入解析：短轮询、长轮询、长连接与WebSocket（原理到实现）

从原理到实战：深度剖析短轮询、长轮询、长连接及 WebSocket 的实现与差异 在日常开发中，短轮询、长轮询、长连接和WebSocket是常见的几种通信技术，各自适用于不同的场景。本文将深入分析这四种技术，从原理到实现，并探讨…
阅读更多...
如何使用springboot项目如何实现小程序里面商品的浏览记录功能案例

如何使用springboot项目如何实现小程序里面商品的浏览记录功能案例

1 第一步，数据库表结构设计 DROP TABLE IF EXISTS product_browse_history; CREATE TABLE product_browse_history (id bigint NOT NULL COMMENT 记录编号,spu_id bigint DEFAULT NULL COMMENT 商品 SPU 编号,user_id bigint DEFAULT NULL COMMENT 用户编号,user_d…
阅读更多...
基于微信小程序的家政服务预约系统的设计与实现（php论文源码调试讲解）

基于微信小程序的家政服务预约系统的设计与实现（php论文源码调试讲解）

第3章 系统设计 3.1系统功能结构设计 本系统的结构分为管理员和客户、员工。本系统的功能结构图如下图3.1所示： 图3.1系统功能结构图 3.2数据库设计 本系统为小程序类的预约平台，所以对信息的安全和稳定要求非常高。为了解决本问题，采用前端…
阅读更多...
C++:类与对象，定义类和构造函数

C++:类与对象，定义类和构造函数

#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> using namespace std; //如何让定义一个类 // 封装 // 1、将数据和方法定义到一起。 // 2、把想给你看的数据给你看&#xff0c;不想给你看的封装起来。 通过访问限定符来实现 class Stack { public: //1.成…
阅读更多...
线性代数中的向量与向量空间

线性代数中的向量与向量空间

线性代数中的向量与向量空间 线性代数是数学的一个分支&#xff0c;它广泛应用于计算机科学、物理学、工程学等领域。在这些领域中&#xff0c;向量和向量空间是构建复杂系统和模型的基础。本文将深入探讨这两个核心概念。 1. 向量&#xff1a;不仅仅是箭头 在线性代数中&am…
阅读更多...
C++蓝桥杯基础篇（四）

C++蓝桥杯基础篇（四）

片头 嗨~小伙伴们&#xff0c;大家好&#xff01;今天我们来学习C蓝桥杯基础篇&#xff08;四&#xff09;&#xff0c;继续练习相关习题。准备好了吗&#xff1f;咱们开始咯~ 题目1 连续整数相加 思路分析&#xff1a; 这道题&#xff0c;我们可以把从键盘中读取n写在while循…
阅读更多...
文心一言，下一代模型开源

文心一言，下一代模型开源

大家好&#xff0c;我是小悟。 百度官宣&#xff0c;将在未来几个月中陆续推出文心大模型 4.5 系列&#xff0c;并于 6 月 30 日起正式开源。 与此同时&#xff0c;百度近期发布多项 AI 开放政策&#xff0c;进一步降低大模型的使用门槛。随着文心大模型的迭代升级和成本不断…
阅读更多...
排查生产sql查询缓慢

排查生产sql查询缓慢

生产投产检验&#xff0c;发现查询客户明细的接口数据响应需要5秒以上&#xff0c;通过接口可以查询到详细的后端代码 1. 先排查后端的代码实现&#xff0c;并未出现复杂逻辑&#xff0c;那么就应该是sql的问题 2. 通过explain对sql进行解析&#xff0c;发现sql没有走索引 3.…
阅读更多...
最新文章

Copyright @ 2022~2023