Privacy policyContactsAbout siteOpinionsGitHubDonate
© EVILEG 2015-2018
Recommend hosting
TIMEWEB

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

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

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

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
AA
April 17, 2019, 7:40 p.m.
Anton Ablin

Qt - Test 001. Signals and slots

  • Result:73points,
  • Rating points1
E
April 17, 2019, 6:16 p.m.
Evgeny

Qt - Test 001. Signals and slots

  • Result:100points,
  • Rating points10
E
April 17, 2019, 6:14 p.m.
Evgeny

Qt - Test 001. Signals and slots

  • Result:78points,
  • Rating points2
Last comments
U
April 18, 2019, 3:37 p.m.
Unreal_man

А как иконку в хедер задать?
u
April 18, 2019, 2:15 a.m.
uaa

доброго времени,большое спасибо за пример для начинающего)при адаптации к своему проекту столкнулся с таким ньансом:в vepolyline.h в 47 строке нужна инициализация по умолчанию: int m_pointF...
E
April 11, 2019, 12:49 p.m.
Evgeny

Спасибо за ответ) У меня компоновщик на нее ругался просто. Оказалось, просто забыл Q_OBJECT в начале класса указать.
April 11, 2019, 12:29 p.m.
Евгений Легоцкой

Добрый день. Вы имели ввиду реализацию? Для сигналов в Qt реализация не пишется, это всё генерируется в moc файлах под капотом Qt.
E
April 11, 2019, 12:15 p.m.
Evgeny

Здравствуйте. А где описание функции signal1()?
Now discuss on the forum
R
April 19, 2019, 9:55 a.m.
RED_Spider

мені важко це зараз навіть перевірити, тому що знайшов коміт, це ще було в 2016 році, і цей код не буде працювати коректно зараз, єдине скажу що це були QThread
i
April 17, 2019, 3:03 p.m.
ilya.guzikov

BlinCT, на стороне ++ это делать необходимо так как в qml при использовании функции append происходит перерисовка всех точек лини(как я понимаю) и из-за этого при использовании больших массиво...
April 10, 2019, 11:20 a.m.
Алексей Внуков

может тоже кому надо будет - QML не принимает QVector<QVector<int>> , при попытке вывести полученый вектор QML показывает что это QVariant(QVector<QVector<int> ...
SN
April 10, 2019, 9:36 a.m.
Stanislav Nykytiuk

Как реализовать такое меню, что бы нажмаешь меню подменю и выбор позиции? Данные меню и подменю в базе SQL.
Join us in social networks

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