Основы алгоритмов и структур данных

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

Полный доступ к материалам

Зарегистрируйтесь и получите доступ к этому и десяткам других курсов

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

+ 2 * 4 + 5 = 16, но (3 + 2)* (4 + 5) = 45.

Далеко не все помнят из школьной математики приоритеты сложения и умножения, поэтому в социальных сетях распространены задачи «Сколько будет 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() уже присутствуют в массиве, поэтому мы можем использовать их как есть:

Javascript

class Stack {
  items = []

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

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

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

Python

class Stack:
    items = []

    def push(self, value):
        self.items.append(value)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0

PHP

<?php

class Stack {
    public $items = [];

    public function push($value)
    {
        array_push($this->items, $value);
    }

    public function pop()
    {
        return array_pop($this->items);
    }

    public function isEmpty()
    {
        return count($this->items) == 0;
    }
}

Java

import java.util.List;
import java.util.ArrayList;

class Stack<T> {
    List<T> items = new ArrayList<>();

    public void push(T item) {
        items.add(item);
    }

    public T pop() {
        var lastElementIndex = items.size() - 1;
        var lastElement = (T) items.get(lastElementIndex);
        items.remove(lastElementIndex);
        return lastElement;
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }
}

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

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

Javascript

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

Python

stack = Stack()
expression = '3 2 + 4 5 + *'
lexems = expression.split(' ')
for lexem in lexems:
    # В Python версии 3.10 и выше возможно использовать конструкцию match/case, но в данном случае рассмотрим реализацию через if/else
    if lexem == '+':
        a = stack.pop()
        b = stack.pop()
        stack.push(a + b)

    elif lexem == '-':
        a = stack.pop()
        b = stack.pop()
        stack.push(a - b)

    elif lexem == '*':
        a = stack.pop()
        b = stack.pop()
        stack.push(a * b)

    elif lexem == '/':
        a = stack.pop()
        b = stack.pop()
        stack.push(a / b)

    else:
        stack.push(float(lexem))

print(stack.pop())  # 45

PHP

<?php

$stack = new Stack();
$expression = '3 2 + 4 5 + *';
$lexems = explode(' ', $expression);
foreach ($lexems as $lexem) {
    $a;
    $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(floatval($lexem));
    }
}

print_r($stack->pop()); // 45

Java

var stack = new Stack();
var expression = "3 2 + 4 5 + *";
String[] lexems = expression.split(" ");
for (String lexem : lexems) {
    float a;
    float 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(Float.parseFloat(lexem));
    }
}

stack.pop(); // 45

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

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

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

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

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

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

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

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

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

Javascript

class Stack {
  items = new LinkedList()

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

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

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

Python

class Stack:
    items = LinkedList()

    def push(self, value):
        self.items.add(value)

    def pop(self):
        return self.items.remove()

    def is_empty(self):
        return self.items.head is None

PHP

<?php

class Stack {
    public function __construct()
    {
        $this->items = new LinkedList();;
    }

    public function push($value)
    {
        $this->items->add($value);
    }

    public function pop()
    {
        return $this->items->remove();
    }

    public function isEmpty()
    {
        return $this->items->head === null;
    }
}

Java

class Stack {
    LinkedList items = new LinkedList();

    public <T> void push(T value) {
        items.add(value);
    }

    public <T> T pop() {
        return (T) items.remove();
    }

    public boolean isEmpty() {
        return items.head == null;
    }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

push()
pop()
isEmpty()

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

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

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

Javascript

class Queue {
  items = new DoublyLinkedList()

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

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

Python

class Queue:
    items = DoublyLinkedList()

    def push(self, value):
        self.items.insert_begin(value)

    def is_empty(self):
        return self.items.head is None

PHP

<?php

class Queue {

    public function __costruct() {
        $this->items = new DoublyLinkedList();
    }

    public function push($value)
    {
        $this->items->insertBegin($value);
    }

    public function isEmpty() {
        return $this->items->head === null;
    }
}

Java

class Queue {
    DoublyLinkedList items = new DoublyLinkedList();

    public <T> void push(T value) {
        items.insertBegin(value);
    }

    public boolean isEmpty() {
        return items.head == null;
    }
}

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

LIFO и FIFO

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

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

Выводы

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

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

Каталог

Полный список доступных курсов по разным направлениям

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

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

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

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

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

LIFO и FIFO

Выводы

Рекомендуемые программы

Каталог