Черга – це корисна структура даних у програмуванні. Уявіть чергу квитків поза кінозалом, де перша людина, що входить у чергу, є першою людиною, яка отримує квиток.
Черга слідує правилу «першим прийшов – першим обслужений» (First In First Out – FIFO) – елемент, який йде першим, – це елемент, який виходить першим.
Розглянемо рисунок. Оскільки 1 поміщена в чергу до 2, вона так само піде першою із черги. Це слідує правилу FIFO.
З погляду програмування, розміщення елемента у чергу (empty queue - порожня черга) називається "enqueue" (постановка у чергу), а видалення елемента з черги - "dequeue" (зняття черги).
Ми можемо реалізувати чергу будь-якою мовою програмування, такою як C, C++, Java, Python або C#, майже з однаковою специфікацією.
Технічні характеристики черги
Черга - це об'єкт або, конкретніше, абстрактна структура даних (ADT), яка дозволяє виконувати наступні операції:
- Enqueue: додати елемент до кінця черги;
- Dequeue: видалити елемент із початку черги;
- IsEmpty: перевірити, чи порожня черга;
- IsFull: перевірте, чи заповнена черга;
- Peek: отримати значення початку черги, не видаляючи його.
Як працює черга
Операції з чергами працюють таким чином:
- Два вказівники, звані FRONT та REAR, використовуються для відстеження першого та останнього елементів у черзі.
- При ініціалізації черги ми встановлюємо значення FRONT та REAR рівним -1.
- При додаванні елемента ми збільшуємо значення індексу REAR і поміщаємо новий елемент у положення, яке вказує REAR.
- При видаленні елемента з черги ми повертаємо значення, яке вказує FRONT, і збільшуємо індекс FRONT.
- Перед постановкою на чергу ми перевіряємо, чи заповнена черга.
- Перед зняттям черги ми перевіряємо, чи порожня черга.
- При ініціалізації першого елемента ми встановлюємо значення FRONT 0.
- При видаленні останнього елемента ми скидаємо значення FRONT і REAR -1.
Реалізація черги мовою програмування
Найбільш поширена реалізація черги використовує масиви, але також черга може бути з використанням списків.
Реалізація з використанням C-програмування
#include<stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;
int main()
{
//deQueue невозможно в пустой очереди
deQueue();
//enQueue 5 elements
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
//6-й элемент не может быть добавлен в очередь, потому что очередь заполнена
enQueue(6);
display();
//deQueue удаляет элемент, введенный первым, т.е. 1
deQueue();
//Теперь у нас всего 4 элемента
display();
return 0;
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!");
else {
if(front == -1)
front = 0;
rear++;
items[rear] = value;
printf("\nInserted -> %d", value);
}
}
void deQueue(){
if(front == -1)
printf("\nQueue is Empty!!");
else{
printf("\nDeleted : %d", items[front]);
front++;
if(front > rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",items[i]);
}
}
Коли ви запускаєте цю програму, ви отримуєте таке:
Queue is Empty!! Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Queue is Full!! Queue elements are: 1 2 3 4 5 Deleted : 1 Queue elements are: 2 3 4 5
Реалізація з використанням програмування на C++
#include <iostream>
#define SIZE 5
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue(){
front = -1;
rear = -1;
}
bool isFull(){
if(front == 0 && rear == SIZE - 1){
return true;
}
return false;
}
bool isEmpty(){
if(front == -1) return true;
else return false;
}
void enQueue(int element){
if(isFull()){
cout << "Queue is full";
} else {
if(front == -1) front = 0;
rear++;
items[rear] = element;
cout << endl << "Inserted " << element << endl;
}
}
int deQueue(){
int element;
if(isEmpty()){
cout << "Queue is empty" << endl;
return(-1);
} else {
element = items[front];
if(front >= rear){
front = -1;
rear = -1;
} /* В Q есть только один элемент, поэтому мы удаляем очередь после удаления. */
else {
front++;
}
cout << endl << "Deleted -> " << element << endl;
return(element);
}
}
void display()
{
/* Функция для отображения элементов очереди */
int i;
if(isEmpty()) {
cout << endl << "Empty Queue" << endl;
}
else
{
cout << endl << "Front -> " << front;
cout << endl << "Items -> ";
for(i=front; i<=rear; i++)
cout << items[i] << ""\t";
cout << endl << "Rear -> " << rear << endl;
}
}
};
int main()
{
Queue q;
//deQueue невозможно в пустой очереди
q.deQueue();
//enQueue 5 элементов
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
//6-й элемент не может быть добавлен в очередь, потому что очередь заполнена
q.enQueue(6);
q.display();
//deQueue удаляет элемент, введенный первым, т.е. 1
q.deQueue();
//Теперь у нас всего 4 элемента
q.display();
return 0;
}
Після запуску ми отримаємо:
Queue is empty Inserted 1 Inserted 2 Inserted 3 Inserted 4 Inserted 5 Queue is full Front -> 0 Items -> 1 2 3 4 5 Rear -> 4 Deleted -> 1 Front -> 1 Items -> 2 3 4 5 Rear -> 4
Обмеження цієї реалізації
Як ви можете бачити на зображенні нижче, через деякий час після додавання в чергу та видалення з черги розмір черги був зменшений.
Індекси 0 та 1 можуть використовуватися тільки після скидання черги, коли всі елементи видалені.
Змінюючи код для черги, ми можемо використовувати простір шляхом реалізації модифікованої черги, яка називається циклічною чергою.
