Упражнение 15: Стеки и очереди

Оригинал: Exercise 15: Stacks and Queues

Переводчик: Феликс Ли

Лицензия: CC BY-NC-SA 4.0

Гордо использует Google Translate

Когда вы работаете с данными структурами, вы часто встречаетесь со структурой, которая похожа на другую структуру. Stack похож на SingleLinkedList из упражнения 13, а также Queue похож на DoubleLinkedList из упражнения 14. Единственное отличие заключается в том, что Stack и Queue ограничивают возможные операции, чтобы упростить их использование. Это помогает уменьшить ошибки, потому что вы не можете случайно использовать Stack, как если бы это был Queue, и создать проблемы. В Stack узлы "вталкиваются" в вершину "стека", а затем "выталкиваются" оттуда же. В очередях узлы "вталкиваются" в конец, а затем "выталкиваются" из начала. Эти операции являются упрощением SingleLinkedList и DoubleLinkedList, где Stack позволяет только операциям push и pop, а Queue — только операциям shift и unshift.

Примечание переводчика: На самом деле, это push и unshift.При визуализации стека вам следует представить себе кучу книг на вашем полу. Представьте себе те тяжёлые художественные книги на полках; если я сложу около двадцати таких книг, они могут весить около ста фунтов. Когда вы строите стек для этих книг, вы не можете поднять весь стек и положить книгу внизу, правильно? Нет, вы кладете книгу сверху. Вы кладете её там, но мы также можем использовать термин "вталкивать". Если вы хотите получить книгу из стека, вы можете поднять несколько книг, взять одну книгу, но в конце концов вам придётся вытащить несколько книг с вершины, чтобы достать книгу снизу. Вы можете поднимать каждую книгу с вершины, или в нашем примере, мы скажем, что "выталкиваем книгу".Если вы представляете себе очередь в банке, она имеет "начало" и "конец". Визуализация такой очереди становится очень простой. Обычно существует лабиринт из верёвок, где конец служит входом, а выход контролируется контроллером. Вы можете войти в эту очередь через "конец" этого лабиринта верёвок; мы называем это shift, поскольку это общепринятое программистское название для этой структуры данных Queue. Как только вы попали в банк (очередь), вы не можете пропустить очередь и покинуть её, иначе остальные люди будут злиться. Поэтому вам нужно ждать, пока каждый перед вами не покинет очередь (это unshift для вас). Когда вы достигнете начала, вы сможете покинуть очередь, мы также называем это unshift.

Часто можно найти реальные примеры таких структур данных, чтобы помочь вам визуализировать их работу. Теперь вы должны потратить немного времени на создание этих сцен или фактического получения книги по стекам и тестирования этих операций. Вы можете найти другие реальные ситуации, аналогичные Stack и Queue?

Упражнение на основе кода

Теперь я хочу, чтобы вы выполнили упражнение на основе кода и реализовали эти структуры данных согласно их описанию. В этом упражнении вы сначала используете начальный код здесь и SingleLinkedList, который вы узнали из упражнения OnClickListener, чтобы реализовать структуру данных Stack. После завершения этого шага вы попробуете реализовать структуру данных Queue с нуля.Класс узла StackNode почти такой же, как и SingleLinkedListNode, за исключением того, что я просто скопировал его и переименовал:

class StackNode(object):

    def __init__(self, value, nxt):
        self.value = value
        self.next = nxt

    def __repr__(self):
        nval = self.next and self.next.value or None
        return f"[{self.value}:{repr(nval)}]"

Контрольный класс Stack очень похож на SingleLinkedList, за исключением того, что я использовал top вместо first. Это соответствует концепции стека.

class Stack(object):

    def __init__(self):
        self.top = None

    def push(self, obj):
        """Добавляет новый объект на вершину стека."""

    def pop(self):
        """Удаляет объект с вершины стека."""

    def top(self):
        """Возвращает ссылку на верхний объект, но не удаляет его."""

    def count(self):
        """Подсчитывает количество элементов в стеке."""

    def dump(self, mark="----"):
        """Функция отладки, которая выводит содержимое стека."""

Теперь ваша задача — реализовать Stack и выполнить тесты для него, аналогично тем, которые вы выполнили в упражнении 13. Убедитесь, что ваши тесты охватывают каждую операцию, и вы можете использовать любой подход. Помните, что несмотря на это, операция push стека должна добавляться на вершину, поэтому есть ссылка на вершину.Как только вы сделаете Stack работоспособной, вам следует реализовать Queue, но она основана на DoubleLinkedList. (Примечание переводчика: На самом деле, можно использовать и односвязный список, так как единственная сложность заключается в удалении элемента с конца списка. Вы можете добавлять элементы в конец и удалять их с начала.) Содержимое должно быть таким же, как и внутренняя структура SingleLinkedList, с тем отличием, что разрешённые функции будут другими. То же самое относится к Queue. Потратьте немного времени на создание схемы работы очереди и понимание того, как она ограничивает DoubleLinkedList. Как только вы закончите, создайте свою очередь.## Повредите егоПовреждение этих данных происходит просто потому, что не поддерживаются ограничения. Посмотрите, что произойдет, если операция не может использовать правильный хвост.

Вы также можете заметить, что существует "постоянная ошибка смещения". В моей реализации, когда структура пустая, я устанавливаю self.top = None. Это значит, что при достижении нулевого количества элементов вам следует выполнять специальное обработание self.top. Одним из альтернативных подходов является всегда делать так, чтобы self.top указывал на объект StackNode (фиктивный головной узел) и считать структуру пустой, когда этот последний элемент присутствует. Попробуйте это и посмотрите, как это изменяет вашу реализацию. Будет ли это более склонно к ошибкам или менее?

Глубокое изучение

Многие операции над этими данными очень неэффективны. Обратитесь к коду, который вы написали для каждого типа данных, и попытайтесь догадаться, какие функции самые медленные. Как только у вас будут идеи, попытайтесь объяснить, почему они могут быть медленными. Изучите взгляды других людей на эти данные. В упражнениях 18 и 19 вы узнаете, как провести анализ производительности этих структур данных и выполнить некоторые изменения.

Наконец, действительно требуется создать новую структуру данных или достаточно просто "обернуть" SingleLinkedList и DoubleLinkedList? Как это повлияет на ваш дизайн?