Page 63 - 4656

Алгоритми і структури даних. Лабораторний практикум.

Лабораторна робота № 8.
Черги

Мета: ознайомитись із поняттям черги у програмуванні.
Алгоритм роботи черги. Навчитися використовувати структуру
даних черга на прикладі мови Джава.
Теоретичні відомості

Черга (англ. queue) в програмуванні — динамічна
структура даних, що працює за принципом «перший прийшов —
перший пішов» (англ. FIFO — first in, first out). У черги є голова
(англ. head) та хвіст (англ. tail). Елемент, що додається до черги,
опиняється в її хвості. Елемент, що видаляється з черги,
знаходиться в її голові.
Така черга повністю аналогічна звичній «базарній» черзі,
в якій хто перший встав в неї, той першим буде обслуженим.
Основні операції з чергою:
1. англ. enqueue — "поставити в чергу". Операція додавання
елемента в "хвіст" черги. При цьому довжина черги
збільшується на одиницю. Якщо відбувається намагання
додати елемент у вже заповнену чергу, відбувається її
переповнення (англ. queue overflow).
2. англ. dequeue — "отримання з черги". Операція, яка повертає
елемент з голови та видаляє його з черги, таким чином
встановлюючи голову на наступний за видаленим елемент та
зменшуючи довжину на одиницю. При намаганні видалити
елемент з пустої черги, виникає ситуація "незаповнення"
(англ. queue underflow).
Приклад реалізації черги на мові Джава:

//Клас - елемент черги
public class lineElement {
// число - корисна інформація
61