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

Content

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

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
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
June 6, 2020, 12:20 a.m.
Aleksej

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:60points,
  • Rating points-1
June 6, 2020, 12:15 a.m.
Aleksej

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

  • Result:53points,
  • Rating points-4
V
June 5, 2020, 5:47 p.m.
Vladzo

C++ - Test 005. Structures and Classes

  • Result:83points,
  • Rating points4
Last comments
June 5, 2020, 11:52 a.m.
progammist

Распознавание изображений на Python с помощью TensorFlow и Keras

Огромное спасибо за метериал, по-больше бы подобных статей (с подробным описанием работы и примерами применения) на тему современных технологий. Вопрос поразмышлять. На текущий момент реал…
June 5, 2020, 2:39 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

По-моему, смысла в этом нет особого. Если делегат будет игнорировать настройки таблицы, то это приведёт ещё к большему непониманию, что вообще происходит, для программиста, который после вас буд…
June 5, 2020, 2:34 a.m.
IscanderChe

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Сижу, размышляю: можно ли переписать делегата так, чтобы независимо от настроек строк выделялись строки?
June 5, 2020, 2:31 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Понятно. Я не обратил внимания на то, что там было в старом коде по настройкам строк :)
Now discuss on the forum
s
June 6, 2020, 2:54 a.m.
shuric

Qt/C++ Определение положения курсора над действие(кнопкой) в QToolBar

Доброго дня. Возник вопрос - как можно определить что курсор находится над определенным действием(кнопкой) в qtoolbar ? mainwindow.cpp MainWindow::MainWi…
s
June 6, 2020, 1:45 a.m.
shuric

Qt/C++ особенности QProxyStyle

Да, Вы правы. Код был скопирован с сайта (уже не помню с какого), но решил пойти по пути более легком. Пришлось переписать - кому интересно: использовал stackedWidget для пе…
June 6, 2020, 12:08 a.m.
Aleksej

Посоветуйте новичку (базы данных и Qt, что учить)

Блин, а я недавно купил Шлее Qt 5.10 :( С детства хотел стать программистом, баловался Паскалем, писал простенькие программки на Delphi, создавал движок на php, изучал C (забросил и перешел на п…
June 5, 2020, 2:09 p.m.
IscanderChe

QPlainTextEdit настройка цвета фона

Вечер добрый. Пытаюсь настроить цвет фона QPlainTextEdit следующим образом: CodeEditor::CodeEditor(QWidget *parent) : QPlainTextEdit(parent){ ... QPalette::ColorRole role = bac…
June 5, 2020, 7:13 a.m.
IscanderChe

Фильтр для QtableView sql

Добрый день. Для такой фильтрации необходимо использовать QSortFilterProxyModel. В оффдоках есть хороший пример.
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB