Когда использовать структуру данных стека

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

Вышеупомянутая функция делает его структурой данных LIFO (Last-In-First-Out). Здесь первым осуществляется доступ к элементу, который вставлен последним. В терминологии стека операция вставки называется PUSH, а операция удаления - POP. Считается, что стек находится в состоянии переполнения, когда он полностью заполнен, и считается, что он находится в состоянии недостаточного заполнения, если он полностью пуст.

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

Когда мы обсуждаем операции Stack, они включают в себя две основные операции.

 push() — Inserting an element to the stack
 pop() — Removing an element from the stack

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

peek() — get the top element of the stack, without removing the element.
isFull() — check if the stack is full
isEmpty() — check if the stack is empty

Алгоритм

1. A pointer called TOP is used to keep track of the top element in the stack.
2. When initializing, The value of TOP is -1. So that we can check if the stack is empty by comparing TOP == -1.
3. When pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP.
4. On popping an element, we return the element pointed to by TOP and reduce the value of TOP.
5. Before pushing, we check if the stack is already full.
6. Before popping, we check if the stack is already empty

Реализация стека с использованием Java

Попробуйте реализовать Stack самостоятельно и проверьте свою с помощью приведенного ниже кода.

Ошибки стека

Две вещи могут пойти не так со стеками:

1. Незаполнение

Когда была сделана попытка вытолкнуть пустую стопку. Нет смысла удалять что-то из пустой коллекции. Недополнение стека - распространенная ошибка - для защиты от нее следует использовать вызовы isEmpty.

2. Переполнение

Когда была сделана попытка поместить элемент в полный стек. Некоторые реализации стеков определяют конкретный конечный размер. Переполнение стека, вероятно, чаще всего происходит из-за «зашедшей слишком далеко» рекурсии.

Сложность выполнения стековых операций

Для всех стандартных операций со стеком (push, pop, isEmpty, size) сложность времени выполнения в наихудшем случае может быть O (1). Потому что эти операции занимают постоянное время. Очевидно, что операции size и isEmpty с постоянным временем. push и pop также имеют значение O (1), потому что они работают только с одним концом структуры данных - вершиной стека.

Приложения Stack для решения проблем

Сбалансированные круглые скобки

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

Отслеживание с возвратом

· Стеки особенно полезны, когда вычисления должны выполняться в обратном порядке. Это часто случается в приложениях искусственного интеллекта: играх, логических программах, средствах доказательства теорем и т. Д.

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

в стек, а затем идите в том направлении, в котором вы не нажимали. Когда вы зайдете в тупик, вернитесь к последнему варианту (т. Е. Вытащите стек) и продолжайте оттуда.

Записи активации

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

Перевернуть слово

· Сложите все буквы в стопку и вытащите их. Из-за порядка стека LIFO вы получите буквы в обратном порядке.

В компиляторах

· Компиляторы используют стек для вычисления значения выражений типа 2 + 4/5 * (7–9) путем преобразования выражения в префиксную или постфиксную форму.

В браузерах

· Кнопка «Назад» в браузере сохраняет все URL-адреса, которые вы посетили ранее, в стеке. Каждый раз, когда вы посещаете новую страницу, она добавляется в верхнюю часть стека. Когда вы нажимаете кнопку «Назад», текущий URL-адрес удаляется из стека, и осуществляется доступ к предыдущему URL-адресу.