1. Очередь

Вспомним карточную игру «Пьяница». Играют двое, у каждого исходно по половине колоды карт. За один ход двое вскрывают по верхней карте из своих стопок. Чья карта старше, тот забирает две вскрытые карты и кладёт под низ своей стопки.

Будем считать, что про любые две карты в колоде можно сказать, какая из них старше. Будем обозначать карты натуральными числами, и пусть большее число бьёт меньшее. Колоду будем представлять списком. Для простоты рассмотрим случай шести карт в колоде:

first_hand = [4, 1, 3]
second_hand = [2, 6, 5]
# порядок карт:
# [верхняя карта, середина ... середина, нижняя карта]

first_hand = [1, 3, 4, 2]
second_hand = [6, 5]

Для моделирования этой ситуации полезно стопку каждого игрока представлять структурой данных «очередь». Сформулируем требования к очереди.

• Очередь должна хранить упорядоченный набор элементов.
• Очередь должна поддерживать операцию push(x), которая принимает новый элемент и добавляет его в конец набора.
• Очередь должна поддерживать операцию pop(), которая возвращает первый элемент набора и удаляет его.

Очень просто реализовать очередь, использую стандартные операции со списком:

queue = []  # список для хранения элементов

def push(x):
    queue.append(x)

def pop():
    return queue.pop(0)

push(3)
push(5)
print(pop())  # 3
print(pop())  # 5

У такой реализации очереди есть существенный недостаток: время работы операций. Стандартная реализация списков в Питоне гарантирует, что append() выполняется в среднем за O(1). Но вот операция pop(0) выполняется за O(n), где n — текущий размер очереди. Действительно, при её выполнении все элементы списка сдвинутся в памяти на одну ячейку влево, т. е. произойдёт n копирований адресов объектов.

Тем не менее, можно предложить реализацию очереди, в которой обе операции будут выполняться за O(1). Для этого немного модифицируем исходное решение. Будем хранить индекс head первого элемента очереди. Изначально head = 0. При каждом удалении элемента из очереди мы будем просто смещать этот индекс на одну позицию вправо, не производя физического удаления элементов из очереди.

queue = []  # список для хранения элементов
head = 0  # индекс первого реального элемента в очереди

def push(x):
    queue.append(x)

def pop():
    global head  
    # поскольку мы изменяем глобальную переменную,
    # мы должны явно написать, что она глобальная

    head += 1
    return queue[head - 1]

push(3)
push(5)
print(pop())  # 3
print(pop())  # 5