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

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

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

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
10% refund of hotel reservation amount on Booking
10% refund of hotel reservation amount on Booking
We offer a link with a 10% return on the amount of the order when booking a hotel through Booking

Comments

Only authorized users can post comments.
Please, Log in or Sign up
TT
June 13, 2019, 7:01 p.m.
Taimoor Tanweer

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
TT
June 13, 2019, 6:51 p.m.
Taimoor Tanweer

C++ - Test 002. Constants

  • Result:75points,
  • Rating points2
ВМ
June 13, 2019, 12:30 p.m.
Ваня Мороз

C++ - Test 001. The first program and data types

  • Result:100points,
  • Rating points10
Last comments
МБ
June 20, 2019, 6:23 p.m.
Михаил Булатов

А если мне нужно сделать конект из дочернего qml?Сигнал работает только из main.qml
i
June 17, 2019, 6:10 a.m.
ingenfly

Только по осям xAxis2, уAxis2 значения начинаются с 0. Почему-то xAxis2 и xAxis не синхронизированы по данным. Ну и QCustomPlot последний.
June 16, 2019, 8:21 p.m.
Евгений Легоцкой

Добрый день. Ну точно также добавляете ту же самую информацию на ось xAxis2, только добавляете другое форматирование customPlot->xAxis2->setDateTimeFormat("hh:mm"); если я ...
EF
June 14, 2019, 1:56 p.m.
Egor Fomin

Спасибо за ваш ответ, у меня получилось реализовать это. Тем не менее появилась другая проблема, поэтому опять надеюсь на вашу помощь. Скажем, я уже выставил точки и они соеденены. Когда я нач...
d
June 13, 2019, 2:47 p.m.
damix

Можно классу, который описывает точку, добавить сигнал, который подавать (emit), когда точка перемещается (переопределить mouseMoveEvent или mouseReleaseEvent). Так вот эти сигналы у каждой из...
Now discuss on the forum
June 20, 2019, 9:30 a.m.
IscanderChe

Вернулся к этой задачке только-только, поэтому и не ответил ничего раньше.Как переопределить mouseReleaseEvent(QMouseEvent* event) у QTableView, если QTableView задан в ui? Или задавать QTabl...
I
June 19, 2019, 1:41 p.m.
Intruder

Всем добрый день. При разборе XML файла наткнулся на тег вот такого плана: <TagName attribute1="value1" attribute2="value2" /> При попытке проверить на наличие такого элеме...
June 19, 2019, 12:55 p.m.
Михаиллл

Скажите пожалуйста, как его в таком случае перемещать и удалять?
June 18, 2019, 7:50 p.m.
Дмитрий

Большое спасибо! SDK заработал.К сожалению удалось продвинутся только на один шаг. При сборке чистого проекта NDK выдаёт следующие ошибки C:\Android\ndk-bundle/toolchains/arm-linux-andr...
June 18, 2019, 4:59 p.m.
Михаиллл

Добрый день.В этом учебнике представлен код INSTALLED_APPS = ( ... 'rest_framework', 'snippets.apps.SnippetsConfig',) На строчке 'snippets.apps.SnippetsConf...
Looking for a Job?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

For registered users on the site there is a minimum amount of advertising

EVILEG
About
Services
Join us
© EVILEG 2015-2019
Recommend hosting TIMEWEB