Стеки относятся ко многим вещам!

Это что-то гораздо более сложное, чем просто понимание переполнения стека как выражения (или даже того, почему оно так называется - если вы не знаете, что посмотрите ЗДЕСЬ).

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

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

Итак, приступим прямо к делу!

Сложность: Начинающий | Легко | Нормальный | Испытывающий

Предпосылки:

  • Никто. Если вы знакомы с массивами, вы можете пропустить первый раздел (полное руководство по массивам находится ЗДЕСЬ)

Терминология

Массив: упорядоченная серия объектов одного типа.

Тип данных: представление набора данных, которые могут быть обработаны, например 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:

Любые вопросы? Вы можете связаться со мной здесь