Черга на Java. теорія
Структура даних, яка називається в інформатиці чергу, кілька нагадує стек, але в черзі першим вилучається елемент, вставлений першим. (Спосіб організації даних FIFO, First-In-First-Out), в той час як в стеці ми бачили, що першим вилучався той елемент, який вставлявся останнім (спосіб організації даних LIFO, Last-In-First-Out).
Черга працює за тим же принципом як і будь-яка чергу в кіно (людина, яка першою встав в чергу, першим дійде до каси і купить квиток). Відповідно той хто стане в чергу останнім, купить квиток останнім (або не купить його взагалі, якщо всі квитки будуть розпродані).
Черга - такий же допоміжний інструмент програміста, як і стек. Вони використовуються для моделювання реальних ситуацій очікування клієнтів в банку, вильоту літаків або передачі даних по Інтернету.
Де використовується чергу?
В операційній системі Вашого комп'ютера (і в мережі інтернет) постійно працюють різні черги, непомітно виконують свої обов'язки.
Наприклад, в черзі друку - документи чекають звільнення принтера. Дані вводяться з клавіатури, також зберігаються в черзі.
Реалізація черзі
Проілюструємо нашу чергу. Перший елемент в черзі назвемо Front, елемент який знаходить в черзі останніми - Rear. Основою нашої черги буде класичний масив.
Дві основні операції з чергою, це: вставка елемента в кінець черги і видалення елемента з початку черги.
Графічна ілюстрація вставки елемента (вставляємо число 7):
Видалимо елемент з початку черги (321):
Варто розглянути таке явище, як циклічний перенос. При вставки нового елемента, маркер Front зміщується вгору в сторону більш високих індексів. При видаленні елементів, маркер Rear також зміщується вгору. Проблема в тому, що навіть якщо на початку масиву будуть порожні клітинки, з яких були вилучені елементи, вставити новий елемент не вийде, тому що маркера Rear нікуди рухатися далі. Проілюструємо цю ситуацію:
Для вирішення цієї проблеми зі вставкою в чергу в якій є вільні комірки, маркери Front і Rear при досягненні межі масиву переміщаються до його початку. Така структура даних називається циклічною чергу (або кільцевих буфером).
Приклад черзі (Queue) на Java
Реалізуємо чергу на базі масиву. Оголосимо і ініціалізує змінні: