28 февраля 2020 г., Мо Чехаде
Что такое структура данных стека?
Думайте о стеке как о реальной физической куче элементов, с точки зрения программирования вы могли бы сказать, что это хранилище объектов, которые выталкиваются или выталкиваются. Чтобы добавлять и удалять элементы, такие операции выполняются в верхней части стека в определенном порядке. мы можем использовать функцию Push() для добавления элементов и функцию pop() для удаления элементов. Это поведение работает по принципу «последним поступил — первым вышел» (LIFO), когда последний элемент, который был добавлен, является первым элементом, подлежащим удалению.
Реализации стека
Стек — это абстрактная структура данных. Он реализован с использованием массива и поддерживается несколькими языками программирования, такими как C, C++, Java, C#, Python и т. д.…
В стеке можно использовать следующие операции:
Push() используется для добавления элементов поверх стека. Полезной аналогией было бы подумать о стопке тарелок, сможете ли вы взять тарелку из середины? Не хорошая идея! Вы хотели бы добавить тарелку из верхней части стопки. для этого нам нужно проверить, есть ли место для добавления элементов. А если бы он был полный? элементу придется ждать в очереди.
Как вы можете видеть в приведенном выше фрагменте кода, мы создали класс стека, который содержит конструктор, затем мы установили элементы, равные массиву, для реализации стека.
Конструктор подобен чертежу. Одна из моих любимых аналогий — «чертеж» дома. Конструктор подобен чертежу дома. Вы можете использовать один и тот же план, чтобы построить много домов. То же самое в классах и конструкторах, где вы можете вызвать этот конструктор в любое время и использовать в нем те же инструкции.
Имея конструктор с пустым массивом, мы хотим использовать функцию push для помещения элементов в стек, мы передаем функции push элемент, который хотим поместить в качестве аргумента, и помещаем в стек элементов.
pop() используется для удаления элементов из верхней части стопки, как и в случае с тарелками, о которых мы упоминали выше, вы не можете удалять тарелки из середины или нижней части стопки, вы должны удалять их сверху . Прежде чем выталкивать элемент из стека, вы должны проверить, пуст ли стек или еще есть элементы, которые нужно удалить.
Стек приложений
Существует ряд приложений, использующих структуру данных стека. Наиболее распространенное использование этой структуры данных:
1- Обратные струны
2- Возврат
3- Преобразование выражения (преобразование инфикса в постфикс, преобразование постфикса в префикс
Обратить строки: одно из приложений стека, в котором вы переворачиваете строку. Вы помещаете слово в стек буква за буквой, а затем удаляете или извлекаете буквы из стека.
Шаг 1: Создайте стек
Шаг 2: Нажмите все символы один за другим
Шаг 3: вытащите все символы один за другим и поместите их в пустой массив
Шаг 4: Наконец, преобразуйте их в строку
Отслеживание с возвратом. Если вы хотите получить доступ к самому последнему элементу в стеке элементов данных, вам нужна алгоритмическая техника для решения проблем, которая использует рекурсии, называемую отслеживанием с возвратом. Он реализуется путем постепенного создания решений, а затем начинается удаление решений, которые не удовлетворяют ограничениям проблемы в любой момент времени.
Отличное видео, объясняющее алгоритм возврата:
