Стеки и очереди

Обзор

Стеки и очереди — это распространённые структуры данных в информатике, в которых определён порядок добавления и удаления элементов. С их помощью вы можете контролировать порядок взаимодействия с данными:

• Стек: контейнер, в который вы добавляете и из которого удаляете элементы в порядке «первый вошёл — последний вышел» (first-in-last-out, или FILO). В качестве аналогии можно представить стопку книг, из которой вы всегда берёте верхнюю книгу.

• Очередь: контейнер, в который вы добавляете и из которого удаляете элементы в порядке «первый вошёл — первый вышел» (first-in-first-out, или FIFO). Аналогия — очередь клиентов, ожидающих еду.

Хотя базовый код стеков и очередей схож, у каждой структуры данных есть ключевые отличия и сильные стороны, которые можно использовать, чтобы сделать программу быстрой, эффективной и интуитивно понятной.

Стеки

Стек можно представить себе как стопку блинов. Предположим, вы завтракаете в ресторане и официант подаёт вам бесконечную стопку блинов. Из вежливости вы будете брать только один блин за раз и только с верха стопки. Вы можете попросить официанта загрузить новый блин на верх стопки, а когда проголодаетесь, можете извлечь блин с вершины стопки и положить на свою тарелку, чтобы съесть его. Если вы хотите съесть определённый блин из середины стопки, вам придётся съесть все блины сверху, чтобы добраться до нужного. Первый добавленный блин будет последним, который вы сможете взять. Таким образом, стек является структурой данных FILO, или first-in-last-out (первый вошёл — последний вышел).

Когда использовать

Стеки полезны, когда требуется обратное отслеживание или нужно сохранять информацию о том, в каком порядке возникали события. Это может быть функция отмены, цепочка событий или ряд вариантов для выбора. К примеру, у вас есть робот, которому нужно пройти лабиринт с ответвлениями. Когда робот доходит до развилки в лабиринте, он делает выбор и загружает информацию о нём в стек. Когда робот заходит в тупик, он возвращается назад по стеку, извлекая из него информацию о принятых решениях, пока не найдёт новый путь, по которому можно пройти.

Реализация в Verse

API Verse не имеет встроенной реализации стеков, но вы можете реализовать их самостоятельно.

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

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Массив Elements хранит в стеке объекты типа t. Это означает, что вы можете инициализировать стек элементом любого типа, например int, float, stack и т. д. Использование type в качестве аргумента класса стека является примером [параметрического типа](parametric-types-in-verse).

Сначала определим несколько вспомогательных функций. Вам нужно знать, где находится вершина стека, чтобы использовать методы Push() и Pop() для загрузки и извлечения элементов. Для этого вам понадобятся три функции, а именно Size(), IsEmpty() и Peek().

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

Функция Size() просто возвращает Length (длину) массива Elements. Функция IsEmpty() вызывает функцию Size() и имеет спецификатор <transacts>, то есть она не вернёт результат, если Size() не равен 0.

Функция Peek() возвращает элемент массива с максимальным индексом (Length – 1). Эта функция имеет спецификаторы <decides><transacts>, поскольку обращение к массиву может не дать результата, если массив пуст.

Для создания экземпляра стека можно использовать функцию конструктора. Конструктор — это специальная функция, которая создаёт экземпляр связанного с ней класса. Конструктор инициализирует объект. С помощью конструктора можно получить доступ к массиву Elements и присвоить ему начальный массив элементов.

# Creates and returns a stack from an initial array of elements InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

Загрузка и извлечение

Чтобы добавить или удалить элементы стека, нужно либо загрузить (push) новый элемент на вершину стека, либо извлечь (pop) его с вершины.

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

Функция Push() принимает в качестве аргумента элемент, который нужно поместить на вершину стека, и возвращает новый стек с этим элементом на вершине. Возврат нового стека вместо изменения текущего стека является примером функционального программирования и снижает риск побочных эффектов.

Чтобы реализовать функцию Pop(), нужно сначала найти элемент на вершине стека с помощью функции Peek(). Затем нужно удалить верхний элемент (с помощью функции RemoveElement[]) и вернуть новый стек без этого элемента. Вы можете использовать кортеж, чтобы одновременно вернуть новый стек и удалённый элемент. Из-за выражений с неоднозначным результатом, используемых для обращения к массиву и вызова функции Peek(), функция Pop() должна иметь спецификаторы <decides><transacts>.

Полный код

Полный код класса стека приведён ниже.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

Очереди

Очередь можно представить себе как конвейерную ленту с суши. Предположим, вы находитесь в суши-ресторане, который отправляет вам на конвейерной ленте тарелки с суши по одной, и они прибывают в том порядке, в каком были заказаны. Вы можете извлечь из очереди тарелку в начале очереди, чтобы взять её и съесть блюдо, но за раз вы можете взять только одну тарелку. Когда вы хотите заказать новую тарелку, вы просите повара добавить тарелку в конец очереди. Если в очереди уже есть другие тарелки с суши, вам придётся взять все тарелки с начала очереди, чтобы добраться до тарелки в конце. Первая поставленная тарелка с суши будет первой, которую вы возьмёте. Это делает очередь структурой данных FIFO (first-in-first-out — «первый вошёл — первый вышел»).

Когда использовать

Очереди полезны, когда нужно обрабатывать данные в зависимости от времени их поступления. Это может быть обслуживание клиентов в автокафе, выстраивание очереди звонков в колл-центре или задание игроку ряда вопросов в рамках опроса. Например, если требуется создать комнату ожидания для игроков, где они будут находиться, пока выполняют задание или проходят уровень по одному, вы можете использовать очередь, чтобы упорядочить игроков по времени их прибытия в порядке «первый вошёл — первый вышел».

Реализация в Verse

API Verse не имеет встроенной реализации очередей, но вы можете реализовать их самостоятельно.

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

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Массив Elements хранит в очереди объекты типа t. Это означает, что вы можете инициализировать очередь элементом любого типа, например int, float, queue и т. д. Использование type в качестве аргумента класса стека является примером [параметрического типа](parametric-types-in-verse).

Как и для стеков, для очередей необходимо несколько вспомогательных функций. Для определения начала и конца очереди будем использовать функции Enqueue() и Dequeue(). Также полезно знать размер очереди и то, пуста ли она. Таким образом, нужно определить четыре функции — Size(), IsEmpty(), Front() и Back().

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

Функция Size() возвращает Length (длину) массива Elements. Функция IsEmpty() вызывает функцию Size() и имеет спецификатор <transacts>, то есть она не вернёт результат, если Size() не равен 0.

Функции Front() и Rear() возвращают первый (с индексом 0) и последний (с индексом Length – 1) элементы массива. Обе эти функции имеют спецификаторы <decides><transacts>, поскольку обращение к массиву может не дать результата, если массив пуст.

Как и в случае с классом stack, для инициализации элементов массива Elements в классе queue следует использовать функцию-конструктор. С помощью функции-конструктора можно обратиться к значению массива Elements и присвоить ему начальный массив элементов.

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Функции включения в очередь (Enqueue) и удаления из очереди (Dequeue)

Чтобы добавить или удалить элемент очереди, нужно либо включить новый элемент в конец очереди, либо удалить элемент из её начала.

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

Функция Enqueue() принимает в качестве аргумента элемент, который вы хотите вставить в очередь, и возвращает новую очередь с новым элементом в конце. Возврат новой очереди вместо изменения текущей очереди является примером функционального программирования и снижает риск побочных эффектов.

Для реализации функции Dequeue() необходимо удалить и вернуть элемент в начале очереди, а также вернуть новую очередь с удалённым первым элементом (с помощью функции RemoveElement[]). Из-за выражений с неоднозначным результатом, используемых для обращения к массиву и вызова функции Front(), функция Dequeue() должна иметь спецификаторы <decides><transacts>.

Полный код

Полный код класса очереди приведён ниже.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

Самостоятельная работа

Существует множество способов перебирать элементы и расширять возможности стеков и очередей, поэтому исследуйте различные способы добавления новых функций. Вот несколько идей для начала:

• Можете ли вы сделать очередь циклической, чтобы последний элемент соединялся с первым и очередь образовывала бесконечную последовательность?

• А как насчёт приоритетной очереди, в которой объекты упорядочиваются на основе времени их включения в очередь И некоторого другого значения?

• Подумайте, как можно использовать концепцию стека при создании игры, такой как Ханойская башня. А как насчёт игры про ресторан, в которой клиенты ждут заказа в очереди?