Рис. 20. Структура очереди
Рис. 19. Структура стека
ОЧЕРЕДЬ – структура, у которой включение элемента производится в хвост, а исключение элемента и доступ к элементам выполняются в начале списка (рис. 20). Для очереди характерна дисциплина обслуживания “первым пришел – первым обслужен” (FIFO – First Input First Output).
ДЕК (двусторонняя очередь) – операции включения / исключения элементов и доступ к элементам выполняются как в начале, так и в хвосте списка.
СПИСКИ ПРОИЗВОЛЬНОГО ВИДА – операции включения / исключения элементов выполняются в любой точке структуры, возможен доступ к произвольному элементу списка.
Каждый элемент односвязного списка содержит одно или несколько информационных полей и единственное поле связи.
Элемент хранения односвязного списка описывается следующим образом:
Type Plist=^List; List= record info: word; link: plist; end; | { указатель на узел списка } { описание узла списка } { информационное поле узла } { поле связи узла } |
Var first: PList; p: PList; x: word; | { указатель на первый узел списка } { вспомогательный указатель } |
На рис. 21 представлен пример структуры односвязного списка.