В інформатиці черга — це лінійна структура даних, де компоненти поміщаються в один кінець і видаляються з іншого кінця відповідно до принципу «першим прийшов, першим вийшов» (FIFO). Ця структура даних може бути використана для керування послідовністю дій або зберігання даних. C — це комп’ютерна мова з можливістю створення черги у вигляді масивів або пов’язаних списків.
Характеристики:
- Черга — це тип лінійної структури даних, яку можна побудувати за допомогою масиву або зв’язаного списку.
- Елементи переміщуються в кінець черги, а їх видаляють з початку.
- Enqueue (додавання елемента назад) і dequeue (видалення елемента спереду) — дві операції черги.
- Коли елементи часто додаються та видаляються, чергу може бути побудовано як циклічна, щоб запобігти марнотратству пам’яті.
Використання масиву:
Щоб реалізувати чергу в C за допомогою масиву, спочатку визначте максимальний розмір черги та оголосите масив такого розміру. Переднім і заднім цілими числами встановлено значення 1 відповідно. Змінна front представляє передній елемент черги, а змінна back представляє задній елемент.
Перш ніж помістити новий елемент у кінцеву позицію черги, нам потрібно збільшити змінну back на 1. Тепер черга заповнена, і жодні додаткові елементи не можуть бути додані, коли задня позиція досягне максимальної місткості черги. Ми додаємо елемент у початок черги та збільшуємо змінну front на одиницю лише для видалення елемента з черги. Якщо передня і задня позиції рівні і жодні компоненти не можуть бути видалені, отже, ми можемо сказати, що черга порожня.
Нижче наведено екземпляр черги, написаної мовою C, яка використовує масив:
Мова програмування C:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Вихід коду буде таким:
Вихід:
10 20 30 Queue is empty-1
Пояснення:
- Спочатку ми ставимо в чергу три елементи 10, 20 і 30.
- Потім ми знімаємо з черги та друкуємо передній елемент черги, який дорівнює 10.
- Далі ми знімаємо з черги та знову друкуємо передній елемент черги, тобто 20.
- Потім ми знімаємо з черги та знову друкуємо передній елемент черги, який дорівнює 30.
- Нарешті, ми створюємо вилучення з порожньої черги, яка виводить «Черга порожня» та повертає -1.
Використання пов’язаного списку:
Іншим альтернативним підходом до побудови черги на мові програмування C є використання зв’язаного списку. Кожен із вузлів у черзі виражається за допомогою цього методу вузлом, який містить значення елемента та вказівник на наступний вузол у черзі. Щоб відстежувати перший і останній вузли в черзі, відповідно, використовуються передній і задній покажчики.
Ми встановлюємо новий вузол із значенням елемента та встановлюємо його наступний покажчик на NULL, щоб додати елемент до черги. Для нового вузла ми встановлюємо передній і задній покажчики, якщо черга порожня. Якщо ні, ми оновлюємо задній покажчик і встановлюємо наступний покажчик старого заднього вузла, щоб вказувати на новий вузол.
Під час видалення вузла з черги спочатку видаляється попередній вузол, потім передній вказівник оновлюється до наступного вузла в черзі, і, нарешті, звільняється пам’ять, яку займав видалений вузол. Якщо після видалення передній покажчик дорівнює NULL, черга порожня.
Ось приклад черги, реалізованої в C за допомогою пов’язаного списку:
Мова програмування C:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Вихід коду буде таким:
git rebase
Вихід:
10 20 30 Queue is empty-1
Пояснення:
- Спочатку ми ставимо в чергу три елементи 10, 20 і 30.
- Потім ми знімаємо з черги та друкуємо передній елемент черги, який дорівнює 10.
- Далі ми знімаємо з черги та знову друкуємо передній елемент черги, тобто 20.
- Потім ми знімаємо з черги та знову друкуємо передній елемент черги, який дорівнює 30.
- Нарешті, ми намагаємося вийти з порожньої черги, яка друкує повідомлення «Черга порожня» та повертає -1.
Переваги:
- Черги особливо корисні для реалізації алгоритмів, які вимагають обробки елементів у точній послідовності, наприклад пошуку в ширину та планування завдань.
- Оскільки операції з чергами мають O(1) часову складність, їх можна виконувати швидко навіть у величезних чергах.
- Черги особливо гнучкі, оскільки їх можна просто реалізувати за допомогою масиву або зв’язаного списку.
Недоліки:
- Черга, на відміну від стека, не може бути створена за допомогою одного покажчика, що робить реалізацію черги дещо складнішою.
- Якщо чергу створено як масив, вона може незабаром заповнитися, якщо додати занадто багато елементів, що призведе до проблем із продуктивністю або, можливо, до збою.
- При використанні зв’язаного списку для реалізації черги накладні витрати пам’яті кожного вузла можуть бути значними, особливо для невеликих елементів.
Висновок:
Програми, які використовують черги, важливу структуру даних, включають операційні системи, мережі та ігри, щоб назвати лише деякі. Вони ідеально підходять для алгоритмів, які повинні обробляти елементи в певному порядку, оскільки їх легко створити за допомогою масиву або зв’язаного списку. Однак черги мають недоліки, які необхідно враховувати при виборі структури даних для конкретного додатка, такі як споживання пам’яті та складність реалізації.