Очередь

(FIFO - First In First Out)

Данные:

Адрес головы очереди,

Адрес хвоста очереди.

Допустимые операции:

Создать очередь из 1 элемента;

Добавить элемент в хвост очереди;

Удалить элемент из головы очереди;

Проверка на отсутствие элементов (пустая очередь);

Узнать значение информационной части первого элемента.

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

Дек (двунаправленная очередь)

Данные:

Адрес головы дека,

Адрес хвоста дека.

Допустимые операции:

Создать дек из 1 элемента;

Добавить элемент в голову/хвост дека;

Удалить элемент из головы/хвоста дека;

Проверка на отсутствие элементов.

Очистить дек (удалить все элементы)

Узнать значение информационной части первого или последнего элемента.

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

Стек (LIFO - Last In First Out)

Данные:

Адрес вершины стека

Допустимые операции:

Создать стек и поместить в него 1 элемент;

Добавить элемент в вершину стека;

Удалить элемент из вершины стека;

Проверка на отсутствие элементов (стек пуст);

Очистить стек (удалить все элементы)

Узнать значение информационной части элемента в вершине стека.

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