Структуры и алгоритмы обработки данных


Очереди


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

pic1_7.jpg (36304 bytes)

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

pic1_8.jpg (35131 bytes)

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

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

pic1_9.jpg (44182 bytes)

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

pic1_10.jpg (47063 bytes)

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

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

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

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




Начало  Назад  Вперед



Книжный магазин