13. Линейные структуры данных. Стек.

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

Стек можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка.

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

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

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

Описание элементов стека аналогично описанию элементов линейного однонаправленного списка, где DataType является типом элементов стека. Поэтому здесь приводить его не будем.

Основные операции, производимые со стеком: записать (положить в стек); прочитать (снять со стека); очистить стек; проверка пустоты стека.

14. Линейные структуры данных. Очередь.

Очередь – это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. Здесь используется принцип «первым пришел – первым вышел» (FIFO: First Input – First Output).

Очередь можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка.

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

Элементы очереди располагаются в «круге» элементов массива в последовательных позициях, конец очереди находится по часовой стрелке на некотором расстоянии от начала. При этом необходимо отдельно хранить значение индекса элемента массива, являющегося началом очереди, и значение индекса элемента массива, являющегося концом очереди. Когда происходит добавление в конец или извлечение из начала очереди, осуществляется смещение значений этих двух индексов по часовой стрелке.

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

Основные операции, производимые с очередью:

– добавить элемент;

– извлечь элемент;

– очистить очередь;

– проверка пустоты очереди.