1 added
1 removed
Original
2026-01-01
Modified
2026-02-21
1
<p><a>#статьи</a></p>
1
<p><a>#статьи</a></p>
2
<ul><li>1 ноя 2023</li>
2
<ul><li>1 ноя 2023</li>
3
<li>0</li>
3
<li>0</li>
4
</ul><h2>Простыми словами: что такое стек и как он устроен</h2>
4
</ul><h2>Простыми словами: что такое стек и как он устроен</h2>
5
<p>"Последним зашёл - первым вышел", или что общего между программированием и поездкой в утреннем метро.</p>
5
<p>"Последним зашёл - первым вышел", или что общего между программированием и поездкой в утреннем метро.</p>
6
<p>Иллюстрация: Оля Ежак для Skillbox Media</p>
6
<p>Иллюстрация: Оля Ежак для Skillbox Media</p>
7
<p>Программист, консультант, специалист по документированию. Легко и доступно рассказывает о сложных вещах в программировании и дизайне.</p>
7
<p>Программист, консультант, специалист по документированию. Легко и доступно рассказывает о сложных вещах в программировании и дизайне.</p>
8
<p>Если вы начинали изучать программирование, то наверняка слышали об ошибке переполнения стека. Той самой, в честь которой назвали известный айтишный сайт вопросов и ответов Stack Overflow. Пришло время разобраться, что вообще означает "стек", почему он может переполниться и чем это грозит.</p>
8
<p>Если вы начинали изучать программирование, то наверняка слышали об ошибке переполнения стека. Той самой, в честь которой назвали известный айтишный сайт вопросов и ответов Stack Overflow. Пришло время разобраться, что вообще означает "стек", почему он может переполниться и чем это грозит.</p>
9
<p>Из этой статьи вы узнаете:</p>
9
<p>Из этой статьи вы узнаете:</p>
10
<ul><li><a>Что такое стек</a></li>
10
<ul><li><a>Что такое стек</a></li>
11
<li><a>Где он используется</a></li>
11
<li><a>Где он используется</a></li>
12
<li><a>Какие у него есть реализации</a></li>
12
<li><a>Какие у него есть реализации</a></li>
13
<li><a>Что такое стек вызовов</a></li>
13
<li><a>Что такое стек вызовов</a></li>
14
<li><a>Почему он может переполниться</a></li>
14
<li><a>Почему он может переполниться</a></li>
15
<li><a>Что такое стек данных</a></li>
15
<li><a>Что такое стек данных</a></li>
16
<li><a>Что запомнить</a></li>
16
<li><a>Что запомнить</a></li>
17
</ul><p><strong>Стек (stack)</strong> - это способ организации данных в памяти компьютера. Он работает по принципу "последним пришёл, первым вышел" (last in first out, LIFO). Это значит, что последний элемент, добавленный в стек, будет взят из него первым. Добавлять новые элементы и удалять существующие из стека можно только с одного конца, который называется вершиной.</p>
17
</ul><p><strong>Стек (stack)</strong> - это способ организации данных в памяти компьютера. Он работает по принципу "последним пришёл, первым вышел" (last in first out, LIFO). Это значит, что последний элемент, добавленный в стек, будет взят из него первым. Добавлять новые элементы и удалять существующие из стека можно только с одного конца, который называется вершиной.</p>
18
<p>Представьте себе детскую пирамидку, где кольца по очереди надеваются на штырёк. Кольца идут друг за другом: мы не можем добавить новые кольца в середину или основание пирамидки - только сверху. Если мы вдруг захотим разобрать пирамидку, сначала нужно снять верхнее кольцо, затем предыдущее и так далее, пока не дойдём до нижнего.</p>
18
<p>Представьте себе детскую пирамидку, где кольца по очереди надеваются на штырёк. Кольца идут друг за другом: мы не можем добавить новые кольца в середину или основание пирамидки - только сверху. Если мы вдруг захотим разобрать пирамидку, сначала нужно снять верхнее кольцо, затем предыдущее и так далее, пока не дойдём до нижнего.</p>
19
<p>Так же устроен и стек: чем выше элемент находится в пирамиде, тем раньше его заберут. Этим стеки отличаются от <strong>очереди (queue)</strong> - структуры данных, где первым используется элемент, который появился раньше всех. Если очередь формируется возле кассы в "Пятёрочке", то стек - в забитом вагоне метро, где первым выходит тот, кто зашёл последним.</p>
19
<p>Так же устроен и стек: чем выше элемент находится в пирамиде, тем раньше его заберут. Этим стеки отличаются от <strong>очереди (queue)</strong> - структуры данных, где первым используется элемент, который появился раньше всех. Если очередь формируется возле кассы в "Пятёрочке", то стек - в забитом вагоне метро, где первым выходит тот, кто зашёл последним.</p>
20
<p>Если переложить нашу аналогию на язык компьютеров, получится несколько базовых команд, которые можно использовать со стеками:</p>
20
<p>Если переложить нашу аналогию на язык компьютеров, получится несколько базовых команд, которые можно использовать со стеками:</p>
21
<ul><li><strong>push</strong>- добавляет элемент на вершину стека.</li>
21
<ul><li><strong>push</strong>- добавляет элемент на вершину стека.</li>
22
<li><strong>pop</strong>- удаляет элемент с вершины стека.</li>
22
<li><strong>pop</strong>- удаляет элемент с вершины стека.</li>
23
<li><strong>peek</strong>- считывает элемент с вершины стека без его удаления.</li>
23
<li><strong>peek</strong>- считывает элемент с вершины стека без его удаления.</li>
24
<li><strong>isEmpty</strong>- проверяет, пуст ли стек.</li>
24
<li><strong>isEmpty</strong>- проверяет, пуст ли стек.</li>
25
<li><strong>size</strong>- возвращает количество элементов в стеке.</li>
25
<li><strong>size</strong>- возвращает количество элементов в стеке.</li>
26
</ul><p>В зависимости от языка и способа реализации команды могут различаться, но этот список - база, без которой невозможно двигаться дальше.</p>
26
</ul><p>В зависимости от языка и способа реализации команды могут различаться, но этот список - база, без которой невозможно двигаться дальше.</p>
27
<p>Считается, что первым понятие стека ввёл в обиход ввёл<a>Алан Тьюринг</a>во время работы над прообразом современного компьютера. Позже эту идею запатентовали немецкие учёные Клаус Самельсон и Фридрих Л. Бауэр.</p>
27
<p>Считается, что первым понятие стека ввёл в обиход ввёл<a>Алан Тьюринг</a>во время работы над прообразом современного компьютера. Позже эту идею запатентовали немецкие учёные Клаус Самельсон и Фридрих Л. Бауэр.</p>
28
<p>Частый сценарий использования стеков - реализация операции отмены в текстовых и графических редакторах. Например, нарисовали вы тень для кнопки в Figma - в стеке отмены появилась операция "Добавить тень". Если вы решите вернуть как было, компьютер быстро достанет последний элемент в стеке и ему не придётся перебирать всю хронологию ваших действий.</p>
28
<p>Частый сценарий использования стеков - реализация операции отмены в текстовых и графических редакторах. Например, нарисовали вы тень для кнопки в Figma - в стеке отмены появилась операция "Добавить тень". Если вы решите вернуть как было, компьютер быстро достанет последний элемент в стеке и ему не придётся перебирать всю хронологию ваших действий.</p>
29
<p>У этого есть и обратная сторона - чем дольше вы работаете над файлом, тем сильнее разрастается стек и тем больше он подъедает оперативки. Поэтому тот же Photoshop может начать тормозить после определённого количества операций. А если памяти мало изначально, система может выдавать ошибку переполнения стекового буфера.</p>
29
<p>У этого есть и обратная сторона - чем дольше вы работаете над файлом, тем сильнее разрастается стек и тем больше он подъедает оперативки. Поэтому тот же Photoshop может начать тормозить после определённого количества операций. А если памяти мало изначально, система может выдавать ошибку переполнения стекового буфера.</p>
30
<p>Помимо имплементации отмены, стеки используются для массы других задач:</p>
30
<p>Помимо имплементации отмены, стеки используются для массы других задач:</p>
31
<ul><li>Для хранения информации о вызовах функций и их локальных переменных.</li>
31
<ul><li>Для хранения информации о вызовах функций и их локальных переменных.</li>
32
<li>Для управления операциями в базах данных. Это может быть, например, откат транзакций или повтор операций.</li>
32
<li>Для управления операциями в базах данных. Это может быть, например, откат транзакций или повтор операций.</li>
33
<li>Для вычисления выражений, проверки скобок и выполнения других операций.</li>
33
<li>Для вычисления выражений, проверки скобок и выполнения других операций.</li>
34
<li>Для управления вызовами системных функций и передачей параметров между приложениями и ядром операционной системы.</li>
34
<li>Для управления вызовами системных функций и передачей параметров между приложениями и ядром операционной системы.</li>
35
</ul><p>На некоторых из этих кейсов мы подробно остановимся чуть позже, а пока - разберёмся с реализациями стека.</p>
35
</ul><p>На некоторых из этих кейсов мы подробно остановимся чуть позже, а пока - разберёмся с реализациями стека.</p>
36
<p>Так как стек - это чистая абстракция, для работы ему нужна реализация в виде конкретной структуры данных. Чаще всего стеки реализуют с помощью динамических массивов и связных списков. Разберём их подробнее.</p>
36
<p>Так как стек - это чистая абстракция, для работы ему нужна реализация в виде конкретной структуры данных. Чаще всего стеки реализуют с помощью динамических массивов и связных списков. Разберём их подробнее.</p>
37
<p>Динамическим называют массив, размер которого может увеличиваться или уменьшаться в процессе выполнения программы. Операции добавления (push) и удаления (pop) элементов производятся либо с конца, либо с начала массива.</p>
37
<p>Динамическим называют массив, размер которого может увеличиваться или уменьшаться в процессе выполнения программы. Операции добавления (push) и удаления (pop) элементов производятся либо с конца, либо с начала массива.</p>
38
<p>Вот как выглядит создание стека с помощью списка на языке Python.</p>
38
<p>Вот как выглядит создание стека с помощью списка на языке Python.</p>
39
class Stack: # Конструктор для инициализации стека def __init__(self): self.items = [] # Функция для проверки того, есть ли в стеке элементы def is_empty(self): return len(self.items) == 0 # Функция для добавления элемента в стек def push(self, item): self.items.append(item) # Функция для удаления верхнего элемента из стека def pop(self): if not self.is_empty(): return self.items.pop() else: print("Стек пуст. Мы не можем удалить из него элемент.") # Функция для чтения верхнего элемента стека def peek(self): if not self.is_empty(): return self.items[-1] else: print("Стек пуст. Мы не можем прочитать верхний элемент.") # Функция, возвращающая размер стека def size(self): return len(self.items) stack = Stack() print(stack.is_empty()) # True stack.push(1) stack.push(2) stack.push(3) print(stack.size()) # 3 print(stack.peek()) # 3 item = stack.pop() print(item) # 3 print(stack.size()) # 2 print(stack.is_empty()) # False<p>Здесь стек представляет собой связанный список, где каждый узел содержит какие-то данные и указатель на предыдущий узел. При добавлении новый элемент становится вершиной стека, а при удалении на вершине оказывается предыдущий элемент.</p>
39
class Stack: # Конструктор для инициализации стека def __init__(self): self.items = [] # Функция для проверки того, есть ли в стеке элементы def is_empty(self): return len(self.items) == 0 # Функция для добавления элемента в стек def push(self, item): self.items.append(item) # Функция для удаления верхнего элемента из стека def pop(self): if not self.is_empty(): return self.items.pop() else: print("Стек пуст. Мы не можем удалить из него элемент.") # Функция для чтения верхнего элемента стека def peek(self): if not self.is_empty(): return self.items[-1] else: print("Стек пуст. Мы не можем прочитать верхний элемент.") # Функция, возвращающая размер стека def size(self): return len(self.items) stack = Stack() print(stack.is_empty()) # True stack.push(1) stack.push(2) stack.push(3) print(stack.size()) # 3 print(stack.peek()) # 3 item = stack.pop() print(item) # 3 print(stack.size()) # 2 print(stack.is_empty()) # False<p>Здесь стек представляет собой связанный список, где каждый узел содержит какие-то данные и указатель на предыдущий узел. При добавлении новый элемент становится вершиной стека, а при удалении на вершине оказывается предыдущий элемент.</p>
40
<p>Пример реализации стека с использованием связанного списка на Python</p>
40
<p>Пример реализации стека с использованием связанного списка на Python</p>
41
class Node: # Конструктор для инициализации узла def __init__(self, data): self.data = data self.next = None class Stack: # Конструктор для инициализации стека def __init__(self): self.top = None # Функция для добавления нового узла def push(self, data): new_node = Node(data) new_node.next = self.top self.top = new_node # Функция для удаления верхнего элемента def pop(self): if not self.is_empty(): popped = self.top self.top = self.top.next popped.next = None return popped.data else: print("Стек пуст. Мы не можем удалить из него элемент.") # Функция для чтения верхнего элемента def peek(self): if not self.is_empty(): return self.top.data else: print("Стек пуст. Мы не можем прочитать верхний элемент.") # Функция для проверки, есть ли в стеке элементы def is_empty(self): return self.top is None # Функция, возвращающая размер стека def size(self): count = 0 current = self.top while current: count += 1 current = current.next return count stack = Stack() print(stack.is_empty()) # True stack.push(1) stack.push(2) stack.push(3) print(stack.size()) # 3 print(stack.peek()) # 3 item = stack.pop() print(item) # 3 print(stack.size()) # 2 print(stack.is_empty()) # False<p>Зависит от задачи. Если вам важна эффективность при доступе к элементам и при этом стек имеет фиксированный размер или меняется редко, лучше выбрать динамический массив. Если же вам нужно менять размер стека и вы не знаете заранее его максимальную величину, связанный список может быть удобнее.</p>
41
class Node: # Конструктор для инициализации узла def __init__(self, data): self.data = data self.next = None class Stack: # Конструктор для инициализации стека def __init__(self): self.top = None # Функция для добавления нового узла def push(self, data): new_node = Node(data) new_node.next = self.top self.top = new_node # Функция для удаления верхнего элемента def pop(self): if not self.is_empty(): popped = self.top self.top = self.top.next popped.next = None return popped.data else: print("Стек пуст. Мы не можем удалить из него элемент.") # Функция для чтения верхнего элемента def peek(self): if not self.is_empty(): return self.top.data else: print("Стек пуст. Мы не можем прочитать верхний элемент.") # Функция для проверки, есть ли в стеке элементы def is_empty(self): return self.top is None # Функция, возвращающая размер стека def size(self): count = 0 current = self.top while current: count += 1 current = current.next return count stack = Stack() print(stack.is_empty()) # True stack.push(1) stack.push(2) stack.push(3) print(stack.size()) # 3 print(stack.peek()) # 3 item = stack.pop() print(item) # 3 print(stack.size()) # 2 print(stack.is_empty()) # False<p>Зависит от задачи. Если вам важна эффективность при доступе к элементам и при этом стек имеет фиксированный размер или меняется редко, лучше выбрать динамический массив. Если же вам нужно менять размер стека и вы не знаете заранее его максимальную величину, связанный список может быть удобнее.</p>
42
<p>Стек вызовов - это структура данных, которая управляет вызовами функций во время выполнения программы. Звучит сложно, на деле - всё просто, следите за руками.</p>
42
<p>Стек вызовов - это структура данных, которая управляет вызовами функций во время выполнения программы. Звучит сложно, на деле - всё просто, следите за руками.</p>
43
-
<p>Когда компьютер выполняет программу и доходит до вызова какой-то функции, ему нужно ненадолго переключиться, чтобы эту самую функцию выполнить. Чтобы запомнить, где он остановился, компьютер сохраняет в памяти специальные закладки - так называемые точки перехода. Область па��яти, где хранятся точки перехода, как раз и называется стеком вызовов.</p>
43
+
<p>Когда компьютер выполняет программу и доходит до вызова какой-то функции, ему нужно ненадолго переключиться, чтобы эту самую функцию выполнить. Чтобы запомнить, где он остановился, компьютер сохраняет в памяти специальные закладки - так называемые точки перехода. Область памяти, где хранятся точки перехода, как раз и называется стеком вызовов.</p>
44
<p>В точке перехода хранится всё, чтобы компьютер быстро и безболезненно вернулся к выполнению основного кода: значения переменных, аргументы функций и адрес возврата - то место, куда компьютер должен перейти после окончания подпрограммы. Жизненная аналогия для точки перехода - это чекпойнт в игре: добежали, сохранились и можете пойти спокойно пить чай, пребывая в уверенности, что сможете начать с того же места.</p>
44
<p>В точке перехода хранится всё, чтобы компьютер быстро и безболезненно вернулся к выполнению основного кода: значения переменных, аргументы функций и адрес возврата - то место, куда компьютер должен перейти после окончания подпрограммы. Жизненная аналогия для точки перехода - это чекпойнт в игре: добежали, сохранились и можете пойти спокойно пить чай, пребывая в уверенности, что сможете начать с того же места.</p>
45
<p>Если внутри одной функции произойдёт вызов другой функции, история аналогичная: компьютер поставит на паузу выполнение первой, сохранит в стеке точку перехода, а затем перейдёт к выполнению второй. Этот принцип будет работать для любой степени вложенности функции, вплоть до рекурсии.</p>
45
<p>Если внутри одной функции произойдёт вызов другой функции, история аналогичная: компьютер поставит на паузу выполнение первой, сохранит в стеке точку перехода, а затем перейдёт к выполнению второй. Этот принцип будет работать для любой степени вложенности функции, вплоть до рекурсии.</p>
46
<p>Чтобы было понятнее, изобразим весь этот процесс на схеме. Представим, что у нас есть программа с тремя функциями: первая вызывает вторую, вторая - третью и так далее.</p>
46
<p>Чтобы было понятнее, изобразим весь этот процесс на схеме. Представим, что у нас есть программа с тремя функциями: первая вызывает вторую, вторая - третью и так далее.</p>
47
<p><strong>Шаг 1.</strong>Компьютер выполняет основную программу и доходит до вызова функции 1. Он прерывает выполнение основной программы, помещает адрес возврата в стек и переходит к выполнению функции 1.</p>
47
<p><strong>Шаг 1.</strong>Компьютер выполняет основную программу и доходит до вызова функции 1. Он прерывает выполнение основной программы, помещает адрес возврата в стек и переходит к выполнению функции 1.</p>
48
<p><strong>Шаг 2.</strong>Компьютер выполняет функцию 1 и доходит до вызова функции 2. Он прерывает выполнение функции 1, помещает её адрес возврата в стек и выполняет функцию 2.</p>
48
<p><strong>Шаг 2.</strong>Компьютер выполняет функцию 1 и доходит до вызова функции 2. Он прерывает выполнение функции 1, помещает её адрес возврата в стек и выполняет функцию 2.</p>
49
<p><strong>Шаг 3.</strong>Компьютер заканчивает выполнение функции 2, считывает и удаляет с вершины стека адрес возврата функции 1. Затем он переходит к функции 1 и продолжает её выполнение с инструкции, находящейся по адресу возврата.</p>
49
<p><strong>Шаг 3.</strong>Компьютер заканчивает выполнение функции 2, считывает и удаляет с вершины стека адрес возврата функции 1. Затем он переходит к функции 1 и продолжает её выполнение с инструкции, находящейся по адресу возврата.</p>
50
<p><strong>Шаг 4.</strong>Компьютер заканчивает выполнение функции 1, считывает и удаляет с вершины стека адрес возврата основной программы. Затем он переходит к основной программе и продолжает её выполнение с указанного адреса. Стек полностью очищается до следующего вызова.</p>
50
<p><strong>Шаг 4.</strong>Компьютер заканчивает выполнение функции 1, считывает и удаляет с вершины стека адрес возврата основной программы. Затем он переходит к основной программе и продолжает её выполнение с указанного адреса. Стек полностью очищается до следующего вызова.</p>
51
<p>Чтобы стек не разрастался в памяти, ему задаётся конкретный размер - либо системой, либо самим программистом. Но если вызовов в программе будет слишком много, стек может внезапно переполниться - в этом случае программа аварийно завершит работу и выдаст ошибку о переполнении стека.</p>
51
<p>Чтобы стек не разрастался в памяти, ему задаётся конкретный размер - либо системой, либо самим программистом. Но если вызовов в программе будет слишком много, стек может внезапно переполниться - в этом случае программа аварийно завершит работу и выдаст ошибку о переполнении стека.</p>
52
<p>Случиться это может по разным причинам:</p>
52
<p>Случиться это может по разным причинам:</p>
53
<ul><li><strong>Рекурсия большой глубины вложенности.</strong>При каждом витке рекурсии в стек добавляются новые элементы. Когда элементов бывает очень много, стек переполняется. В различных языках может быть разная глубина рекурсии, например в Python она ограничена примерно 3000 вызовов.</li>
53
<ul><li><strong>Рекурсия большой глубины вложенности.</strong>При каждом витке рекурсии в стек добавляются новые элементы. Когда элементов бывает очень много, стек переполняется. В различных языках может быть разная глубина рекурсии, например в Python она ограничена примерно 3000 вызовов.</li>
54
<li><strong>Бесконечные циклы</strong>, которые тоже приводят к накоплению данных в стеке. Вот пример бесконечного цикла на Python, который приводит к переполнению стека вызовов:</li>
54
<li><strong>Бесконечные циклы</strong>, которые тоже приводят к накоплению данных в стеке. Вот пример бесконечного цикла на Python, который приводит к переполнению стека вызовов:</li>
55
</ul>def infinite_loop(): while True: pass # Вызываем бесконечный цикл infinite_loop()<ul><li><strong>Огромные массивы</strong>или другие структуры в программах.</li>
55
</ul>def infinite_loop(): while True: pass # Вызываем бесконечный цикл infinite_loop()<ul><li><strong>Огромные массивы</strong>или другие структуры в программах.</li>
56
</ul><p>Когда программа пытается разместить на стеке больше данных, чем он может вместить, система записывает эти данные памяти за пределами выделенного участка. Это может привести к непредсказуемому поведению программы или её аварийному завершению с потерей данных. А ещё переполнение стека могут использовать хакеры, чтобы внедрить в систему вредоносный код.</p>
56
</ul><p>Когда программа пытается разместить на стеке больше данных, чем он может вместить, система записывает эти данные памяти за пределами выделенного участка. Это может привести к непредсказуемому поведению программы или её аварийному завершению с потерей данных. А ещё переполнение стека могут использовать хакеры, чтобы внедрить в систему вредоносный код.</p>
57
<p>Стеки данных работают подобно стекам вызовов - в них можно читать и удалять только последний элемент, остальные недоступны. Этот вид стеков часто используют для работы с разветвлёнными типами данных: деревьями, графами, XML-документами,<a>JSON-объектами</a>и другими.</p>
57
<p>Стеки данных работают подобно стекам вызовов - в них можно читать и удалять только последний элемент, остальные недоступны. Этот вид стеков часто используют для работы с разветвлёнными типами данных: деревьями, графами, XML-документами,<a>JSON-объектами</a>и другими.</p>
58
<p>Например, стеки данных хорошо подходят для обхода деревьев в глубину - когда мы посещаем все узлы дерева, чтобы сделать с ними что-то, скажем, вывести все значения. В этом случае мы начинаем с корня и идём так глубоко, как только можем, а потом возвращаемся, чтобы исследовать другую ветвь. И стеки подходят для этого как нельзя лучше:</p>
58
<p>Например, стеки данных хорошо подходят для обхода деревьев в глубину - когда мы посещаем все узлы дерева, чтобы сделать с ними что-то, скажем, вывести все значения. В этом случае мы начинаем с корня и идём так глубоко, как только можем, а потом возвращаемся, чтобы исследовать другую ветвь. И стеки подходят для этого как нельзя лучше:</p>
59
<ul><li>Когда мы посещаем узел, мы добавляем его в стек.</li>
59
<ul><li>Когда мы посещаем узел, мы добавляем его в стек.</li>
60
<li>Когда мы хотим вернуться к предыдущему узлу, мы достаём его из стека.</li>
60
<li>Когда мы хотим вернуться к предыдущему узлу, мы достаём его из стека.</li>
61
</ul><p>Другой кейс - вычисление выражений в обратной польской нотации (ОПН). Это такие выражения, в которых сначала пишутся числа, а потом знаки операций. Например, 2+ 3∗4 будет записано как 2 3 4 ∗ +. Идея в том, чтобы создать алгоритм, который будет сначала "откладывать" числа в стек, а как доберётся до знаков операций - достанет их оттуда и проведёт вычисления.</p>
61
</ul><p>Другой кейс - вычисление выражений в обратной польской нотации (ОПН). Это такие выражения, в которых сначала пишутся числа, а потом знаки операций. Например, 2+ 3∗4 будет записано как 2 3 4 ∗ +. Идея в том, чтобы создать алгоритм, который будет сначала "откладывать" числа в стек, а как доберётся до знаков операций - достанет их оттуда и проведёт вычисления.</p>
62
<p>Для самых стойких - вот как это реализуется с помощью Python:</p>
62
<p>Для самых стойких - вот как это реализуется с помощью Python:</p>
63
import operator OPERATORS = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv} # Создаём словарь, содержащий арифметические операции и их обозначения def polsk(strok): stack = [] # Создаём стек lst = strok.split() for i in lst: # Перебираем элементы списка if i.isdigit(): stack.append(i) # Если элемент - число, то помещаем его в стек else: a, b = stack.pop(), stack.pop() # Считываем в переменные a и b два последних элемента стека и удаляем их из стека stack.append(OPERATORS[i](int(a), int(b))) # Выполняем над ними операцию и результат помещаем в стек return stack.pop() print(polsk('11 26 33 + +')) # 70<p>Давайте подытожим всё, что мы узнали из этой статьи:</p>
63
import operator OPERATORS = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv} # Создаём словарь, содержащий арифметические операции и их обозначения def polsk(strok): stack = [] # Создаём стек lst = strok.split() for i in lst: # Перебираем элементы списка if i.isdigit(): stack.append(i) # Если элемент - число, то помещаем его в стек else: a, b = stack.pop(), stack.pop() # Считываем в переменные a и b два последних элемента стека и удаляем их из стека stack.append(OPERATORS[i](int(a), int(b))) # Выполняем над ними операцию и результат помещаем в стек return stack.pop() print(polsk('11 26 33 + +')) # 70<p>Давайте подытожим всё, что мы узнали из этой статьи:</p>
64
<ul><li>Стек - это способ хранения данных, работающий по принципу "последним пришёл, первым вышел". Он применяется в разных областях программирования и алгоритмов.</li>
64
<ul><li>Стек - это способ хранения данных, работающий по принципу "последним пришёл, первым вышел". Он применяется в разных областях программирования и алгоритмов.</li>
65
<li>Две наиболее распространённые реализации стека: с использованием динамического массива и с помощью связанного списка.</li>
65
<li>Две наиболее распространённые реализации стека: с использованием динамического массива и с помощью связанного списка.</li>
66
<li>Есть множество видов стеков, которые применяются в разных областях. Основные из них - стек вызовов и стек данных.</li>
66
<li>Есть множество видов стеков, которые применяются в разных областях. Основные из них - стек вызовов и стек данных.</li>
67
<li>Стек вызовов - это структура данных, которая управляет вызовами функций во время выполнения программы.</li>
67
<li>Стек вызовов - это структура данных, которая управляет вызовами функций во время выполнения программы.</li>
68
<li>Если программа пытается разместить на стеке больше данных, чем он может вместить, происходит переполнение стека. Это приводит к аварийному завершению работы программы и другим непредсказуемым последствиям.</li>
68
<li>Если программа пытается разместить на стеке больше данных, чем он может вместить, происходит переполнение стека. Это приводит к аварийному завершению работы программы и другим непредсказуемым последствиям.</li>
69
<li>Стеки данных используются при вычислении выражений, обратной польской нотации, для обхода деревьев, графов и других целей.</li>
69
<li>Стеки данных используются при вычислении выражений, обратной польской нотации, для обхода деревьев, графов и других целей.</li>
70
</ul><a><b>Бесплатный курс по Python ➞</b>Мини-курс для новичков и для опытных кодеров. 4 крутых проекта в портфолио, живое общение со спикером. Кликните и узнайте, чему можно научиться на курсе. Смотреть программу</a>
70
</ul><a><b>Бесплатный курс по Python ➞</b>Мини-курс для новичков и для опытных кодеров. 4 крутых проекта в портфолио, живое общение со спикером. Кликните и узнайте, чему можно научиться на курсе. Смотреть программу</a>