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

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

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

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
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.

Comments

Only authorized users can post comments.
Please, Log in or Sign up
Donate

Hello, Dear Users of EVILEG!!!

If the site helped you, then support the development of the site financially, please.

You can do it by following ways:

Thank you, Evgenii Legotckoi

SB
Dec. 5, 2019, 8:01 a.m.
Sergej Bederin

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

  • Result:60points,
  • Rating points-1
AS
Dec. 4, 2019, 6:39 a.m.
Artur Salmin

C++ - Test 005. Structures and Classes

  • Result:33points,
  • Rating points-10
ST
Dec. 2, 2019, 4:05 p.m.
Sergej Timchenko

Qt - Test 001. Signals and slots

  • Result:68points,
  • Rating points-1
Last comments
Dec. 5, 2019, 4:15 p.m.
Evgenij Legotskoj

В этом слоте ваам нужно будет правильно смаппить координату. У QGraphicsView есть методы mapToScene, mapFromScene. Попробуйте использовать их.
LP
Dec. 5, 2019, 8:30 a.m.
Leonid Pivovarov

А без переопределения qgraphicsScene это сделать возможно? Есть же коорината нажатия кнопки мыши slotCustomMenuRequested(QPoint)
Dec. 5, 2019, 8:11 a.m.
Mihailll

//qDebug()<<"position:"<<event->pos(); //qDebug()<<"position:"<<event->screenPos(); qDebug()<<"position:"<<event->scenePos();
LP
Dec. 5, 2019, 8:09 a.m.
Leonid Pivovarov

Подскажите пожалуйста, К graphicsView я подключил обработку контекстного меню: сonnect(ui->graphicsView, SIGNAL(customContextMenuRequested(QPoint)), this, SLOT(slotCustomMenuRequest…
Dec. 4, 2019, 3:49 p.m.
Evgenij Legotskoj

resources_big - это флаг для сборки c++ приложения. Если Nuitka не предоставляет какой-либо функционал для прикручивания конфигурационных директив типа CONFIG при компиляции, то сомнева…
Now discuss on the forum
Dec. 5, 2019, 4:12 p.m.
Evgenij Legotskoj

Это уже кастомная стилизация. Придётся отключать обрамление и самостоятельно реализовывать ресайз окна, его перемещение, стиль и т.д. Вот статья, как отключить обрамление окна - QML …
Dec. 5, 2019, 4:27 a.m.
qml_puthon_user

Вот код, вдруг, кому поможет. Код основной формы: import QtQuick 2.12import QtQuick.Controls 2.12import QtQuick.Layouts 1.3import "./Components/Panels" as PanelsApplicationWindow{…
Dec. 5, 2019, 2:50 a.m.
Evgenij Legotskoj

Создавайте новые темы, чтобы не было всё в куче.
Dec. 4, 2019, 10:07 p.m.
qml_puthon_user

Спасибо за помощь! :) Я попытаю надежды в ожидании QtQuick3D от Riverbank'a. :)
V
Dec. 4, 2019, 7:02 a.m.
Vitali

Со временем распаковки соласен - для слабых ноутов это проблема и именно Nuitka мог бы здесь помочь, если бы заработало. А QtlFW - это уже фреймфорк для создания инсталятора из имеющихся па…
EVILEG
About
Services
© EVILEG 2015-2019
Recommend hosting TIMEWEB