首页 > 其他 > 详细

用3种方法实现堆栈和队列并示例实际应用场景

时间:2021-04-26 11:16:54      阅读:24      评论:0      收藏:0      [点我收藏+]

介绍

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

堆栈

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

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

技术分享图片

 

 

 

  • pop - 删除堆栈顶部的元素:
 技术分享图片

 

 

队列

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

  • enqueue - 在队列的开头添加元素:
 技术分享图片

 

 

  • dequeue - 删除队列开头的元素:
 技术分享图片

 

 

使用列表实现堆栈和队列

Python的内置List数据结构--------堆栈和队列。

堆栈:

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种方法实现堆栈和队列并示例实际应用场景

原文:https://www.cnblogs.com/hls-code/p/14703271.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!