Rivalry2

HTML Diff

0 added 16 removed

Original 2026-01-01

Modified 2026-02-26

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

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

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

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

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

6 <ul><li>Обычная запись - 3 + 2, обратная - 3 2 +</li>

7 <li>Обычная запись - (3 + 2) * (4 + 5), обратная - 3 2 4 5 + + *</li>

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

9 3 2 + 4 5 + *

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

11 <ul><li>Число 3</li>

12 <li>Число 2</li>

13 <li>Операция сложения</li>

14 <li>Число 4</li>

15 <li>Число 5</li>

16 <li>Операция сложения</li>

17 <li>Операция умножения</li>

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

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

20 3 2 + 4 5 + *

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

22 3 + 2 = 5

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

24 4 + 5 = 9

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

26 3 2 4 5 + + *

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

28 5 9 *

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

30 5 * 9 = 45

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

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

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

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

35 <h2>Реализация стека через массив</h2>

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

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

38 <ul><li>Метод push() помещает элемент на вершину стека, как карточку наверх стопки</li>

39 <li>Метод pop() убирает элемент с вершины и возвращает его</li>

40 <li>Метод isEmpty() проверяет, пуст ли стек</li>

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

42 - Javascript

43 - Python

44 - PHP

45 - Java

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

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

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

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

48 - Javascript

49 - Python

50 - PHP

51 - Java

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

61 - Javascript

62 - Python

63 - PHP

64 - Java

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

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

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

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

67 <h2>Накопление и отправка изменения</h2>

55 <h2>Накопление и отправка изменения</h2>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

78 <ul><li>push()</li>

66 <ul><li>push()</li>

79 <li>pop()</li>

67 <li>pop()</li>

80 <li>isEmpty()</li>

68 <li>isEmpty()</li>

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

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

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

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

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

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

84 - Javascript

85 - Python

86 - PHP

87 - Java

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

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

89 <h2>LIFO и FIFO</h2>

73 <h2>LIFO и FIFO</h2>

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

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

91 <ul><li>Стекилисписок LIFO- Last In First Out (последним пришел - первым ушел)</li>

75 <ul><li>Стекилисписок LIFO- Last In First Out (последним пришел - первым ушел)</li>

92 <li>Очередьилисписок FIFO- First In First Out (первым пришел - первым ушел)</li>

76 <li>Очередьилисписок FIFO- First In First Out (первым пришел - первым ушел)</li>

93 </ul><h2>Выводы</h2>

77 </ul><h2>Выводы</h2>

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

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

95 <ul><li>Стеки и очереди полезны для решения широкого круга задач</li>

79 <ul><li>Стеки и очереди полезны для решения широкого круга задач</li>

96 <li>Стек может быть реализован либо с помощью массива, либо с помощью односвязного списка</li>

80 <li>Стек может быть реализован либо с помощью массива, либо с помощью односвязного списка</li>

97 <li>Очередь может быть реализована с помощью двусвязного списка</li>

81 <li>Очередь может быть реализована с помощью двусвязного списка</li>

98 <li>Работу стека описывает принцип LIFO (последним пришел - первым ушел)</li>

82 <li>Работу стека описывает принцип LIFO (последним пришел - первым ушел)</li>

99 <li>Работу очереди описывает принцип FIFO (первым пришел - первым ушел)</li>

83 <li>Работу очереди описывает принцип FIFO (первым пришел - первым ушел)</li>

100 </ul>

84 </ul>