Структура данных. Стек

1.

СТРУКТУРА ДАННЫХ
СТЕК

2.

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

3.

Стек
Стек — это структура данных, в которой элементы добавляются и удаляются
в порядке «последним пришел, первым ушел». Из-за такого поведения их иногда
называют списками LIFO, или просто LIFO (от англ. last in first out).
Стек легко представить в виде стопки книг, лежащей на столе: можно добавить
или убрать книгу сверху, но нельзя вынуть ее из середины или снизу, не разрушив
всю конструкцию. Еще один хороший пример — стопка тарелок с пружинной
фиксацией, которая используется в кафе. Если добавить тарелку сверху, то
пружина сожмется и вся стопка окажется вровень со столешницей. То же самое
произойдет при снятии тарелки, когда пружина ослабнет.

4.

Стек
Такую структуру данных иногда еще называют стеком магазинного типа;
добавление объекта — вдавливанием в стек, а удаление — выталкиванием из
стека.
Класс стека обычно предусматривает методы Push и Pop для добавления
элементов и их удаления соответственно. Элементы помещаются и извлекаются с
головы стека (top).

5.

Стек и C#
Класс Stack<T> представляет коллекцию, которая использует алгоритм LIFO
("последний вошел - первый вышел"). При такой организации каждый следующий
добавленный элемент помещается поверх предыдущего. Извлечение из коллекции
происходит в обратном порядке - извлекается тот элемент, который находится выше
всех в стеке.
Для создания стека можно использовать один из трех конструкторов. Прежде всего
можно создать пустой стек:
При создании пустого стека можно указать емкость стека:

6.

Стек и C#
Также можно инициализировать стек элементами из другой коллекции или
массивом:
Для перебора стека можно использовать стандартный цикл foreach. Причем в
цикле в соответствии с аалгоритмом стека LIFO данные извлекаются в порядке,
обратном их добавлению. Консольный вывод в данном случае:
Для получения количества элементов
стека применяется свойство Count.

7.

Стек и C#
В классе Stack можно выделить следующие методы:
Clear: очищает стек
Contains: проверяет наличие в стеке элемента и возвращает true при его наличии
Push: добавляет элемент в стек в верхушку стека
Pop: извлекает и возвращает первый элемент из стека
Peek: просто возвращает первый элемент из стека без его удаления

8.

Стек и C#
Рассмотрим пример:

9.

Стек и C#
Стоит отметить, что если с помощью методов Peek или Pop мы попытаемся
получить первый элемент стека, который пуст, то программа выдаст исключение.
Соответственно перед получением элемента мы можем проверять количество
элементов в стеке:

10.

Стек и C#
Либо можно использовать пару методов:
bool TryPop(out T result): удаляет из стека первый элемент и передает его в
переменную result, возвращает true, если очередь не пуста и элемент успешно
получен.
bool TryPeek(out T result): передает в переменную result первый элемент стека
без его извлечения, возвращает true, если элемент успешно получен.

11.

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

12.

Стеки связных списков
Алгоритм
удаления
элемента
из
стека
на
основе
связного
списка:

13.

Стеки связных списков
Рассмотренный процесс показан на рисунке 5.2. Верхний фрагмент отражает
состояние стека после того, как программа вставила в него буквы A, P, P,
L и E; средний — тот же стек после добавления буквы S, нижний — после ее же
удаления.

14.

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

15.

Стеки массивов
Следующий псевдокод содержит алгоритм удаления элемента из стека на
основе
массива.

16.

Стеки массивов
Описанный процесс показан на
рисунке 5.3. Верхний фрагмент —
это стек, в который добавлены
буквы A, P, P, L и E; средний и
нижний фрагменты — стек после
вставки и удаления буквы S
соответственно.

17.

Стеки массивов
В случае с массивами операции вдавливания и выталкивания элементов занимают время
O(1) и являются довольно быстрыми. Кроме того, установка и получение
значения из массива происходят быстрее, чем создание новой ячейки в связном
списке, а потому такой метод более эффективен.
Основанный на массиве стек не нуждается и в дополнительной памяти для
хранения ссылок между ячейками, но ему требуется место для новых элементов.
Объем такого места зависит от используемого приложения и от того, известно ли
вам заранее количество записей. Если нет — при необходимости можно изменить
размер массива, но это займет дополнительное время. Если в массиве N элементов,
то при изменении его размера понадобится выполнить O(N) шагов, чтобы скопировать уже
имеющиеся записи.
В зависимости от того, как используется стек, резервирование места для дополнительных
элементов
может
быть
крайне
неэффективным.
Предположим,
что
в какой-то момент алгоритму понадобится сохранить 1000 записей в стеке, хотя
большую часть времени ему нужно всего несколько. В таком случае массив будет
тратить неоправданно много ресурсов памяти. Если же вы знаете, что в стеке всегда будет
храниться всего нескольких элементов, то имеет смысл выстраивать его на основе массива.

18.

Реализация собственного класса стека на основе массива
В библиотеке классов .NET в принципе уже есть свой класс, который выполняет роль
стека. Это класс - System.Collections.Generic.Stack. Но рассмотрим, как мы сами можем
реализовать структуру в виде стека.
Структура стек вне зависимости от языка программирования обладает неким общим
функционалом, который составляют метод добавления элемента (push()) и метод
извлечения элемента из вершины стека (pop()). Кроме того, нередко реализации стеков
содержат метод получения элемента из вершины без его извлечения, метод определения
размера стека и ряд других

19.

Реализация собственного класса стека на основе массива
В начале для реализации структуры данных определим следующий класс:

20.

Реализация собственного класса стека на основе массива

21.

Реализация собственного класса стека на основе массива
Данная реализация представляет обобщенный класс, а поэтому позволяет хранить
элементы любого типа. Сами элементы в стеке в реальности будут храниться в
массиве items. Для хранения реально добавленного количества элементов в стек
служит переменная count.
Для инициализации стека служат два конструктора. Конструктор без параметров
создает массив items с длиной 10. Через конструктор с параметром можно
самостоятельно установить длину массива.
В методе Push() добавляем элемент в массив, при этом увеличивая значение
переменной count. Если же стек (а фактически массив items) уже заполнен, то
выбрасываем исключение.
В методе Pop() извлекаем элемент из верхушки стека, при этом уменьшая значение
переменной count. Если в стеке нет элементов, то выбрасываем исключение.

22.

Реализация собственного класса стека на основе массива
Применение стека:

23.

Реализация собственного класса стека на основе массива
Схематично все операции можно выразить следующим образом:

24.

Реализация собственного класса стека на основе массива
Данный стек имеет один важный недостаток - что если мы вначале не знаем точно,
сколько стек может будет содержать элементов. Фиксированная длина массива
накладывает ограничение на работу со стеком. Чтобы решить эту проблему, нам
надо динамически менять длину массива при увеличении или уменьшении до
определенного момента. Так, определим следующий класс стека:

25.

Реализация собственного класса стека на основе массива
В данном случае в класс стека по сравнению с предыдущим случаем добавлен
метод Resize, который изменяет размер массива до значения max. Для этого в
методе просто создается новый массив, в который копируются данные из старого.
Теперь при добавлении в методе Push() больше не надо проверять стек на
переполнение. Если вдруг в массиве items больше не окажется места, то мы
вызовем функцию Resize, которая увеличит массив на 10 элементов:

26.

Реализация собственного класса стека на основе массива
При удалении элемента в методе Pop аналогично изменяем размер, если в массиве
items образовалось более 10 пустых ячеек.
Здесь при добавлении и удалении идет изменение количества элементов на 10.
Можно увеличивать/уменьшать в два раза и т.д. Однако следует помнить, что
изначальное выделение больших объемов памяти увеличит совокупную память,
потребляемую приложением. При этом не факт, что хотя бы половина из нее будет
использоваться.
В то же время если увеличивать/уменьшать понемногу размер массива, то это
увеличит частоту перераспределения памяти, что в конечном счете ведет к
уменьшению производительности.
Таким образом, стек стал более гибким в отношении размеров массива, однако
сохранил ряд недостатков, связанных с массивами - необходимости
перераспределения памяти при добавлении или удалении данных, и увеличении
сложности вычислительного алгоритма.