Python 数据结构入门 - 队列(Queue)
18年9月10日 · Python123 4912 人阅读
什么是队列
由数据类型相似的元素组成,只允许队尾插入,队头删除的的有序列表。
队尾:队列的最后端;队头:队列的最前端。
队列的特点
数据元素遵循先进先出原则:FIFO(First in, first out)。
队列的应用场景
凡是需要排队的场景都可以使用队列。
- 对共享资源服务的请求,比如打印机排队打印文档、 CPU 任务调度等;
- 呼叫中心电话系统利用队列保持呼叫有序;
- 实时系统的中断处理。
动手试一试
(提示:点击交互式代码框右上角按钮可运行代码)
下面是一个简单的队列实现,先不要关心实现原理,亲自试一试队列的各种操作吧
1. 创建一个队列,并入队几个元素
2. 删除队头元素,模拟出队操作,并打印整个队列
3. 队列 q 中入队 x y z,并出队一次,打印整个队列
队列经典案例
1. 杨辉三角问题
杨辉三角是二项式系数在三角形中的一种几何排列。它有下列性质:
- 前两行的数字都为 1
- 每个数等于它上方两数之和
- 每行数字左右对称,由 1 开始逐渐变大
- 第 n 行的数字有 n 项
上面这段代码打印出一个直角三角形,你能修改代码并打印出一个等腰三角形吗?
2. 约瑟夫环问题
约瑟夫斯问题是一个出现在计算机科学和数学中的问题,也叫约瑟夫环。已知 n 个人(以编号1,2,3 ... n 分别表示)围坐在一张圆桌周围。从编号为 k 的人开始报数,数到 m 的那个人出列;他的下一个人又从 1 开始报数,数到 m 的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
假设有 n 个人排成一个圆,从某个位置开始依次从 1 报数,报到 m,则那个人退出,再重新报数,如此循环,求解最后留下的人。
Python3Turtle