Круговая Очередь

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

Циклическая очередь позволяет избежать потери места в обычной реализации очереди с использованием массивов.

DeQueue - удаление элемента из очереди;
FRONT и REAR - два указателя, используемые для отслеживания первого и последнего элементов в очереди.

Как вы можете видеть на изображении выше, после некоторого количества добавления в очередь и удаления из очереди ее размер был уменьшен.

Индексы 0 и 1 могут использоваться только после сброса очереди, когда все элементы сняты.

Как работает круговая очередь

Циклическая очередь работает по процессу циклического приращения, то есть когда мы пытаемся увеличить любую переменную и достигаем конца очереди, мы начинаем с начала очереди по модулю деления с размером очереди.

То есть:

if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)

Операции с очередями работают следующим образом:

• Два указателя, называемые FRONT и REAR, используются для отслеживания первого и последнего элементов в очереди.
• При инициализации очереди мы устанавливаем значение FRONT и REAR равным -1.
• При добавления элемента мы постепенно увеличиваем значение индекса REAR и помещаем новый элемент в положение, на которое указывает REAR.
• При снятии очереди с элемента мы возвращаем значение, на которое указывает FRONT, и постепенно увеличиваем индекс FRONT.
• Перед постановкой в очередь мы проверяем, заполнена ли очередь.
• Перед снятием очереди мы проверяем, пуста ли очередь.
• При инициализации первого элемента мы устанавливаем значение FRONT в 0.
• При удалении последнего элемента мы сбрасываем значения FRONT и REAR в -1.

Однако проверка на полную очередь имеет новый дополнительный пункт:

• Случай 1: FRONT = 0 && REAR == РАЗМЕР - 1
• Случай 2: ПЕРЕДНЯЯ = ЗАДНЯЯ + 1

Второй случай происходит, когда REAR начинается с 0 из-за кругового приращения, и когда его значение всего на 1 меньше значения FRONT, очередь заполнена.

Реализация циклической очереди на языке программирования

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

Реализация с использованием C-программирования

#include <stdio.h>
 
#define SIZE 5
 
int items[SIZE];
int front = -1, rear =-1;
 
int isFull()
{
    if( (front == rear + 1) || (front == 0 && rear == SIZE-1)) return 1;
    return 0;
}
 
int isEmpty()
{
    if(front == -1) return 1;
    return 0;
}
 
void enQueue(int element)
{
    if(isFull()) printf("\n Queue is full!! \n");
    else
    {
        if(front == -1) front = 0;
        rear = (rear + 1) % SIZE;
        items[rear] = element;
        printf("\n Inserted -> %d", element);
    }
}
 
 
int deQueue()
{
    int element;
    if(isEmpty()) {
        printf("\n Queue is empty !! \n");
        return(-1);
    } else {
        element = items[front];
        if (front == rear){
            front = -1;
            rear = -1;
        } /* В Q есть только один элемент, поэтому мы сбрасываем очередь после ее удаления. */
        else {
            front = (front + 1) % SIZE;
 
        }
        printf("\n Deleted element -> %d \n", element);
        return(element);
    }
}
 
 
 
 
void display()
{
    int i;
    if(isEmpty()) printf(" \n Empty Queue\n");
    else
    {
        printf("\n Front -> %d ",front);
        printf("\n Items -> ");
        for( i = front; i!=rear; i=(i+1)%SIZE) {
            printf("%d ",items[i]);
        }
        printf("%d ",items[i]);
        printf("\n Rear -> %d \n",rear);
    }
}
 
int main()
{
    // Ложь, потому что front = -1
    deQueue();
 
    enQueue(1);
    enQueue(2);
    enQueue(3);
    enQueue(4);
    enQueue(5);
 
    // Невозможно поставить в очередь, потому что front == 0 && rear == SIZE - 1
    enQueue(6);
 
    display();
    deQueue();
 
    display();
 
    enQueue(7);
    display();
 
    // Невозможно поставить в очередь, потому что front == rear + 1
    enQueue(8);
 
    return 0;
}

Когда вы запустите эту программу, получите следующее:

Inserted -> 1
  Inserted -> 2
  Inserted -> 3
  Inserted -> 4
  Inserted -> 5
  Queue is full!! 
 
  Front -> 0 
  Items -> 1 2 3 4 5 
  Rear -> 4 
 
  Deleted element -> 1 
 
  Front -> 1 
  Items -> 2 3 4 5 
  Rear -> 4 
 
  Inserted -> 7
  Front -> 1 
  Items -> 2 3 4 5 7 
  Rear -> 0 
 
  Queue is full!!

Реализация с использованием программирования на 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;
        }
        if(front == rear + 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 = (rear + 1) % SIZE;
            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=(front+1) % SIZE;
            }
            return(element);
        }
    }
 
    void display()
    {
        /* Функция для отображения статуса круговой очереди */
        int i;
        if(isEmpty()) {
            cout << endl << "Empty Queue" << endl;
        }
        else
        {
            cout << "Front -> " << front;
            cout << endl << "Items -> ";
            for(i=front; i!=rear;i=(i+1)%SIZE)
                cout << items[i];
            cout << items[i];
            cout << endl << "Rear -> " << rear;
        }
    }
 
};
 
 
int main()
{
    Queue q;
 
    // Ложь, потому что front = -1
    q.deQueue();
 
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);
 
    // Невозможно поставить в очередь, потому что front == 0 && rear == SIZE - 1
    q.enQueue(6);
 
 
    q.display();
 
    int elem = q.deQueue();
 
    if( elem != -1)
       cout << endl << "Deleted Element is " << elem;
 
    q.display();
 
    q.enQueue(7);
 
    q.display();
 
    // Невозможно поставить в очередь, потому что front == rear + 1
    q.enQueue(8);
 
    return 0;
}

Когда вы запустите эту программу, получите следующее:

Queue is empty
 
Inserted 1
 
Inserted 2
 
Inserted 3
 
Inserted 4
 
Inserted 5
 
Queue is full
Front -> 0
Items -> 12345
Rear -> 4
Deleted Element is 1
Front -> 1
Items -> 2345
Rear -> 4
Inserted 7
 
Front -> 1
Items -> 23457
Rear -> 0
Queue is full