Черги з пріоритетами
У реальних завданнях іноді виникає потреба у формуванні черг, порядок вибірки елементів у тому числі визначається пріоритетами елементів. Пріоритет у випадку може бути представлений числовим значенням, яке обчислюється чи підставі значень будь-яких полів елемента, чи підставі зовнішніх чинників. Так, і FIFO, і LIFO можуть трактуватися як пріоритетні черги, у яких пріоритет елемента залежить від часу його включення до черги. При вибірці елемента щоразу вибирається елемент із найбільшим пріоритетом.
Черги із пріоритетами м. б. реалізовані на лінійних спискових структурах - у суміжному чи зв'язковому поданні. Можливі черги з пріоритетним включенням - у яких послідовність елементів черги постійно підтримується упорядкованої, тобто. кожен новий елемент включається те місце в послідовності, яке визначається його пріоритетом, а при виключенні завжди вибирається елемент з початку. Можливі і черги з пріоритетним винятком - новий елемент завжди включається в кінець черги, а при виключенні в черзі шукається (цей пошук може бути тільки лінійним) елемент з максимальним пріоритетом і після вибірки видаляється з послідовності. І в тому, і в іншому варіанті потрібен пошук, а якщо черга розміщується у статичній пам'яті – ще й переміщення елементів.
Найбільш зручною формою для організації великих черг з пріоритетами є сортування елементів за спаданням пріоритетів частково впорядкованим деревом, кіт. Розглянемо далі.
Черги у обчислювальних системах
Черга є одним із ключових понять у багатозадачних ОС (Windows NT, Unix, OS/2, ЄС та ін.). Ресурси обчислювальної системи (процесор, оперативна пам'ять, зовнішні пристрої і т.п. (використовуються всіма завданнями,одночасно виконуваними серед такої ОС. Т.к. Багато видів ресурсів не допускають одночасного використання різними завданнями, такі ресурси надаються завданням по черзі. Т. о., завдання, що претендують на використання того чи іншого ресурсу, вишиковуються в чергу до цього ресурсу. Ці черги зазвичай пріоритетні, але досить часто застосовуються і FIFO-черги, тому що це єдина логіч. організація черги, яка гарантовано не допускає постійного витіснення завдання пріоритетнішими. Стеки зазвичай використовуються ОС обліку вільних ресурсів.
Також у сучасних операційних системах одним із засобів взаємодії між паралельно виконуваними завданнями є черги повідомлень, які називаються також поштовими скриньками. Кожне завдання має свою чергу - поштову скриньку, і всі повідомлення, що надсилаються їй від інших завдань, потрапляють у цю чергу. Завдання-власник черги вибирає з неї повідомлення, причому може керувати порядком вибірки - FIFO, LIFO або за пріоритетом.