- Реализация стека через массив
- Реализация стека через односвязный список
- Накопление и отправка изменения
- Реализация очереди через двусвязный список
- LIFO и FIFO
- Выводы
Мы привыкли записывать математические выражения, опираясь на приоритет операций и на скобки. Именно поэтому:3 + 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 (первым пришел — первым ушел)
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
