Стеки — это упорядоченная структура данных, в которой порядок — первый пришел последним. Вы можете в основном представить это как штабелирование тарелок. Первая тарелка, которую вы ставите, находится внизу, но когда вы получаете тарелку, вы берете ее сверху.
Поскольку вы всегда вставляете и извлекаете сверху, время выполнения для обоих вариантов составляет O (1). Метод pop удаляет верхнее значение из стека, которое также будет O (1). Обычно вы сможете увидеть только верхнее значение, а чтобы увидеть остальное, вам придется вытолкнуть верх. Необходимое пространство будет O (n), что является размером всего, что вы поместите в стек.
Стеки — это рекурсивная структура данных, в которой вы сможете видеть только начало или вершину стека. Всякий раз, когда вы выталкиваете стек, новая голова будет данными непосредственно под или рядом с предыдущей вершиной. Стеки могут быть реализованы по-разному, включая массивы и списки.
Некоторые приложения с использованием стеков включают в себя:
- Возвращение назад — как решение лабиринта. Вталкивая в стек каждый сделанный шаг, и когда вы достигаете тупика, вы будете выталкивать его, пока не сможете пойти в другом направлении.
- Вычисление выражений — решение математических выражений в соответствии с правилом порядка операций.
- Анализ синтаксиса. Многие компиляторы используют стеки для анализа выражений и программных блоков перед преобразованием в низкоуровневый код.
- Parenthesis Checking — Проверка, соответствует ли открывающая скобка закрывающей скобке и допустима ли она.
- Вызов функции — отслеживает информацию об активных функциях и подпрограммах.
