Черга може бути описана як непримітивна структура лінійних даних, яка відповідає порядку FIFO, в якому елементи даних вставляються з одного кінця (задній кінець) і видаляються з іншого кінця (передній кінець). Іншими варіантами черги є кругова черга, двічі закінчена чергу і чергу пріоритетів.
Діаграма порівняння
| Основа для порівняння | Лінійна черга | Кругова черга |
|---|---|---|
| Основний | Організує елементи даних та інструкції послідовно один за одним. | Впорядковує дані в круговому шаблоні, де останній елемент з'єднаний з першим елементом. |
| Порядок виконання завдання | Завдання виконуються для того, щоб вони були розміщені раніше (FIFO). | Порядок виконання завдання може змінитися. |
| Вставка та видалення | Новий елемент додається з заднього кінця і знімається з фронту. | Вставка і видалення можуть бути зроблені в будь-якому положенні. |
| Продуктивність | Неефективно | Працює краще, ніж лінійна черга. |
Визначення лінійної черги
Лінійна черга раціонально є першим у першому списку. Вона називається лінійною, оскільки вона нагадує пряму лінію, де елементи розташовані один за одним. Він містить однорідний набір елементів, в які додаються нові елементи в одному кінці і видаляються з іншого кінця. Концепцію черги можна зрозуміти на прикладі черги аудиторії, що чекає поза лічильника квитків, щоб отримати квиток на театр. У цій черзі, особа приєднується до заднього кінця черги, щоб взяти квиток, і квиток видається в передньому кінці черги.
У черзі виконується кілька операцій
- По-перше, чергу ініціалізується до нуля (тобто порожній).
- Визначте, чи є чергу порожньою чи ні.
- Визначте, чи є чергу повна чи ні.
- Вставка нового елемента з заднього кінця (Enqueue).
- Видалення елемента з переднього кінця (Dequeue).
Черга може бути реалізована двома способами
- Статично (з використанням масивів)
- Динамічно (за допомогою вказівників)
Обмеження лінійної черги полягає в тому, що він створює сценарій, де не можна додавати новий елемент у чергу, навіть якщо в черзі містяться порожні пробіли. Наведена вище ситуація ілюструється на малюнку, наведеному нижче. Тут тил вказує на останній індекс, тоді як всі поля ще порожні, новий елемент не може бути доданий.
Визначення кругової черги
Кругова черга - це варіант лінійної черги, який ефективно долає обмеження лінійної черги. У круговій черзі новий елемент додається в першій позиції черги, якщо останній зайнятий, а простір доступний. Коли мова йде про лінійну чергу, вставка може виконуватися тільки з заднього кінця і видалення з переднього кінця. У повній черзі після виконання серії послідовних видалень в черзі виникає певна ситуація, коли новий елемент не може бути доданий далі, навіть якщо доступний простір, оскільки умова підтоку (Rear = max - 1) все ще існує.
Циркулярна черга з'єднує два кінці через покажчик, коли перший елемент приходить після останнього елемента. Вона також відстежує фронт і задню частину, реалізуючи деяку додаткову логіку, щоб вона могла простежити елементи, які потрібно вставити і видалити. При цьому кругова черга не генерує умови переповнення, поки чергу не буде заповнена фактичною.
Деякі умови, що супроводжуються циркулярною чергою:
- Фронт повинен вказувати на перший елемент.
- Черга буде порожньою, якщо Front = Rear.
- При додаванні нового елемента чергу збільшують на значення (Rear = Rear + 1).
- Коли елемент видаляється з черги, фронт збільшується на один (Front = Front + 1).
Ключові відмінності між лінійною чергою та циркулярною чергою
- Лінійна черга є впорядкованим списком, в якому елементи даних організовані в послідовному порядку. Навпаки, кругова черга зберігає дані круговим способом.
- Лінійна черга йде по порядку FIFO для виконання завдання (елемент, доданий у першу позицію, буде видалено у першій позиції). І навпаки, в круговій черзі порядок операцій, що виконуються над елементом, може змінюватися.
- Вставка і видалення елементів фіксується в лінійній черзі, тобто доповнення від заднього кінця і видалення з переднього кінця. З іншого боку, циркулярна черга здатна вставляти і видаляти елемент з будь-якої точки, поки він не буде зайнятий.
- Лінійна черга витрачає пам'ять, а кругова черга робить ефективне використання простору.
Реалізація лінійної черги
Наведений нижче алгоритм ілюструє додавання елементів у чергу:
Черга потребує трьох змінних даних, включаючи один масив для зберігання черги, а інший для зберігання передньої та задньої початкової позиції, яка дорівнює -1.
insert (item, queue, n, rear) {if (задній == n), після чого надрукуйте "переповнення черги"; ще {задня = задня + 1; queue [rear] = елемент; }} Наведений нижче алгоритм ілюструє видалення елементів в черзі:
delete_circular (item, queue, rear, front) {if (задній == фронт), потім надрукуйте "queue underflow"; else {front = front + 1; item = queue [фронт]; }} Реалізація кругової черги
Алгоритм інтерпретації додавання елемента в круговій черзі:
insert_circular (елемент, чергу, задній, передній) {тил = (задній + 1) mod n; якщо (спереду == ззаду), то друк "чергу заповнена"; else {queue [rear] = елемент; }} Алгоритм пояснює видалення елемента в круговій черзі:
delete_circular (елемент, чергу, задній, передній) {if (front == задні), потім print ("чергу порожня"); else {front = front + 1; item = queue [фронт]; }} Висновок
Лінійна черга є неефективною в деяких випадках, коли для переходу на вільні простори потрібно виконати операцію вставки. Саме тому вона прагне витрачати місце для зберігання, тоді як кругова черга робить належне використання місця для зберігання, оскільки елементи додаються в будь-яку позицію, якщо існує порожній простір.
