Теория: Очередь и стек

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

Далеко не все помнят из школьной математики приоритеты сложения и умножения, поэтому в социальных сетях распространены задачи «Сколько будет 3 + 2 * 4 + 5?».

Польский математик Ян Лукасевич около ста лет назад предложил необычный способ записи выражений, в котором не нужны ни приоритеты операций, ни скобки. Сейчас этот способ называют обратной польской записью.

Обратная запись непривычна и не получила широкого распространения, но ее можно встретить в таких языках программирования, как Forth и PostScript. * В обратной польской записи знак операции записывается не между операндами, а после них. Посмотрим, как это выглядит на примерах:

• Обычная запись — 3 + 2, обратная — 3 2 +
• Обычная запись — (3 + 2) * (4 + 5), обратная — 3 2 4 5 + + *

Операторы в обратной записи не всегда должны быть в конце. Например, 3 + 2 * 4 + 5 можно записать так:

3 2 + 4 5 + *

Эта запись читается слева направо и воспринимается так:

• Число 3
• Число 2
• Операция сложения
• Число 4
• Число 5
• Операция сложения
• Операция умножения

Преимущество обратных выражений в том, что они не вызывают разночтения.

Чтобы разобраться на примере, дальше мы пошагово вычислим это выражение:

3 2 + 4 5 + *

Шаг 1. Берем из стопки два верхних числа — 3 и 2. Выполняем над ними первую операцию — сложение:

3 + 2 = 5

Шаг 2. Идем дальше по выражению — нужно взять следующие два значения и второй оператор. Берем эти значения и применяем к ним вторую операцию сложения:

4 + 5 = 9

Шаг 3. Вспомним изначальное выражение:

3 2 4 5 + + *

Мы провели две операции сложения. Оставим только умножение и запишем в выражение результаты первых двух вычислений:

5 9 *

Шаг 4. Проводим последнюю операцию и получаем результат:

5 * 9 = 45

Алгоритм вычисления очень прост, но требует новой для нас структуры данных. Представьте, что в вычислениях выше мы бы записывали каждое число на карточки и складывали бы из них стопку. Наверху стопки лежало бы число 45.

В программировании такие стопки называются стеком — от английского stack, то есть стопка или кипа.

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

В отличие от ранее изученных нами структур, стек обычно реализуют поверх других структур — массива или односвязного списка.

Реализация стека через массив

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

Разные реализации могут быть непохожи друг на друга, но мы всегда ожидаем найти основные методы — конечно, у разных структур они разные. У стека должны быть реализованы три обязательных метода:

• Метод push() помещает элемент на вершину стека, как карточку наверх стопки
• Метод pop() убирает элемент с вершины и возвращает его
• Метод isEmpty() проверяет, пуст ли стек

В JavaScript методы push() и pop() уже присутствуют в массиве, поэтому мы можем использовать их как есть:

class Stack {
  items = []

  push(value) {
    this.items.push(value)
  }

  pop() {
    return this.items.pop()
  }

  isEmpty() {
    return this.items.length == 0
  }
}

Метод isEmpty() возвращает true, потому что массив пуст — содержит 0 элементов.

Воспользуемся нашим стеком, чтобы вычислить значение выражения 3 2 + 4 5 + *:

let stack = new Stack()
const expression = '3 2 + 4 5 + *'
const lexems = expression.split(' ')
for (lexem of lexems) {
  let a
  let b
  switch (lexem) {
    case '+':
      b = stack.pop()
      a = stack.pop()
      stack.push(a + b)
      break
    case '-':
      b = stack.pop()
      a = stack.pop()
      stack.push(a - b)
      break
    case '*':
      b = stack.pop()
      a = stack.pop()
      stack.push(a * b)
      break
    case '/':
      b = stack.pop()
      a = stack.pop()
      stack.push(a / b)
      break
    default:
      stack.push(parseFloat(lexem))
  }
}

console.log(stack.pop()) // 45

Как видите, решение не очень сложное. Мы разбиваем строку с выражением на лексемы и обрабатываем каждую лексему в цикле.

Если лексема — это знак операции, то мы «снимаем» с вершины стека два числа, выполняем операцию и помещаем результат обратно на стек.

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

Порядок операндов не важен для таких операций, как сложение и умножение, потому что 3 + 2 равно 2 + 3. Но при делении это уже не так — 3 / 2 не равно 2 / 3.

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

После завершения цикла на вершине стека должен храниться результат.

Реализация стека через односвязный список

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

Метод push() будет добавлять узел в начало списка, а pop() — удалять узел из начала:

class Stack {
  items = new LinkedList()

  push(value) {
    this.items.add(value)
  }

  pop() {
    return this.items.remove()
  }

  isEmpty() {
    return this.items.head == null
  }
}

Метод isEmpty() проверяет, есть ли у списка голова. Если в списке нет ни одного узла, поле head будет содержать null — это означает, что стек пуст.

Методы в старом и новом классах Stack выглядят совершенно одинаково: имеют одинаковые названия, параметры и поведение. Поэтому вместо старой реализации нового стека мы можем использовать новую. Она будет немного быстрее, но чтобы это заметить, нам потребуются достаточно большие выражения.

Накопление и отправка изменения

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

Программы часто хранят данные в облаке — то есть на серверах в интернете. Скажем, календарь нам нужен не только на смартфоне, но и на ноутбуке. А иногда нужно не только предоставить доступ с разных устройств, но и надежно хранить данные. В облаке надежнее, чем на смартфоне.

В теории, как только в программе появляются новые данные, она должна отправить их на сервер. Например, трекер понимает, что наша позиция изменилась и посылает в облако новые координаты.

Но мобильная связь не всегда надежна и мы регулярно оказываемся без интернета. Простые программы в этом случае показывают ошибку подключения.

Однако, кратковременная потеря связи — это штатная ситуация и современные программы научились с ней справляться. Если связи нет, они складывают данные во временное хранилище, а когда связь появляется, отправляют их на сервер.

Но для хранения данных подойдет не любое хранилище. Представим, что программа-трекер складывает координаты в стек. Из стека координаты извлекаются в обратном порядке, как будто человек двигался задом наперед.

Нам нужна структура данных, похожая на стек и проводящая те же операции — поместить и извлечь. При этом в отличие от стека, она не должна менять порядок элементов. Это похоже на очередь в магазине, где люди обслуживаются в том же порядке, в котором они подошли к кассе.

Такая структура действительно существует. Она называется очередь, а по английски — queue.

Реализация очереди через двусвязный список

Как и в стеке, в очереди есть три основных метода:

• push()
• pop()
• isEmpty()

Отличие в том, что в стеке элементы вставляются и извлекаются с одного конца. В очереди элементы вставляются с одного конца, а извлекаются из другого.

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

Зато для этой цели подходит двусвязный список, одинаково быстро работающий как в начале, так и в конце:

class Queue {
  items = new DoublyLinkedList()

  push(value) {
    this.items.insertBegin(value)
  }

  isEmpty() {
    return this.items.head == null
  }
}

Операция push() сводится к вставке узла в начало двусвязного списка. А реализация pop() останется вам в виде упражнения.

LIFO и FIFO

Иногда в технической литературе вместо терминов стек и очередь, можно встретить другие термины:

• Стек или список LIFO — Last In First Out (последним пришел — первым ушел)
• Очередь или список FIFO — First In First Out (первым пришел — первым ушел)

Выводы

Повторим ключевые моменты из этого урока:

• Стеки и очереди полезны для решения широкого круга задач
• Стек может быть реализован либо с помощью массива, либо с помощью односвязного списка
• Очередь может быть реализована с помощью двусвязного списка
• Работу стека описывает принцип LIFO (последним пришел — первым ушел)
• Работу очереди описывает принцип FIFO (первым пришел — первым ушел)