Стеки

Стек (stack) - это структура данных, в которой данные, записанные сперва, извлекаются в конце. Стек работает по принципу FILO (First In – Last Out), то есть если имеется стек $[8, 3, 5, 10, -21, “trololo”]$, первым будет извлекаться элемент $”trololo”$, затем $-21$, $10$ и так далее.

Стек удобно представить в виде какой-нибудь узкой емкости, например, коробки для теннисных мячиков со дном.

Мы можем взять мячик только сверху и положить новый можем только наверх. Для этого определены методы .push() и .pop() для добавления и удаления соответственно, при этом каждая операция работает за $O(1)$.

Реализация стеков на Python

На Python стеки реализуются как массивы, ведь по сути это они и есть, так как методы .append() и .pop() выполняют те же функции, что и .push() и .pop().

    stack = [1, 34, -88, 90.01]

    stack.append("never gonna give you up")
    stack.append(True)
    print(stack)

    print(stack.pop())
    print(stack)
    print(stack.pop())
    print(stack)

Вывод:

[1, 34, -88, 90.01, ‘never gonna give you up’, True]
True
[1, 34, -88, 90.01, ‘never gonna give you up’]
‘never gonna give you up’
[1, 34, -88, 90.01]

Обратите внимание, что команда stack.pop(), записанная отдельно в строке, просто удаляет последний элемент стека, но если stack.pop() будет записано как значение переменной или аргумент функции (например, n = stack.pop() или print(stack.pop())), то в этом случае берется не стек без последнего элемента, а извлекаемый элемент. При этом последний элемент удаляется. Чтобы использовать стек без последнего элемента, нужно до использования функции или задания переменной использовать метод .pop()

    stack.pop()
    print(quicksort(stack))

Очереди

Очереди работают по обратному принципу FIFO (First In – First Out), то есть элементы добавляются в конец и извлекаются из начала. Получается, что элементы как бы “двигаются”, будто очередь.

Очередь можно представить как туннель, в который въезжают и выезжают машины.

Реализация очередей на Python

1) При помощи массива. Как и со стеками, мы будем использовать методы .append() и .pop(). У метода .pop() в качестве аргумента можно задать индекс элемента, который нужно удалить, в нашем случае, это $0$, так как извлекать элементы нужно из начала.

    queue = [1, 34, -88, 90.01]
    queue.append("never gonna give you up")
    queue.append(True)
    print(queue)

    print(queue.pop(0))
    print(queue)
    print(queue.pop(0))
    print(queue)

Вывод:

[1, 34, -88, 90.01, "never gonna give you up", True]
1
[34, -88, 90.01, "never gonna give you up", True]
34
[-88, 90.01, "never gonna give you up", True]

Но операция .pop(0) работает за $O(N)$, так как после удаления первого элемента необходимо сдвинуть все элементы на одно место назад, это очень медленно.

2) При помощи дека. Этот метод позволит ускорить извлечение до $O(1)$. Дек – это смесь стека и очереди, это позволяет извлекать элементы как с начала, так и с конца, новые элементы добавляется как в конец, так и в начало структуры (в Python метод .appendleft()).

Дек можно использовать и для реализации очереди, для этого нужно импортировать модуль deque и использовать метод .popleft():

    from collections import deque

    queue = deque([1, 34, -88, 90.01])
    queue.append("never gonna give you up")
    queue.append(True)
    print(queue)

    print(queue.popleft())
    print(queue)
    print(queue.popleft())
    print(queue)

Вывод:

[1, 34, -88, 90.01, "never gonna give you up", True]
1
[34, -88, 90.01, "never gonna give you up", True]
34
[-88, 90.01, "never gonna give you up", True]