Структура данных стека в C++

Структура данных стекаСтек — это фундаментальная структура данных, которая используется для хранения элементов линейным способом.

Стек следует LIFO (последний вход, первый выход) порядок или подход, в котором выполняются операции. Это означает, что элемент, который был добавлен последним в стек, будет первым элементом, который будет удален из стека.

Ниже приведена схема стека:

Схема стека наглядно

Как показано выше, есть куча элементов, уложенных друг на друга. Если мы хотим добавить к ним еще один элемент, то мы добавляем его в верхнюю часть стека, как показано на рисунке выше (слева). Эта операция добавления элемента в стек называется “Push”.

В правой части мы показали противоположную операцию, то есть мы удаляем элемент из стека. Это также делается с того же конца, то есть с вершины стека. Эта операция называется “Pop”.

Как показано на рисунке выше, мы видим, что push и pop выполняются с одного конца. Это заставляет стек следовать порядку LIFO. Позиция или конец, из которого элементы вставляются или извлекаются в / из стека, называется “Вершиной стека”.

Изначально, когда в стеке нет элементов, верх стека устанавливается равным -1. Когда мы добавляем элемент в стек, верхняя часть стека увеличивается на 1, указывая, что элемент добавлен. Верхняя часть стека уменьшается на 1, когда элемент извлекается из стека.

Далее мы покажем некоторые из основных операций структуры данных стека, которые нам потребуются при реализации стека.

Основные операции

Ниже приведены основные операции, которые поддерживаются стеком.

  • push – добавляет или помещает элемент в стек.
  • pop – удаляет или выталкивает элемент из стека.
  • peek – возвращает верхний элемент стека, но не удаляет его.
  • isFull – проверяет, заполнен ли стек.
  • isEmpty – проверяет, пуст ли стек.

Демонстрация

Последовательность операций

На приведенном выше рисунке показана последовательность операций, которые выполняются в стеке. Изначально стек пуст. Для пустого стека верх стека устанавливается равным -1.

Далее мы помещаем элемент 10 в стек. Видно, что вершина стека теперь указывает на элемент 10.

Читать также:  Структура данных циклического связного списка в C++

Далее мы выполняем еще одну операцию push с элементом 20, в результате чего вершина стека теперь указывает на 20. Это состояние показывает третий рисунок.

Теперь на последнем рисунке мы выполняем операцию pop (). В результате операции pop элемент, указанный в верхней части стека, удаляется из стека. Следовательно, на рисунке мы видим, что элемент 20 удален из стека. Таким образом, вершина стека теперь указывает на 10.

Реализация

1) Использование массивов

Ниже приведена реализация стека на C ++ с использованием массивов:

Вывод данных:

The Stack Push
2
4
6
The Stack Pop:
6
4
2

В выводных данных мы можем видеть, что элементы помещаются в стек в одном порядке и извлекаются из стека в обратном порядке. Это демонстрирует подход LIFO (последний вход, первый выход) для стека.

Для приведенной выше реализации стека в виде массива мы можем сделать вывод, что это очень легко реализовать, поскольку указатели не задействованы. Но в то же время размер стека статичен, и стек не может расти или уменьшаться динамически.

Далее мы реализуем стек с использованием массивов на языке программирования Java:

Вывод данных:

Stack Push:
1
3
5
Stack Pop:
5
3
1

Логика реализации такая же, как и в реализации на C ++. На выходе показана методика LIFO по вводу и извлечению элементов в / из стека.

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

2) Использование связного списка

Далее мы реализуем операции стека с использованием связного списка как в C++, так и в Java. Сначала мы продемонстрируем реализацию на C++:

Вывод данных:

Stack Push:
100
200
300
Top element is 300
Stack Pop:
300
200
100
Top element is -1

Далее мы представим реализацию стека на Java с использованием связного списка:

Вывод данных:

Stack Push:
100
200
300
Top element is 300
Stack Pop:
300
200
100
Stack is empty
Top element is -2147483648

Читать также:  Безопасность реализации на языке Java

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

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

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

Применения стека

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

Ниже мы кратко опишем некоторые применения стека:

1) Инфикс в постфиксные выражения

Любое общее арифметическое выражение имеет вид operand1 OP operand2 .

Основываясь на позиции оператора OP, мы имеем следующие типы выражений:

  • Инфикс – общая форма инфиксного выражения — “operand1 OP operand2”. Это базовая форма выражения, которую мы постоянно используем в математике.
  • Префикс – когда оператор помещается перед операндами, это префиксное выражение. Общая форма инфиксного выражения — “OP operand1 operand2”.
  • Постфикс – в постфиксных выражениях сначала записываются операнды, за которыми следует оператор. Она имеет вид “operand1 operand2 OP”.

Рассмотрим выражение “a + b * c”. Компилятор сканирует выражение либо слева направо, либо справа налево. Заботясь о приоритете операторов и ассоциативности, он сначала сканирует выражение для вычисления выражения b * c. Затем снова придется сканировать выражение, чтобы добавить результат b * c к a.

По мере того, как выражения становятся все более и более сложными, такой подход повторного сканирования выражения становится неэффективным.

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

Читать также:  Ссылки в С++

2) Синтаксический анализ / оценка выражений

Используя стек, мы также можем выполнять фактическую оценку выражения. В этом случае, выражение просматривается слева направо, а операнды помещаются в стек.

Всякий раз, когда встречается оператор, извлекаются операнды и выполняется операция. Результат операции снова помещается в стек. Это способ, при котором выражение вычисляется с помощью стека, и конечным результатом выражения обычно является текущая вершина стека.

3) Обход деревьев

Древовидная структура данных может быть пройдена для посещения каждого узла многими способами и в зависимости от того, когда посещается корневой узел, который у нас есть.

  • Обход по порядку
  • Обход предварительный
  • Пост обход

Для эффективного обхода деревьев мы используем структуру данных стека для перемещения промежуточных узлов в стеке, чтобы поддерживать порядок обхода.

4) Алгоритмы сортировки

Алгоритмы сортировки, такие как quicksort (быстрая сортировка), могут быть сделаны более эффективными с использованием структур данных стека.

5) Ханойские башни

Это классическая задача, включающая n дисков и три башни, и проблема заключается в перемещении дисков из одной башни в другую с использованием третьей башни в качестве промежуточной.

Эта проблема может быть эффективно решена с помощью стека, когда мы помещаем диски для перемещения в стек, поскольку стек в основном действует как башня, используемая для перемещения дисков.

Итог

Стек — это самая простая структура данных, которую проще реализовать в виде программы. В нем использовался подход LIFO (последний вход, первый выход), который означает, что элемент, введенный последним, удаляется первым. Так происходит потому, что стек использует только один конец для добавления (push) и удаления (pop) элементов.

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

В нашей следующей статье мы подробно изучим структуру данных очереди в C++.

С Уважением, МониторБанк

Добавить комментарий