Стек — это абстрактная структура данных, которая следует логике LIFO (последним пришел — первым вышел). Стек — это структура реального времени, которую мы используем в сценарии нашей повседневной жизни.
например :колода карт, книги помещены в коробку.
Стек похож на контейнер с полками для хранения данных в каждом сегменте. К стеку применяются две операции.
Push: это похоже на вставку элемента данных в стек. Данные записываются снизу вверх по стеку.
Извлечение. Удаление элемента из стека называется операцией извлечения из стека.
Давайте посмотрим пример:
Важным термином, используемым в стеке, является «верхний», который относится к самому верхнему элементу стека.
Стек имеет определенный размер. Помещая элемент в стек, пользователь должен проверить, полон ли стек. Но перед удалением или извлечением элемента пользователь должен проверить состояние стека пустым.
Теперь давайте посмотрим на алгоритмы push и pop.
Алгоритм отправки:
- Проверьте состояние стека.
- Если стек полон, вернуть стек полон.
- В противном случае вставьте элемент в стек.
- Увеличьте позицию вершины на 1.
- вернуть успех.
Алгоритм поп-музыки:
- Проверить наличие пустого стека
- Если стек пуст, верните стек пустым.
- В противном случае доступ к данным в верхней части стека.
- Уменьшить позицию вершины на 1.
- Вернуть успех.
Применения стека:
- Оценка выражения
- Преобразование выражений
- Вызов функции
- Возвращение
- Разбор синтаксиса
Из приведенных выше приложений давайте углубимся в одно из приложений, то есть преобразование выражений.
Прежде чем узнать преобразование выражений, что такое выражение?
Говорят, что выражение представляет собой комбинацию операторов и операндов. Операторы — это арифметические символы. Арифметические операции выполняются над арифметическими операндами.
e. g: a +b
где a, b — операнды, а + — оператор.
Существует 3 различных типа выражений:
- Infix: это удобочитаемый тип, в котором оператор находится между операндами.
e. g : a +b
2. Постфикс:это машиночитаемый тип, в котором операторы размещаются после операндов.
e. g: ab+
3. Префикс: Здесь это обратный тип постфикса, в котором операнды идут первыми, а операторы.
e. g: +ab
Преобразование выражения из одного типа в другой называется преобразованием выражения.
В следующем рассказе мы обсудим преобразование выражения из инфиксного в постфиксное.
Спасибо.