- Реализация стека через массив
- Реализация стека через односвязный список
- Накопление и отправка изменения
- Реализация очереди через двусвязный список
- LIFO и FIFO
- Выводы
Мы привыкли записывать математические выражения, опираясь на приоритет операций и на скобки. Именно поэтому: , но .
Далеко не все помнят из школьной математики приоритеты сложения и умножения, поэтому в социальных сетях распространены задачи «Сколько будет ».
Польский математик Ян Лукасевич около ста лет назад предложил необычный способ записи выражений, в котором не нужны ни приоритеты операций, ни скобки. Сейчас этот способ называют обратной польской записью.
Обратная запись непривычна и не получила широкого распространения, но ее можно встретить в таких языках программирования, как Forth и PostScript.
В обратной польской записи знак операции записывается не между операндами, а после них. Посмотрим, как это выглядит на примерах:
-
Обычная запись — , обратная —
-
Обычная запись — , обратная —
Операторы в обратной записи не всегда должны быть в конце. Например, можно записать так:
Эта запись читается слева направо и воспринимается так:
-
Число
-
Число
-
Операция сложения
-
Число
-
Число
-
Операция сложения
-
Операция умножения
Преимущество обратных выражений в том, что они не вызывают разночтения.
Чтобы разобраться на примере, дальше мы пошагово вычислим это выражение:
Шаг 1. Берем из стопки два верхних числа — и . Выполняем над ними первую операцию — сложение:
Шаг 2. Идем дальше по выражению — нужно взять следующие два значения и второй оператор. Берем эти значения и применяем к ним вторую операцию сложения:
Шаг 3. Вспомним изначальное выражение:
Мы провели две операции сложения. Оставим только умножение и запишем в выражение результаты первых двух вычислений:
Шаг 4. Проводим последнюю операцию и получаем результат:
Алгоритм вычисления очень прост, но требует новой для нас структуры данных. Представьте, что в вычислениях выше мы бы записывали каждое число на карточки и складывали бы из них стопку. Наверху стопки лежало бы число 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;
}
}https://replit.com/@hexlet/js-stack#index.js
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) == 0https://replit.com/@hexlet/python-stack#main.py
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;
}
}https://replit.com/@hexlet/php-stack#main.php
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();
}
}https://replit.com/@hexlet/java-stack#src/main/java/Stack.java
Метод isEmpty() возвращает true, потому что массив пуст — содержит
элементов.
Воспользуемся нашим стеком, чтобы вычислить значение выражения :
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()); // 45Python
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()) # 45PHP
<?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()); // 45Java
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.
Порядок операндов не важен для таких операций, как сложение и умножение, потому что равно . Но при делении это уже не так — не равно .
Если лексема не похожа на знак операции, мы считаем, что это число. Тогда с помощью функции 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;
}
}https://replit.com/@hexlet/js-stack-ll#index.js
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 Nonehttps://replit.com/@hexlet/python-stack-ll#main.py
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;
}
}https://replit.com/@hexlet/php-stack-ll#main.php
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;
}
}https://replit.com/@hexlet/java-stack-ll#src/main/java/Main.java
Метод 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;
}
}https://replit.com/@hexlet/js-queue#index.js
Python
class Queue:
items = DoublyLinkedList()
def push(self, value):
self.items.insert_begin(value)
def is_empty(self):
return self.items.head is Nonehttps://replit.com/@hexlet/python-queue#main.py
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;
}
}https://replit.com/@hexlet/php-queue#main.php
Java
class Queue {
DoublyLinkedList items = new DoublyLinkedList();
public <T> void push(T value) {
items.insertBegin(value);
}
public boolean isEmpty() {
return items.head == null;
}
}https://replit.com/@hexlet/java-queue#src/main/java/Queue.java
Операция push() сводится к вставке узла в начало двусвязного списка. А реализация pop() останется вам в виде упражнения.
LIFO и FIFO
Иногда в технической литературе вместо терминов стек и очередь, можно встретить другие термины:
-
Стек или список LIFO — Last In First Out (последним пришел — первым ушел)
-
Очередь или список FIFO — First In First Out (первым пришел — первым ушел)
Выводы
Повторим ключевые моменты из этого урока:
-
Стеки и очереди полезны для решения широкого круга задач
-
Стек может быть реализован либо с помощью массива, либо с помощью односвязного списка
-
Очередь может быть реализована с помощью двусвязного списка
-
Работу стека описывает принцип LIFO (последним пришел — первым ушел)
-
Работу очереди описывает принцип FIFO (первым пришел — первым ушел)
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
