Еще две структуры данных стек и очередь.
Куча
Python не имеет специальной структуры данных для стека. В качестве стека мы можем использовать список, что также рекомендуется официальным документом.
Предположим, я объявляю стек как stack = list[]
. Наиболее часто используемый метод для стека Java может быть реализован следующим образом.
Классическая проблема допустимых скобок:
def isValid(s : str): stack = [] mapping = {"[":"]", "{":"}", "(":")"} for c in s: if c in mapping: stack.append(c) elif stack and mapping[stack[-1]] == c: stack.pop() else: return False return stack == []
Очередь
Теоретически мы также можем использовать List в качестве очереди, но это не рекомендуется. Это недостаточно эффективно. Мы все знаем, что очередь — это FIFO. Чтобы удалить первый элемент, в Java мы используем pollFirst()
. В списке Python мы также можем использовать my_list.pop(0)
, но это займет O(n) времени.
Python предоставляет специальную структуру данных deque
. Чтобы использовать это, нам нужно сначала импортировать его с помощью. Официальный документ можно найти здесь. Чтобы удалить первый элемент из очереди, мы используем queue.popleft()
. Дополнительные методы deque можно найти в документе объекты deque.
Обычно очередь используется при поиске в ширину двоичного дерева. Я реализовал использование Python.
from collections import deque class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def bfs(root: TreeNode): result = [] if not root: // if root is None return result queue = deque([root]) while queue: size = len(queue) // we get how many nodes in the level temp_list = [] for _ in range(size): node = queue.popleft() temp_list.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(temp_list) return result