Python数据结构与算法中的队列详解(1)

目录
  • 什么是队列？
  • 构建一个队列
  • 总结

什么是队列？

队列，与栈类似，是有序集合。添加操作发生在 “尾部”，移除操作只发生在 “头部”。新元素只从尾部进入队列，然后一直向前移动到头部，直到成为下一个被移除的元素。​

最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素则排在最前面。这种排序原则被称作FIFO（first-in first-out），即先进先出，也称先到先得。在日常生活中，我们经常排队，这便是最简单的队列例子。进电影院要排队，在超市结账要排队，买咖啡也要排队。好的队列只允许一头进，另一头出，不可能发生插队或者中途离开的情况。​

构建一个队列

如前所述，队列是元素的有序集合，添加操作发生在其尾部，移除操作则发生在头部。队列的操作顺序是 FIFO，它支持以下操作。

  • 创建一个空队列。它不需要参数，且会返回一个空队列。Queue()
  • 在队列的尾部添加一个元素。 它需要一个元素作为参数，不返回任何值。enqueue(item)
  • 从队列的头部移除一个元素。它不需要参数，且会返回一个元素，并修改队列的内容。 dequeue()
  • 检查队列是否为空。它不需要参数， 且会返回一个布尔值。isEmpty()
  • 返回队列中元素的数目。它不需要参数，且会返回一个整数。 size()​

与构建栈一样，我们利用简洁强大的列表来实现队列。​

需要确定列表的哪一端是队列的尾部，哪一端是头部。 我们假设队列的尾部在列表的位置0处。 如此一来，便可以使用 insert 函数向队列的尾部添加新元素。pop 则可用于移除队列头部的元素（列表中的最后一个元素）。这意味着添加操作的时间复杂度是O(n)，移除操作则是O(1)。​

队列实现代码如下：

class Queue:
    def __init__(self):
        self.items = []            # 构建空队列
        print("你创建了一个队列")
    def isEmpty(self):
        return self.items ==[]     # 判断是否为空
    def enqueue(self,item):
        self.items.insert(0, item) # 在队列尾部(列表左端)插入元素
        print("你在队列尾部插入了一个%s" % item)
    def dequeue(self):
        print("你在队列头部移除了一个元素")
        return self.items.pop()    # 在队列头部(列表右端)移出元素
    def size(self):
        return len(self.items)     # 队列(列表)长度
    def look(self):
        print(self.items)

下图展示了队列的操作及其返回结果：

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容!

赞 (0)

相关推荐

  • Python的数据结构与算法之队列详解

    Python的数据结构与算法之队列详解

    目录 模拟打印机任务队列过程 主要模拟步骤: ​构建队列程序 模拟打印程序 模拟打印过程(有注释) 总结 模拟打印机任务队列过程 计算机科学中也有众多的队列例子.比如计算机实验室有10台计算机,它们都与同一台打印机相连.当学生需要打印的时候,他们的打印任务会进入一个队列.该队列中的第一个任务就是即将执行的打印任务.如果一个任务排在队列的最后面,那么它必须等到所有前面的任务都执行完毕后才能执行.​ 学生向共享打印机发送打印请求,这些打印任务被存在一个队列中,并且按照先到先得的顺序执行.这样的设定可

  • Python双端队列deque的实现

    Python双端队列deque的实现

    目录 前言 基本用法 填充 线程安全 旋转 限制双端队列大小 前言 双端队列deque支持从任意一端增加和删除元素.其中,栈和队列就是双端队列的退化形式,它们的输入输出被限制在某一端. 基本用法 首先,我们来看看容器collections.deque()函数的基本用法.具体代码如下所示: import collections c = collections.deque('abcdefg') print("输出双端队列:", c) print("双端队列的长度:",

  • Python全栈之队列详解

    Python全栈之队列详解

    目录 1. lock互斥锁 2. 事件_红绿灯效果 2.1 信号量_semaphore 2.2 事件_红绿灯效果 3. queue进程队列 4. 生产者消费者模型 5. joinablequeue队列使用 6. 总结 1. lock互斥锁 知识点: lock.acquire()# 上锁 lock.release()# 解锁 #同一时间允许一个进程上一把锁 就是Lock 加锁可以保证多个进程修改同一块数据时,同一时间只能有一个任务可以进行修改,即串行的修改,没错,速度是慢了,但牺牲速度却保证了数据

  • Python双端队列实现回文检测

    Python双端队列实现回文检测

    目录 一.双端队列 二.回文检测 补充 一.双端队列 双端队列 Deque 是一种有次序的数据集,跟队列相似,其两端可以称作"首" 和 "尾"端,但 Deque 中数据项既可以从队首加入,也可以从队尾加入:数据项也可以从两端移除.某种意义上说,双端队列集成了栈和队列的能力. 但双端队列并不具有内在的 LIFO 或者 FIFO 特性,如果用双端队列来模拟栈或队列,需要由使用者自行维护操作的一致性. 用 Python 实现抽象数据类型Deque,Deque定义的操作如下

  • 详解python数据结构之队列Queue

    详解python数据结构之队列Queue

    一.前言 队列Queue是一种先进先出(FIFO,First In First Out)的线性表.允许一端进行插入(rear),对应的另一段进行删除(front). 本篇包含以下内容: (1)Queue的基本格式 (2)入队列en_queue (3)删除数据函数 de_queue 二.Queue的基本格式 class Queue(): def __init__(self,size): self.size = size self.front = -1 #设置front初始值,每出队列一个数据就加

  • Python数据结构与算法中的队列详解(2)

    Python数据结构与算法中的队列详解(2)

    目录 传土豆 总结 传土豆 队列的一个典型方法是模拟需要以 FIFO 方式管理数据的真实场景.考虑这样一个游戏:传土豆.在这个游戏中,成员们围成一圈,并依次尽可能快地传递一个土豆.在某个时刻,大家停止传递,此时手里有土豆的成员就得退出游戏. 重复上述过程,直到只剩下一个成员. 我们将针对传土豆游戏实现通用的模拟程序.该程序接受一个名字列表和一个用于计数的常量 num ,并且返回最后剩下的那个人的名字. 我们使用队列来模拟一个环.即假设握着土豆的人位于队列的头部.在模拟传土豆的过程中,程序将这个人

  • Python数据结构与算法中的队列详解(1)

    Python数据结构与算法中的队列详解(1)

    目录 什么是队列? 构建一个队列 总结 什么是队列? 队列,与栈类似,是有序集合.添加操作发生在 “尾部”,移除操作只发生在 “头部”.新元素只从尾部进入队列,然后一直向前移动到头部,直到成为下一个被移除的元素.​ 最新添加的元素必须在队列的尾部等待,在队列中时间最长的元素则排在最前面.这种排序原则被称作FIFO(first-in first-out),即先进先出,也称先到先得.在日常生活中,我们经常排队,这便是最简单的队列例子.进电影院要排队,在超市结账要排队,买咖啡也要排队.好的队列只允许一

  • Python数据结构与算法中的栈详解(2)

    Python数据结构与算法中的栈详解(2)

    目录 匹配括号 匹配符号 总结 匹配括号 接下来,我们使用栈解决实际的计算机科学问题.​ 比如我们都写过这样所示的算术表达式, ( 5 + 6 ) ∗ ( 7 + 8 ) / ( 4 + 3 ) (5 + 6) * (7 + 8) / (4 + 3) (5+6)∗(7+8)/(4+3),其中的括号用来改变计算顺序,或提升运算优先级.​ 匹配括号是指每一个左括号都有与之对应的一个右括号,并且括号对有正确的嵌套关系. 正确的嵌套关系: ( ( ) ( ) ( ) ( ) ) (()()()()) (

  • Python数据结构与算法中的栈详解(3)

    Python数据结构与算法中的栈详解(3)

    目录 前序.中序和后序表达式是什么? 我们为什么要学习前/后序表达式? 从中序向前序和后序转换 用Python实现从中序表达式到后序表达式的转换​ 计算后序表达式 总结 前序.中序和后序表达式是什么? 对于像B∗C 这样的算术表达式,可以根据其形式来正确地运算.在B∗C 的例子中,由于乘号出现在两个变量之间,因此我们知道应该用变量 B 乘以变量 C .​ 因为运算符出现在两个操作数的中间 ,所以这种表达式被称作中序表达式 .​ 来看另一个中序表达式的例子:A+B∗C.虽然运算符 “ + ” 和

  • Python数据结构与算法中的栈详解

    Python数据结构与算法中的栈详解

    目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.1.2求栈长 2.1.3判栈空 2.1.4判栈满 2.1.5入栈 2.1.6出栈 2.1.7求栈顶元素 2.2链栈的实现 2.2.1栈结点 2.2.2栈的初始化 2.2.3求栈长 2.2.4判栈空 2.2.5入栈 2.2.6出栈 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 总

  • Python数据结构与算法中的栈详解(1)

    Python数据结构与算法中的栈详解(1)

    目录 什么是栈 构建一个栈 总结 什么是栈 栈有时也被称作“下推栈”.它是有序集合,添加操作和移除操作总发生在同一端,即栈的 “顶端”,栈的另一端则被称为 “底端”.所以最新添加的元素将被最先移除,而且栈中的元素离底端越近,代表其在栈中的时间越长. 这种排序原则被称作LIFO(last-in first-out),即后进先出.它提供了一种基于在集合中的时间来排序的方式. 最近添加的元素靠近顶端,旧元素则靠近底端. 栈的例子在日常生活中比比皆是.几乎所有咖啡馆都有一个由托盘或盘子构成的栈,你可以从

  • Python数据结构与算法之跳表详解

    Python数据结构与算法之跳表详解

    目录 0. 学习目标 1. 跳表的基本概念 1.1 跳表介绍 1.2 跳表的性能 1.3 跳表与普通链表的异同 2. 跳表的实现 2.1 跳表结点类 2.2 跳表的初始化 2.3 获取跳表长度 2.4 读取指定位置元素 2.5 查找指定元素 2.6 在跳表中插入新元素 2.7 删除跳表中指定元素 2.8 其它一些有用的操作 3. 跳表应用 3.1 跳表应用示例 0. 学习目标 在诸如单链表.双线链表等普通链表中,查找.插入和删除操作由于必须从头结点遍历链表才能找到相关链表,因此时间复杂度均为O(

  • 详解Python数据结构与算法中的顺序表

    详解Python数据结构与算法中的顺序表

    目录 0. 学习目标 1. 线性表的顺序存储结构 1.1 顺序表基本概念 1.2 顺序表的优缺点 1.3 动态顺序表 2. 顺序表的实现 2.1 顺序表的初始化 2.2 获取顺序表长度 2.3 读取指定位置元素 2.4 查找指定元素 2.5 在指定位置插入新元素 2.6 删除指定位置元素 2.7 其它一些有用的操作 3. 顺序表应用 3.1 顺序表应用示例 3.2 利用顺序表基本操作实现复杂操作 0. 学习目标 线性表在计算机中的表示可以采用多种方法,采用不同存储方法的线性表也有着不同的名称和特

  • Python数据结构与算法之使用队列解决小猫钓鱼问题

    Python数据结构与算法之使用队列解决小猫钓鱼问题

    本文实例讲述了Python数据结构与算法之使用队列解决小猫钓鱼问题.分享给大家供大家参考,具体如下: 按照<啊哈>里的思路实现这道题目,但是和结果不一样,我自己用一幅牌试了一下,发现是我的结果像一点,可能我理解的有偏差. # 小猫钓鱼 # 计算桌上每种牌的数量 # 使用defaultdict类,并设置默认类型为int型,即默认值为0 # cardcounts = defaultdict(int) # 不过deque有对应的方法 def henhenhaahaa(): from collecti

  • Python数据结构之图的存储结构详解

    Python数据结构之图的存储结构详解

    一.图的定义 图是一种比树更复杂的一种数据结构,在图结构中,结点之间的关系是任意的,任意两个元素之间都可能相关,因此,它的应用极广.图中的数据元素通常被称为顶点 ( V e r t e x ) (Vertex) (Vertex), V V V是顶点的有穷非空集合, V R VR VR是两个顶点之间的关系的集合(可以为空),可以表示为图 G = { V , { V R } } G=\{V,\{VR\}\} G={V,{VR}}. 二.相关术语 2.1 无向图 给定图 G = { V , { E }

随机推荐