Простая для понимания структура данных стека и ее реализация.
Стек — это простая структура данных, используемая для хранения данных. В стеке важен порядок поступления данных. Стопка тарелок в столовой — хороший пример стопки. Пластины добавляются в стопку по мере их очистки и кладутся сверху. Когда требуется тарелка, ее берут с вершины стопки. Первая тарелка, помещенная в стопку, используется последней.
Определение. Стек — это упорядоченный список, в котором вставка и удаление выполняются на одном конце, который называется вершиной. Последний вставленный элемент удаляется первым. Следовательно, он называется списком последним пришел первым вышел (LIFO) или первым пришел последним (FILO).
Двум изменениям, которые можно внести в стек, даются специальные имена. Когда элемент вставляется в стек, концепция называется push, а когда элемент удаляется из стека, концепция называется pop. Попытка извлечь пустой стек называется переполнением, а попытка поместить элемент в полный стек называется переполнением. Как правило, мы относимся к ним как к исключениям.
Как используются стеки:
Рассмотрим рабочий день в офисе. Предположим, разработчик работает над долгосрочным проектом. Затем менеджер дает разработчику новую задачу, которая является более важной. Разработчик откладывает долгосрочный проект и начинает работу над новой задачей. Звонит телефон, и это высший приоритет, так как на него нужно ответить немедленно. Разработчик помещает текущую задачу в отложенный лоток и отвечает на телефонные звонки.
Когда вызов завершен, задача, от которой отказались ответить на звонок, извлекается из области ожидания, и работа продолжается. Чтобы принять другой вызов, его, возможно, придется обрабатывать таким же образом, но в конечном итоге новая задача будет завершена, и разработчик может взять долгосрочный проект из области ожидания и продолжить работу.
Прямые приложения:-
• Балансировка символов
• Преобразование инфикса в постфикс
• Вычисление постфиксного выражения
• Реализация вызовов функций (включая рекурсию )
• История посещенных страниц в веб-браузере [кнопки «Назад»]
• Отмена последовательности в текстовом редакторе
• Сопоставление тегов в HTML и XML
Косвенные приложения: -
• Вспомогательная структура данных для других алгоритмов (Пример: алгоритмы обхода дерева)
• Компонент других структур данных (Пример: Моделирование очередей)
Реализация стека
Существует много способов реализации стека, ниже приведены наиболее часто используемые методы.
• Простая реализация на основе массива
• Реализация на основе динамического массива
• Реализация связанных списков
В этой реализации стекового ADT используется массив. В массив мы добавляем элементы слева направо и используем переменную для отслеживания индекса верхнего элемента. Массив, хранящий элементы стека, может переполниться. Затем операция push вызовет исключение полного стека. Точно так же, если мы попытаемся удалить элемент из пустого стека, это вызовет исключение пустого стека.
В этой статье мы видим реализацию стека с использованием простого массива. Итак, для реализации стека мы используем концепцию класса, вы также можете объявить структуру. Сначала создайте класс с именем «Stack». Мы знаем, что для обхода в стеке есть одна переменная-член, которая является «верхней». Объявите член данных стека, который является верхним.
После написания вышеприведенного кода мы должны добавить к этому коду дополнительную функциональность, которая похожа на объявление размера массива, почему именно массив? потому что мы реализуем стек, используя массив. В массиве мы вставляем и удаляем элемент, а также в стеке есть такая же операция, но мы называем ее push для вставки элемента и pop для удаления элемента.
Теперь мы обсудим операцию push. Операция push означает вставку элемента в стек. Перед вставкой элемента мы должны проверить, заполнен ли стек или нет, и если он заполнен, то нет возможности вставить элемент, поэтому он может вызвать исключение. Для проверки переполнения стека мы используем функцию isFull(), которая возвращает истинное значение, если стек полон, в противном случае возвращает false. Прежде чем вставить элемент на вершину стека, он сначала увеличивает вершину стека, потому что мы инициализируем верхние значения как «-1», вы также можете объявить значение вершины как «0». Давайте посмотрим фрагмент кода операции push:
Приведенный выше код показывает, что функция push() принимает один аргумент от пользователя, этот аргумент является значением, которое вы хотите добавить в стек. Операция Pop() не принимает никаких аргументов, потому что это операция удаления, она удаляет элемент с вершины стека после выполнения операции удаления, она уменьшает значение вершины. Перед выполнением операции удаления мы должны проверить, пуст стек или нет, если он пуст, то это состояние потери значимости, и в этой ситуации удаляем ли мы элемент с вершины стека. Давайте посмотрим фрагмент кода операции pop:
Теперь мы видим функцию peek. Peek просто возвращает верхнюю часть элемента, поэтому мы можем увидеть значение, которое было вставлено в последний раз. Функция размера, возвращающая текущий размер стека, означает, сколько элементов вы вставили. Пришло время увидеть весь код:
Пространственная сложность (для n операций push):- O(n)
Временная сложность Push():- O(1)
>Временная сложность Pop():-O(1)
Временная сложность Size():- O(1)
Временная сложность peek():- O(1)
Мы определяем один макрос, который является емкостью, которая представляет емкость стека.
Ограничения:-
Сначала необходимо определить максимальный размер стека, и его нельзя изменить. Попытка поместить новый элемент в полный стек вызывает исключение, зависящее от реализации. Также в операции pop мы видим, что на самом деле мы не удаляем элемент, а просто уменьшаем верхнюю часть.
