[雪峰磁针石博客]Python经典面试题: 用3种方法实现堆栈和队列并示例实际应用场景
介绍
数据结构在计算机中组织存储,以便我们可以有效地访问和更改数据。 堆栈和队列是计算机科学中定义的最早的数据结构。
堆栈
遵循后进先出 (Last-in-First-Out LIFO)原则。
- push - 在堆栈顶部添加元素:
- pop - 删除堆栈顶部的元素:
队列
遵循先入先出(FIFO:First-in-First-Out)原则。
- enqueue - 在队列的开头添加元素:
- dequeue - 删除队列开头的元素:
使用列表实现堆栈和队列
Python的内置List数据结构k堆栈和队列操作的方法。
堆栈
letters = [] # Let's push some letters into our list letters.append('c') letters.append('a') letters.append('t') letters.append('g') # Now let's pop letters, we should get 'g' last_item = letters.pop() print(last_item) # If we pop again we'll get 't' last_item = letters.pop() print(last_item) # 'c' and 'a' remain print(letters) # ['c', 'a']
执行结果
g t ['c', 'a']
队列
fruits = [] # Let's enqueue some fruits into our list fruits.append('banana') fruits.append('grapes') fruits.append('mango') fruits.append('orange') # Now let's dequeue our fruits, we should get 'banana' first_item = fruits.pop(0) print(first_item) # If we dequeue again we'll get 'grapes' first_item = fruits.pop(0) print(first_item) # 'mango' and 'orange' remain print(fruits) # ['c', 'a']
执行结果
banana grapes ['mango', 'orange']
使用Deque库的堆栈和队列
deque是Double Ended Queue的缩写 - 可以获取存储的第一个或最后一个元素的通用队列,下面我们使用Deque库的堆栈和队列:
from collections import deque # you can initialize a deque with a list numbers = deque() # Use append like before to add elements numbers.append(99) numbers.append(15) numbers.append(82) numbers.append(50) numbers.append(47) # You can pop like a stack last_item = numbers.pop() print(last_item) # 47 print(numbers) # deque([99, 15, 82, 50]) # You can dequeue like a queue first_item = numbers.popleft() print(first_item) # 99 print(numbers) # deque([15, 82, 50])
执行结果
47 deque([99, 15, 82, 50]) 99 deque([15, 82, 50])
参考资料
更严格的实现
创建撤消功能 - 允许用户回溯他们的操作,直到会话开始。堆栈是这种情况的理想选择。 我们可以通过将其推送到堆栈来记录用户所采取的每个操作。 当用户想要撤消操作时,他们将从堆栈中弹出它。
游戏中,每次按下按钮,都会触发输入事件。 测试人员注意到,如果按钮按下得太快,游戏只处理第一个按钮,特殊动作将无效!可以使用队列修复它。 我们可以将所有输入事件排入队列。
#!/usr/bin/python3 # -*- coding: utf-8 -*- # 项目实战讨论QQ群630011153 144081101 # python测试开发库汇总: https://github.com/china-testing/python-api-tesing/ # 本文最佳板式地址: https://www.jianshu.com/p/c990427ca608 # A simple class stack that only allows pop and push operations class Stack: def __init__(self): self.stack = [] def pop(self): if len(self.stack) < 1: return None return self.stack.pop() def push(self, item): self.stack.append(item) def size(self): return len(self.stack) # And a queue that only has enqueue and dequeue operations class Queue: def __init__(self): self.queue = [] def enqueue(self, item): self.queue.append(item) def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) def size(self): return len(self.queue) document_actions = Stack() # The first enters the title of the document document_actions.push('action: enter; text_id: 1; text: This is my favourite document') # Next they center the text document_actions.push('action: format; text_id: 1; alignment: center') # As with most writers, the user is unhappy with the first draft and undoes the center alignment document_actions.pop() # The title is better on the left with bold font document_actions.push('action: format; text_id: 1; style: bold') input_queue = Queue() # The player wants to get the upper hand so pressing the right combination of buttons quickly input_queue.enqueue('DOWN') input_queue.enqueue('RIGHT') input_queue.enqueue('B') # Now we can process each item in the queue by dequeueing them key_pressed = input_queue.dequeue() # 'DOWN' # We'll probably change our player position key_pressed = input_queue.dequeue() # 'RIGHT' # We'll change the player's position again and keep track of a potential special move to perform key_pressed = input_queue.dequeue() # 'B' # This can do the act, but the game's logic will know to do the special move
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
循环语句
什么是循环:举例就是相同的事情重复做,例如操场跑圈跑圈,跑十圈就是循环了10次,例如吃包子,吃了10个包子就是循环了10次。 循环是有两种的,一种是条件循环例如循环10次,百次,千次等等,还有一种是死循环无限循环不会停止。 嵌套循环,外循环控制的是行,内循环控制的是列。 import java.util.Scanner; public class T6 { public static void main(String[] args) { for (int i = 1; i <=4 ; i++) { System.out.println();//共有4行从1开始 for (int j = 1; j <=i ; j++) { System.out.print("*");//内控制列 } } } } 循环常用的是while循环和for循环,如果知道循环次数的话就用for,如果不知到次数就用while循环。 循环当中有两个关键字:break 跳出最近循环(终止最近操作的循环 continue 停止最近的本次循环 进行下次循环 import jav...
- 下一篇
[雪峰磁针石博客]数据仓库快速入门教程1简介
数据仓库是从各种渠道收集和管理数据的技术,可提供有意义的业务洞察,战略性地使用数据。它用于查询和分析而不是事务处理,是将数据转换为信息并及时向用户提供的过程。 决策支持数据库(数据仓库)与组织的运营数据库分开维护。 但是数据仓库不是产品,而是环境。 它是属于信息系统,向用户传统运营数据存储难以访问或展示的当前和历史决策支持信息。 数据仓库是BI系统的核心,BI是为数据分析和报告而构建的。 你们很多人都知道,3NF设计的库存系统数据库很多都有相互关联的表。 例如,有关当前库存信息的报告可包含超过12个连接条件,查询慢。 数据仓库提供了一种新设计,可以缩短响应时间,提高报表和分析查询的性能。 数据仓库系统的其他名称: 决策支持系统(DSS Decision Support System) 执行信息系统(Executive Information System) 管理信息系统(Management Information System) 商业智能解决方案(Management Information System) 分析应用(Analytic Application) 数据仓库(Data W...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2全家桶,快速入门学习开发网站教程
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS6,CentOS7官方镜像安装Oracle11G
- Windows10,CentOS7,CentOS8安装Nodejs环境
- Linux系统CentOS6、CentOS7手动修改IP地址