[雪峰磁针石博客]Python经典面试题: 用3种方法实现堆栈和队列并示例实际应用场景

简介: 介绍 数据结构在计算机中组织存储,以便我们可以有效地访问和更改数据。 堆栈和队列是计算机科学中定义的最早的数据结构。 堆栈 遵循后进先出 (Last-in-First-Out LIFO)原则。 push - 在堆栈顶部添加元素: pop - 删除堆栈顶部的元素: 队列 遵循先入先出(FIFO:First-in-First-Out)原则。

介绍

数据结构在计算机中组织存储,以便我们可以有效地访问和更改数据。 堆栈队列是计算机科学中定义的最早的数据结构。

堆栈

遵循后进先出 (Last-in-First-Out LIFO)原则。

  • push - 在堆栈顶部添加元素:

图片.png

  • pop - 删除堆栈顶部的元素:

图片.png

队列

遵循先入先出(FIFO:First-in-First-Out)原则。

  • enqueue - 在队列的开头添加元素:

图片.png

  • dequeue - 删除队列开头的元素:

图片.png

使用列表实现堆栈和队列

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
相关文章
|
3天前
|
机器学习/深度学习 数据可视化 算法
Python数值方法在工程和科学问题解决中的应用
本文探讨了Python数值方法在工程和科学领域的广泛应用。首先介绍了数值计算的基本概念及Python的优势,如易学易用、丰富的库支持和跨平台性。接着分析了Python在有限元分析、信号处理、优化问题求解和控制系统设计等工程问题中的应用,以及在数据分析、机器学习、模拟建模和深度学习等科学问题中的实践。通过具体案例,展示了Python解决实际问题的能力,最后总结展望了Python在未来工程和科学研究中的发展潜力。
|
10天前
|
Python
解决Python报错:DataFrame对象没有concat属性的多种方法(解决方案汇总)
总的来说,解决“DataFrame对象没有concat属性”的错误的关键是理解concat函数应该如何正确使用,以及Pandas库提供了哪些其他的数据连接方法。希望这些方法能帮助你解决问题。记住,编程就像是解谜游戏,每一个错误都是一个谜题,解决它们需要耐心和细心。
56 15
|
17天前
|
Python
[oeasy]python086方法_method_函数_function_区别
本文详细解析了Python中方法(method)与函数(function)的区别。通过回顾列表操作如`append`,以及随机模块的使用,介绍了方法作为类的成员需要通过实例调用的特点。对比内建函数如`print`和`input`,它们无需对象即可直接调用。总结指出方法需基于对象调用且包含`self`参数,而函数独立存在无需`self`。最后提供了学习资源链接,方便进一步探索。
53 17
|
10天前
|
Python
Python中Cp、Cpk、Pp、Ppk的计算与应用
总的来说,Cp、Cpk、Pp、Ppk是衡量过程能力的重要工具,它们可以帮助我们了解和改进生产过程,提高产品质量。
50 13
|
12天前
|
存储 缓存 文件存储
uv安装python及其依赖的加速方法
国内在使用uv的时候,可能会涉及到装python的速度太慢的问题,为了解决这个问题,可以使用`UV_PYTHON_INSTALL_MIRROR`这个环境变量。除此以外,对于多人协作场景,`UV_CACHE_DIR`也是一个有用的环境变量。本文会介绍这两个变量。
345 10
|
11月前
|
测试技术 Python
Python中的装饰器应用与实践
在Python编程中,装饰器是一种强大的工具,能够优雅地扩展和修改函数或方法的行为。本文将深入探讨Python中装饰器的作用、原理以及实际应用场景,帮助读者更好地理解并运用装饰器提升代码的可维护性和灵活性。
|
10月前
|
数据采集 数据可视化 大数据
Python在大数据处理中的应用实践
Python在大数据处理中扮演重要角色,借助`requests`和`BeautifulSoup`抓取数据,`pandas`进行清洗预处理,面对大规模数据时,`Dask`提供分布式处理能力,而`matplotlib`和`seaborn`则助力数据可视化。通过这些工具,数据工程师和科学家能高效地管理、分析和展示海量数据。
494 4
|
5月前
|
设计模式 开发者 Python
Python编程中的设计模式应用与实践感悟####
本文作为一篇技术性文章,旨在深入探讨Python编程中设计模式的应用价值与实践心得。在快速迭代的软件开发领域,设计模式如同导航灯塔,指引开发者构建高效、可维护的软件架构。本文将通过具体案例,展现设计模式如何在实际项目中解决复杂问题,提升代码质量,并分享个人在实践过程中的体会与感悟。 ####
|
5月前
|
机器学习/深度学习 数据采集 数据可视化
Python在数据科学中的应用:从入门到实践
本文旨在为读者提供一个Python在数据科学领域应用的全面概览。我们将从Python的基础语法开始,逐步深入到数据处理、分析和可视化的高级技术。文章不仅涵盖了Python中常用的数据科学库,如NumPy、Pandas和Matplotlib,还探讨了机器学习库Scikit-learn的使用。通过实际案例分析,本文将展示如何利用Python进行数据清洗、特征工程、模型训练和结果评估。此外,我们还将探讨Python在大数据处理中的应用,以及如何通过集成学习和深度学习技术来提升数据分析的准确性和效率。
|
5月前
|
设计模式 监控 算法
Python编程中的设计模式应用与实践感悟###
在Python这片广阔的编程疆域中,设计模式如同导航的灯塔,指引着开发者穿越复杂性的迷雾,构建出既高效又易于维护的代码结构。本文基于个人实践经验,深入探讨了几种核心设计模式在Python项目中的应用策略与实现细节,旨在为读者揭示这些模式背后的思想如何转化为提升软件质量的实际力量。通过具体案例分析,展现了设计模式在解决实际问题中的独特魅力,鼓励开发者在日常编码中积极采纳并灵活运用这些宝贵的经验总结。 ###
下一篇
oss创建bucket