2. 3. Стек.

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

В силу указанной дисциплины обслуживания, в стеке доступна единственная его позиция, которая называется вер­шиной стека- это позиция, в которой находится последний по времени поступления в стек элемент.

Графически стек можно представить следующим обра­зом:

EN	Вершина стека
…
…
E2
E1	Нижняя граница стека

Рис. 4 – Графическое изображение стека

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

АТД «стек» использует следующие пять операторов:

1. MAKENUL – делает стек пустым.

2. TOP – возвращает копию элемента из стековой вершины.

3. POP – достаёт элемент из вершины стека. Иногда реализует возвращение удаляемого элемента.

4. PUSH – помещает элемент в стек, делая его вершиной, а предыдущую вершину вторым элементом.

5. Stacktop(S) - Прочтение элемента без его выборки из стека.

- Реализация стека посредством массива. В низу массива зафиксиhetz дно стека max и стек «растет» вверх по массиву к ячейки с наименьшим индексом. На вершину стека будет указывать курсор с именем top, который определяет текущее положение первого элемента стека. Данное представление стека показано на рисунке 5.

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

О ператор PUSH добавляет элемент лишь в вершину стека. Добавление элемента происходит следующим образом: создаётся новая ячейка, в поле next записывается указатель на прошлую вершину стека, а указатель на новую ячейку становится новым указателем на вершину стека (рис.6).

рис. переделать.

3. 5. Очередь

Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание

Очередь – это структура данных, представляющая собой последовательность элементов.

Д обавление элементов происходит с одной стороны последовательности, удаление – с другой. Рис. 7.

Рис. 7 – Графическое изображение очереди

Заказ поступает в очередь первым, выбирается первым для обработка (и удаляется из очереди тоже первым) называется FIFO (первым пришел, первым ушел). Такая очередь открыта с обеих сторон.

Для работы с очередями используются следующие операторы:

1. MAKENUL – делает очередь пустой.

2. FRONT – возвращает копию элемента из начала очереди.

3. ENQUEUE – эта процедура вставляет новый элемент в конец очереди.

4. DEQUEUE – осуществляет удаление первого элемента из очереди.

5. EMPTY – возвращает значение true, если очередь пуста, и значение false, если в ней есть элементы

Реализация очередей с помощью циклических массивов. Во время представления очередей с помощью массивов (рис.8) возникает трудность, связанная с определением пустоты очереди, так как по взаимному расположению указателей конца и начала не возможно определить, когда очередь пуста, а когда заполнила весь массив.

Реализация очередей с помощью указателей. Так же как и «стек», «очередь» является специальным типом списка и, имея похожую структуру, обладает рядом отличий при добавлении рис. 9 и удалении элементов рис. 10

Вставка элемента осуществляется оператором enqueue ((по)ставить в очередь) осуществляется добавление элемента следующим образом: создаётся новая ячейка, и указать на неё записывается вместо nil в поле next конечного элемента очереди, т.е. указатель P4 был записан вместо nil в поле next ячейки, на которую указывает указатель P3 (рис. 9а, 9б)

Dequeue (выводить [исключать] из очереди), удаляя первый элемент из очереди, отсоединяет от очереди прежнее начало, в результате чего новая ячейка становится первым элементом списка. Указатель на начало очереди P0 присваивается новое значение – P2, что исключило из очереди прежнее начало, т.е. элемент a с указателем на него P1.(рис. 10а, 10б)

2. 6. Дек.

О собенностью деков является то, что запись и удаление ячеек может производиться с двух концов дека (рис.11). В английской аббревиатуре дек записывается следующим образом - DEQ (Double Ended Queue - Очередь с двумя концами). Дек так же можно рассматривать и в виде двух стеков, соединенных нижними границами.

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

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