Стеки относятся ко многим вещам!
Это что-то гораздо более сложное, чем просто понимание переполнения стека как выражения (или даже того, почему оно так называется - если вы не знаете, что посмотрите ЗДЕСЬ).
Эта конкретная статья, однако, посвящена рассмотрению абстрактной концепции стеков и того, как они используются в компьютерном программировании.
Не волнуйтесь, в большинстве статей стопки пишутся как стопки книг. Но мы можем пойти дальше, и это действительно может быть весело. Мы начнем с быстрого обзора массивов, а затем проведем вас по стекам.
Итак, приступим прямо к делу!
Сложность: Начинающий | Легко | Нормальный | Испытывающий
Предпосылки:
- Никто. Если вы знакомы с массивами, вы можете пропустить первый раздел (полное руководство по массивам находится ЗДЕСЬ)
Терминология
Массив: упорядоченная серия объектов одного типа.
Тип данных: представление набора данных, которые могут быть обработаны, например Integer или String.
Символы: символ, обычно связанный с буквой алфавита.
Коллекция: последовательность элементов, которые можно перемещать (сколько угодно раз) и к которым можно получить доступ с помощью индексированного нижнего индекса.
Целое число: число без дробной части, то есть без цифр после десятичной точки.
LIFO: последний пришел - первым ушел
Стек: структура данных, используемая для хранения объектов.
Подстрочный индекс: ярлык для доступа к элементам массива (или любой коллекции или списка, в зависимости от языка).
Терминология операций над стеком
isEmpty: возвращает true, если стек пуст, false, если нет.
Peek: возвращает верхний элемент из стека
Pop: возвращает и удаляет верхний элемент из стека.
Push: вытягивает элемент из вершины стека.
Обзор массивов
Мы можем думать о массиве как о коллекции элементов с определенным порядком. Таким образом, мы можем поместить Characters
«h», «e», «l», «l» и «o» в Array
.
Обычно они нумеруются с нуля, как в следующем примере.
Мы назовем это Array
обр.
Это здорово, и мы можем получить доступ к отдельным элементам через Subscripting
. Это означает, что для доступа к первому элементу мы используем следующие
arr [0]
что, конечно же, показывает «h».
чтобы получить доступ к последнему элементу, который мы используем
arr [4]
что, конечно, показывает "о"
Этот тип Collection
означает, что у вас есть массив, но для финансирования любого конкретного элемента вам потребуется искать его с помощью некоторого алгоритма, такого как линейный поиск. (руководство по линейному поиску находится ЗДЕСЬ).
Что такое стек
Зачем кому-то когда-либо понадобилось использовать Stack
в компьютерном программировании? Зачем использовать Stack
в компьютерных приложениях?
Ну Arrays
, без сомнения, фантастичны. Основная идея состоит в том, что вы можете использовать Subscripting
для доступа к любому элементу (это известно как произвольный доступ). В некоторых ситуациях вам нужен более ограниченный доступ к своим данным.
Использование в реальном мире
Пример использования Stack
- в мобильных приложениях. В этом примере показана iOS, но идеи одинаково применимы к Android и iPadOS.
Изображение, которое вы видите на экране, является контроллером представления, и вы можете отображать только ОДИН из них за раз (поскольку есть один экран).
А теперь представьте, что вы проходите через набор экранов своего телефона. Когда приложение загружается, вы видите контроллер представления Introduction. Затем вам будет представлено меню в форме Контроллер представления меню, щелкните значок и перейдите к Контроллер представления подробностей. . Еще раз вы нажимаете на значок, и перед вами появляется Мой новый контроллер представления.
Теперь помните, что мы можем видеть только один контроллер представления одновременно. Поскольку мы хотим вернуться к представлениям, которые вы хотите сохранить, как мы попали в Мой новый контроллер представления. Один из способов сделать это - использовать Stack
Каждый раз, когда мы помещаем новый контроллер представления в существующие контроллеры представления, мы говорим, что push
элемент на Stack
.
Когда мы нажимаем кнопку "Назад" для перехода к предыдущему контроллеру представления, мы pop
элемент Stack
, то есть удаляем его, чтобы увидеть представление контроллер ниже того, который мы popped
сняли со стека.
Stacks
может содержать различные Data types
- то есть мы не ограничены контроллерами представления, и мы увидим силу этого, поскольку сейчас продемонстрируем общий Stacks
.
Общий стек
Когда мы добавляем elements
к stack
, мы push
этот конкретный elements
на stacks
, когда мы удаляем элемент, мы pop
этот элемент из стека.
Вставка и вставка элементов в стек
Начиная с пустого stack
. Эта конкретная стопка может содержать четыре elements
Затем мы добавляем elements
6, 9 и 0 (в указанном порядке). Это дает нам следующее stack
:
Операции, которые мы будем выполнять, будут
Нажать 6
Нажать 9
Нажмите 0
Если мы хотим удалить 0 из stack
, мы должны pop
самый верхний element
из stack
.
Поп
который десять предоставляет нам следующее, а также возвращает 0:
Шаг за шагом
Начиная с пустого stack
, мы можем протолкнуть серию elements
на stack
, а затем pop
element
из стека. Это показано в следующем примере:
Немного теории: операции
Мы рассмотрели несколько основных операций stack
Поп
Просто удалите верхний элемент из stack
, а затем верните этот element
Толкать
Push
элемент на stack
Подглядывать
Вы можете выполнять операцию, похожую на POP
, но не удалять соответствующий элемент (самый верхний элемент в стеке). Это называется PEEK
.
пустой
У нас может быть метод, который определяет, является ли stack
пустым или нет. Если он пуст, isEmpty вернет true. Если в stack
есть элементы, isEmpty вернет false.
Немного теории: ЛИФО
Stacks
, как говорят, реализует LIFO
data type
. Другими словами, последний element
, который мы нажимаем на stack
, является первым, который мы выскакиваем из верха stack
.
Следует отметить, что stack
не просто хранят Integer
или Character
, как показано выше, они могут (по крайней мере теоретически) содержать любой тип данных на вашем языке.
Заключение:
Stacks
действительно важны data type
в информатике, и о них стоит знать, когда вы пишете код. В этой статье приводится реальный пример, а также демонстрация stack
.
Я надеюсь, что это было полезно для вас, и удачного программирования!
Расширьте свои знания
- Если вы действительно хотите разбираться в массивах с нулевым индексом, вы можете использовать руководство ЗДЕСЬ
- Если вас интересует линейный поиск, вы можете просмотреть ЗДЕСЬ
- Вы можете увидеть причины переполнения стека ЗДЕСЬ
Контактное лицо в Twitter:
Любые вопросы? Вы можете связаться со мной здесь