Черга

очередь, сортировка, Queue, алгоритмы

Черга – це корисна структура даних у програмуванні. Уявіть чергу квитків поза кінозалом, де перша людина, що входить у чергу, є першою людиною, яка отримує квиток.

Черга слідує правилу «першим прийшов – першим обслужений» (First In First Out – FIFO) – елемент, який йде першим, – це елемент, який виходить першим.

Розглянемо рисунок. Оскільки 1 поміщена в чергу до 2, вона так само піде першою із черги. Це слідує правилу FIFO.

З погляду програмування, розміщення елемента у чергу (empty queue - порожня черга) називається "enqueue" (постановка у чергу), а видалення елемента з черги - "dequeue" (зняття черги).

Ми можемо реалізувати чергу будь-якою мовою програмування, такою як C, C++, Java, Python або C#, майже з однаковою специфікацією.

Технічні характеристики черги

Черга - це об'єкт або, конкретніше, абстрактна структура даних (ADT), яка дозволяє виконувати наступні операції:

• Enqueue: додати елемент до кінця черги;
• Dequeue: видалити елемент із початку черги;
• IsEmpty: перевірити, чи порожня черга;
• IsFull: перевірте, чи заповнена черга;
• Peek: отримати значення початку черги, не видаляючи його.

Як працює черга

Операції з чергами працюють таким чином:

1. Два вказівники, звані FRONT та REAR, використовуються для відстеження першого та останнього елементів у черзі.
2. При ініціалізації черги ми встановлюємо значення FRONT та REAR рівним -1.
3. При додаванні елемента ми збільшуємо значення індексу REAR і поміщаємо новий елемент у положення, яке вказує REAR.
4. При видаленні елемента з черги ми повертаємо значення, яке вказує FRONT, і збільшуємо індекс FRONT.
5. Перед постановкою на чергу ми перевіряємо, чи заповнена черга.
6. Перед зняттям черги ми перевіряємо, чи порожня черга.
7. При ініціалізації першого елемента ми встановлюємо значення FRONT 0.
8. При видаленні останнього елемента ми скидаємо значення 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 можуть використовуватися тільки після скидання черги, коли всі елементи видалені.

Змінюючи код для черги, ми можемо використовувати простір шляхом реалізації модифікованої черги, яка називається циклічною чергою.