Очередь

очередь, сортировка, 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 могут использоваться только после сброса очереди, когда все элементы удалены.

Изменяя код для очереди, мы можем использовать пространство путем реализации модифицированной очереди, называемой циклической очередью.