1. Чергу можна визначити як упорядкований список, який дозволяє виконувати операції вставки на одному кінці, який називається ЗАДНІЙ і операції видалення, які мають бути виконані на іншому кінці ПЕРЕДНІЙ .
2. Черга називається списком «Першим прийшов, першим вийшов».
3. Наприклад, люди, які стоять у черзі за залізничним квитком, утворюють чергу.
Застосування черги
Через те, що черга виконує дії за принципом «перший прийшов, перший вийшов», що цілком справедливо для порядку дій. Існують різні застосування черг, розглянуті нижче.
- Черги широко використовуються як списки очікування для одного спільного ресурсу, наприклад принтера, диска, ЦП.
- Черги використовуються в асинхронній передачі даних (де дані не передаються з однаковою швидкістю між двома процесами), наприклад. труби, файл IO, розетки.
- Черги використовуються як буфери в більшості програм, таких як медіаплеєр MP3, програвач компакт-дисків тощо.
- Черга використовується для підтримки списку відтворення в медіаплеєрах, щоб додавати та видаляти пісні зі списку відтворення.
- Черги використовуються в операційних системах для обробки переривань.
Складність
| Структура даних | Складність часу | Повнота простору | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Середній | Найгірше | Найгірше | |||||||
| Доступ | Пошук | Вставка | Видалення | Доступ | Пошук | Вставка | Видалення | ||
| Черга | i(n) | i(n) | i(1) | i(1) | O(n) | O(n) | О(1) | О(1) | O(n) |