Еще две структуры данных стек и очередь.

Куча

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