Очереди

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

Рис.1.7. Организация дека на основе двусвязного линейного списка

Рис.1.8. Организация дека на основе двусвязного линейного списка

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

Рис.1.9. Организация дека с ограниченным входом на основе двусвязанного линейного списка

Рис.1.10. Организация дека с ограниченным выходом на основе двусвязанного линейного списка

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

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

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

Поиск по сайту: