Лабораторна робота № 1
Назва роботи: Моделювання структури даних «чергу FIFO»
Мета роботи: Докладне вивчення моделювання та способу організації даних в черзі FIFO
Теоретична частина
Поняття черги
Чергою FIFO («First in - First out» - «першим увійшов - першим вийшов») називається такий послідовний список зі змінною довжиною, в якому включення елементів виконується тільки з одного боку списку (цю сторону часто називають кінцем або хвостом черги), а виняток - з іншого боку (званої початком або головою черги).
Основні операції над чергою.
При роботі з чергою застосовують такі основні операції: - включення в чергу нового елемента. Якщо в позиції вже є елемент, то він зміщується, щоб звільнити місце для нового елемента. Усі наступні елементи перебудовуються з урахуванням нового.- видалення елемента з очереді.- очистка черги. Обнулення всіх елементів очереді.- висновок на екран вмісту черги.
Структурний вид черги приведений на рис. 1.
Рис. 1. Структурний вид черги.
Машинне уявлення черги і реалізація операцій
При включенні елемента в чергу останній записується за адресою, що визначається покажчиком на кінець, після чого цей покажчик збільшується на одиницю. При виключенні елемента з черги вибирається елемент, що адресується покажчиком на початок, після чого цей покажчик зменшується на одиницю. Очевидно, що з часом покажчик на кінець черги при черговому включенні елемента досягне верхньої межі тієї області пам'яті, яка виділена для черги. Однак, якщо операції включення чергувалися з операціями винятку елементів, то в початковій частині, відведеної під чергу пам'яті, є вільне місце. Для того, щоб місця, займані виключеними елементами, могли бути повторно використані, черга замикається в кільце: покажчики (на початок і на кінець), досягнувши кінця виділеної області пам'яті, переключаються на її початок. Така організація черги в пам'яті називається кільцевої чергою. Якщо в процесі роботи з кільцевою чергою число операцій включення перевищує число операцій виключення, то може виникнути ситуація, в якій покажчик кінця «наздожене» покажчик початку. Це ситуація заповненої черги і спроби запису в неї блокуються.
Використання типу даних «чергу».
Черга в програмуванні використовується, як і в реальному житті, коли потрібно зробити якісь дії в порядку їх надходження, виконавши їх послідовно. Прикладом може служити організація подій в Windows. Коли користувач надає якусь дію на додаток, то в додатку не викликається відповідна процедура (адже в цей момент додаток може вчиняти інші дії), а йому надсилається повідомлення, що містить інформацію про вчинений дії, це повідомлення ставиться в чергу, і тільки коли будуть оброблені повідомлення, що прийшли раніше, додаток виконає необхідну дію. Клавіатурний буфер BIOS організований у вигляді кільцевого масиву, звичайно довжиною в 16 машинних слів, і двох покажчиків: на наступний елемент в ньому і на перший незайнятий елемент.
Практична частина
На рис. 2 представлений вихідний код програми, яка демонструє процес функціонування черги.
Рис. 2 (початок). Вихідний код програми, що моделює чергу FIFO.
Рис. 2 (продовження). Вихідний код програми, що моделює чергу FIFO.
На рис. 3 представлено консольне вікно програми, що відображає результати функціонування черги при додаванні елементів.
Рис. 3. Вікно програми при додаванні елементів в чергу FIFO.
На рис. 4 представлено вікно програми, що відображає результати функціонування черги при видаленні всіх елементів, крім одного.
Рис. 4. Вікно програми при видаленні елементів з черги.
На рис. 5 представлена ??гістограма зміни сукупності значень елементів, що входять в чергу, залежно від послідовно проведених операцій додавання і видалення елементів.
Рис. 5. Гістограма зміни сукупності елементів.
Висновок
машинне чергу операція
У даній лабораторній роботі ми докладно вивчили моделювання черзі FIFO і спосіб організації даних в ній. У ході роботи на обчислювальній машині була змодельована чергу FIFO. Крім того була показана робота даної черзі на прикладі послідовності натуральних чисел, які спочатку додавалися, а потім віддалялися.
