Блог для любопытных и не только
Структуры

Стеки

  • Название: Стек (stack);
  • Применение: Способ хранения данных;
  • Время выполнения: Зависит от конкретной операции;
  • Сложность: Низкая;
  • Входные данные: Динамическая область памяти или массив;
  • Результат: Порядок данных по принципу LIFO ( Last Input – First Output, «последним пришел – первым вышел»).

Пример из жизни:

Существует стопка книг и предположим положили книгу на верх стопки. Если нужно взять последнюю положенную книгу, то необходимо извлечь эту книгу с вершины стопки. Получается для того чтобы достать книгу в самом низу требуется извлечь все книги последовательно. Т.е. с самой верхей, потом слудующую верхнюю  и т.д. Получается, что книги разбираются в порядке, обратном тому, в котором ставились. Данный случай можно распространить на бесконечное множество примеров — стопка тарелок, магазин патронов в автомате и т.д.

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

Стековую структуру можно сравнить с процессом выполнения различных дел во время рабочего дня. Например, имеется долгосрочная задача проект под названием (A). Вдруг поступает срочная задача — зайти расписаться в бугалтерию (B). Таким образом, все задачи немедленно прерываются и выполняется та задача, которая поступала последней в этот список. После выполнения последней задачи (B) поступила новая — звонок из другого отдела, которому нужен срочно отчет (C). Выполнив задачу (C), работник только потом приступает к своему проекту (А). Обратите внимание, такая схема работает при выполнени очень срочных задач и задач c низким приоритетом. Если бы поступила долгосрочная задача и с более низким приоритетом, скорей всего, ее пришлось бы отложить.

Определения:

Стек (англ. stack – стопка) – это абстрактная структура данных, которая реализует такой способ их хранения, в котором новый элемент всегда записывается в ее начало (вершину) и очередной извлекаемый элемент также всегда выбирается из ее начала. Еще такой порядок называют —  LIFO ( Last Input – First Output, «последним пришел – первым вышел»).

Итак, стек – это список, у которого доступен один элемент (одна позиция). Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека. Например, если записаны в стек числа 1, 2, 3, то при последующем извлечении получим 3,2,1. Можно сказать, что порядок добавления меняется на обратный при извлечении.

Если говорить о реальных примерах применения стека в IT . Программный вид стека используется для обхода структур данных, например, дерево или граф. При использовании рекурсивных функций также будет применяться стек, но аппаратный его вид. Часто стек применяется для синтаксического разбора различных выражений, например арифметических. Данный пример будет рассмотрен ниже.

Реализация:

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

Добавление элемента в стек:

Шаг 1. Находится последний элемент массива;

Шаг 2. Размер массива увеличивается на один элемент и добавляется элемент (если используется статический массив, размер, которого фиксирован и задается на этапе компиляции, находится последний занятый элемент массива и значение вставляется в следующую ячейку массива. При этом необходимо отслеживать);

Извлечение из стека:

Шаг 1. Находится последний элемент массива;

Шаг 2. Извлекается и сохраняется в промежуточную переменную;

Шаг 3. Данный элемент массива уничтожается и его размер уменьшается на один;

Шаг 4. Возращается сохраненное значение.

Программная разработка:

В компилируемых языках программирования стеки можно представить, используя динамические области памяти или массивы. В большинстве языков программирования стек реализован в виде готовых библиотек или функции. В php существуют две функции, которые выполняют операции с данными, как со стеком: array_push и array_pop, соотвественно для добавления и извлечения элементов из стека.

В нашем случае используем класс для реализации стека. Объявляем следующие свойства поля $data — массив (строка 3), который будет реализовывать стектовую архитектуру, $top — значение на вершине стека и $index — счетчик массива. Как было указано выше, существует основные три операции выполнения действий над стеком: добавление нового элемента, извлечение и получение текущего размера стека. На 8-10 реализован метод добавления нового элемента в стек, увелечивая счетчик на единицу. При извлечении элемента (11-16) происходит его удаление, с последующим возвращением удаленного значения (обратите внимание счетчик уменьшается на 1 т.к. элемента больше не существует и нужно обновить актуальный размер массива). Методы size() и getData() возвращают размер стека и его содержимое. Для чтения элемента на вершине стека достаточно прочитать последний элемент массива метод getHead().

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

Давайте рассмотрим простую задачу по разбору выражения в виде скобок! Это классическая задача синтаксического разбора, в которой можно и нужно применить стек.

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

В данном примере, происходит сохранение в стеке только открывающихся скобок вида ( «[«, «(» ). Если попадаются скобки обратного вида, при чтении строки ( «]», «)» ), то происходит сравнение этих скобок методом чтения вершины стека. Таким образом, если сравнение выполняется, то происходит выталкивание из стека данной скобки pop(). Соотвественно,если в стеке осталась хоть одна скобка, выражение считается не валидным.

Время выполнения

Алгоритм В среднем В худжем случаее Пояснение
Добавление O(1) O(n)  
Извлечение O(1) O(n)  
Удаление O(1) O(n)    
Список источников

 

Поделиться

Отправить ответ

avatar
wpDiscuz