Черга програмування, уроки і приклади

Глава 2. Складні структури даних

створення черги (create_que);
включення елемента в чергу (push_que);
виключення елемента з черги (popque);
перевірка порожнечі черзі (TestEmptyQue);
очищення черги без звільнення пам'яті для неї (initque);
видалення черги (delete_que).

За допомогою черги зручно моделювати деякі обслуговуючі дії, наприклад це може бути деяка чергу запитів до критичного ресурсу або черги завдань на обробку. До черзі так само, як і стека, застосовні такі параметри, як ємність черги і розмір елемента черги.
На практиці використовуються черзі двох типів - прості і кільцеві. Черга обслуговується двома покажчиками - голови (Р,) і хвоста черги (Р2). Покажчик голови Р ідентифікує найстаріший елемент черги, покажчик хвоста - перший вільний слот після останнього включеного в чергу елемента. Самі елементи фізично по черзі не рухаються. Змінюється лише значення покажчиків. При включенні в чергу новий елемент заноситься в комірку черзі, на яку вказує Р2. Операція виключення увазі витяг елемента з осередку черзі, про яку йдеться Р. Крім вилучення елемента операція виключення здійснює коригування покажчика Р, так, щоб він вказував на черговий найстаріший елемент черги. Таким чином, Покажчик хвоста простий черги завжди вказує на вільну комірку очерь-Ді і рано чи пізно він вийде за межі блоку, виділеного для черги. І це трапиться не дивлячись на те, що в черзі можуть бути вільні комірки
(Осередку А. Щоб виключити це явище, чергу організовується за принципом кільця. У обох способах організації черги важливо правильно визначити її ємність. Недостатній обсяг черзі може привести в певний момент до її переповнення, що може призвести до втрати нових елементів, які претендують на включення в чергу.
Для ілюстрації порядку організації і роботи з чергою розглянемо приклад. Нехай є рядок символів, яка в такий спосіб моделює деяку обчислювальну ситуацію: символи букв означають запити на деякий ресурс і підлягають постановці в чергу (має обмежений розмір). Якщо серед символів зустрічаються символи цифр в діапазоні 1-9, то це означає, що необхідно вилучити з черги відповідає значенню цифри кількість елементів. Якщо чергу повна, а символів цифр все немає, то відбувається втрата заявок (символів букв). У нашій програмі будемо вважати, що черга кільцевої і її переповнення крім втрати нових елементів призводить до висновку відповідного повідомлення. Для кільцевої черзі можливі наступні співвідношення значень покажчиків Р, і Р2: Pj <Р2, Pj = Р2 (пустая очередь), Р,> Р2. Пам'ять для черги в нашому завданні виділяється динамічно засобами API Win32.
Зауважимо, що виходячи з потреб конкретного завдання можна змінити дисципліну обслуговування черги. Наприклад, встановити, що при переповненні черги втрати підлягають старі заявки (в голові черги) і т. П.

jb ml cmpa1.39h
ja ml
xor есх.есх: удгляем з черги елементи
mov cl, al
subcl, 30h перетворимо символ цифри в двійковий еквівалент ш2: pop_quechar_que.
jc cycl; якщо чергу порожня
1 oop m2
jmpcycl ml: додаємо елементи в чергу
mov temp, a 1
push_que char_que.
jnc cycl; ycnex; Вибір нотатки про помилку - відсутність місця в черзі
jmp cycl
; Вихід з програми exit. видаляємо блок пам'яті з чергою
delete_que char_que

Як і у випадку зі стеком, код, який виконує роботу з чергою, оформлений у вигляді макрокоманд. Програма видає єдине Повідомлення про переповнення черги. Щоб спостерігати роботу програми в динаміці, необхідно виконати наступні дії.