Міністерство освіти і науки, молоді та спорту України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт про виконання лабораторної роботи № 2 з дисципліни: “Обчислювальний практикум” на тему: “ Застосування АТД "Черга" до розв’язання прикладних задач”  Львів 2013 Мета: Ознайомитись з АТД «Черга» Теоретичні відомості: Черга - структура даних з дисципліною доступу до елементів "перший прийшов - перший вийшов" ( FIFO, First In - First Out). Додавання елемента (прийнято позначати словом enqueue - поставити в чергу) можливо лише в кінець черги, вибірка - тільки з початку черги (що прийнято називати словом dequeue - прибрати з черги), при цьому обраний елемент з черги видаляється. Способи реалізації черги Існує кілька способів реалізації черзі в мовах програмування. Масив Перший спосіб являє чергу у вигляді масиву і двох цілочисельних змінних start і end. / Зазвичай start вказує на голову черги, end - на елемент, який заповниться, коли в чергу увійде новий елемент. При додаванні елемента в чергу в q[end]записується новий елемент черги, а end зменшується на одиницю. Якщо значення end стає менше 1, то ми як би циклічно обходимо масив і значення змінної стає рівним n. Витяг елемента з черги проводиться аналогічно: після вилучення елемента q[start] з черги змінна start зменшується на 1. З такими алгоритмами один осередок з n завжди буде незайнятої (так як черга з n елементами неможливо відрізнити від порожньої), що компенсується простотою алгоритмів. Переваги даного методу: можлива незначна економія пам'яті в порівнянні з другим способом; простіше в розробці. Недоліки: максимальна кількість елементів в черзі обмежене розміром масиву. При його переповненні потрібно перевиделеніе пам'яті і копіювання всіх елементів в новий масив Зв'язний список Другий спосіб заснований на роботі з динамічною пам'яттю. Чергу представляється в якості лінійного списку, в якому додавання / видалення елементів йде строго з відповідних його кінців. Переваги даного методу: розмір черги обмежений лише обсягом пам'яті. Недоліки: складніше в розробці; потрібно більше пам'яті; при роботі з такою чергою пам'ять сильніше фрагментируется; робота з чергою трохи повільніше. Реалізація на двох стеках Чергу може бути побудована з двох стеков S1 і S2 як показано нижче: Процедура enqueue (x): S1.push (x) Процедура dequeue (): якщо S2 порожній: якщо S1 порожній: повідомити про помилку: черга порожня поки S1 не порожній: S2.push (S1.pop ()) return S2.pop () Такий спосіб реалізації найбільш зручний в якості основи для побудови персистентной черзі. Застосування черг Черга в програмуванні використовується, як і в реальному житті, коли потрібно зробити якісь дії в порядку їх надходження, виконавши їх послідовно. Прикладом може служити організація подій у Windows. Коли користувач надає якусь дію на додаток, то в додатку не викликається відповідна процедура (адже в цей момент додаток може вчиняти інші дії), а йому надсилається повідомлення, що містить інформацію про скоєний дії, це повідомлення ставиться в чергу, і тільки коли будуть оброблені повідомлення, що прийшли раніше, додаток виконає необхідну дію. Клавіатурний буфер BIOS організований у вигляді кільцевого масиву, зазвичай довжиною в 16 машинних слів, і двох покажчиків: на наступний елемент у ньому і на перший незайнятий елемент. Завдання: Автостоянка має одну полосу, на якій може бути розмiщено до 10 автомобiлiв. Машини в'їжджають з пiвденного кiнця стоянки i від'їжджають з пiвнiчного. Якщо автомобiль власника, що прийшов на стоянку забрати його, не розташований пiвнiчнiше за всі решту, то всi автомобiлi, що стоять пiвнiчнiше його, виїжджають iз зупинки, потiм виїжджає його машина і всі машини повертаються в початковому порядку. Якщо машина залишає гараж, то всi машини розташованi пiвденнiше, перемiщаються вперед на стiльки позицій, скiльки є вiльних мiсць в пiвнiчнiй частинi. Написати програму зчитування групи рядків, кожний з яких мiстить літеру "A" для прибуття i літеру "D" для вiдправленн...