Python經典面試題：用3種方法做到堆棧和隊列並示例實際運用

介紹

數據結構在計算機中組織存儲，以便我們可以有效地訪問和更改數據。 堆棧和隊列是計算機科學中定義的最早的數據結構。

堆棧

遵循後進先出 (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

小禮物走一走，來簡書關注我