Очередь

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

Очередь - это полезная структура данных в программировании. Представьте очередь билетов за пределами кинозала, где первый человек, входящий в очередь, является первым человеком, который получает билет.

Очередь следует правилу «первым пришел - первым обслужен» (First In First Out - FIFO) - элемент, который идет первым, - это элемент, который выходит первым.

Рассмотрим рисунок. Поскольку 1 помещена в очередь до 2, она так же уйдет первой из очереди. Это следует правилу FIFO.

С точки зрения программирования, помещение элемента в очередь (empty queue - пустая очередь) называется "enqueue" (постановка в очередь), а удаление элемента из очереди - "dequeue" (снятие очереди).

Мы можем реализовать очередь на любом языке программирования, таком как C, C ++, Java, Python или C #, почти с одинаковой спецификацией.

Технические характеристики очереди

Очередь - это объект или, более конкретно, абстрактная структура данных (ADT), которая позволяет выполнять следующие операции:

  • Enqueue: добавить элемент в конец очереди;
  • Dequeue: удалить элемент из начала очереди;
  • IsEmpty: проверить, пуста ли очередь;
  • IsFull: проверьте, заполнена ли очередь;
  • Peek: получить значение начала очереди, не удаляя его.
Как работает очередь

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

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

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

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

Реализация с использованием C-программирования
#include<stdio.h>
#define SIZE 5

void enQueue(int);
void deQueue();
void display();

int items[SIZE], front = -1, rear = -1;

int main()
{
    //deQueue невозможно в пустой очереди
    deQueue();

    //enQueue 5 elements
    enQueue(1);
    enQueue(2);
    enQueue(3);
    enQueue(4);
    enQueue(5);

    //6-й элемент не может быть добавлен в очередь, потому что очередь заполнена
    enQueue(6);

    display();

    //deQueue удаляет элемент, введенный первым, т.е. 1
    deQueue();

    //Теперь у нас всего 4 элемента
    display();

    return 0;

}

void enQueue(int value){
    if(rear == SIZE-1)
        printf("\nQueue is Full!!");
    else {
        if(front == -1)
            front = 0;
        rear++;
        items[rear] = value;
        printf("\nInserted -> %d", value);
    }
}

void deQueue(){
    if(front == -1)
        printf("\nQueue is Empty!!");
    else{
        printf("\nDeleted : %d", items[front]);
        front++;
        if(front > rear)
            front = rear = -1;
    }
}

void display(){
    if(rear == -1)
        printf("\nQueue is Empty!!!");
    else{
        int i;
        printf("\nQueue elements are:\n");
        for(i=front; i<=rear; i++)
            printf("%d\t",items[i]);
    }
}

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

Queue is Empty!!
Inserted -> 1
Inserted -> 2
Inserted -> 3
Inserted -> 4
Inserted -> 5
Queue is Full!!
Queue elements are:
1    2    3    4    5    
Deleted : 1
Queue elements are:
2    3    4    5
Реализация с использованием программирования на 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;
        }
        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++;
            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++;
            }
            cout << endl << "Deleted -> " << element << endl;
            return(element);
        }
    }

    void display()
    {
        /* Функция для отображения элементов очереди */
        int i;
        if(isEmpty()) {
            cout << endl << "Empty Queue" << endl;
        }
        else
        {
            cout << endl << "Front -> " << front;
            cout << endl << "Items -> ";
            for(i=front; i<=rear; i++)
                cout << items[i] << ""\t";
            cout << endl << "Rear -> " << rear << endl;
        }
    }

};


int main()
{
    Queue q;

    //deQueue невозможно в пустой очереди
    q.deQueue();

    //enQueue 5 элементов
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);

    //6-й элемент не может быть добавлен в очередь, потому что очередь заполнена
    q.enQueue(6);

    q.display();

    //deQueue удаляет элемент, введенный первым, т.е. 1
    q.deQueue();

    //Теперь у нас всего 4 элемента
    q.display();

    return 0;
}

После запуска мы получим:

Queue is empty

Inserted 1

Inserted 2

Inserted 3

Inserted 4

Inserted 5
Queue is full
Front -> 0
Items -> 1    2    3    4    5    
Rear -> 4

Deleted -> 1

Front -> 1
Items -> 2    3    4    5    
Rear -> 4
Ограничение этой реализации

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

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

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

Virtual hosting with 10 percent discount
Virtual hosting with 10 percent discount
EVILEG offers reliable hosting with a 10% discount for virtual hosting and 5% for VPS

Comments

Only authorized users can post comments.
Please, Log in or Sign up
July 22, 2019, 7:26 a.m.
Pavel K.

Qt - Test 001. Signals and slots

  • Result:68points,
  • Rating points-1
o
July 22, 2019, 6:26 a.m.
oksik193

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

  • Result:80points,
  • Rating points4
VD
July 21, 2019, 11:33 p.m.
Vlad Dolgov

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

  • Result:40points,
  • Rating points-8
Last comments
July 21, 2019, 6:03 a.m.
Evgenij Legotskoj

да, наверное, 32-х разрядную поддержку уже давно поа было выкинуть. К слову, у вас много проектов под Android? Часто много где вижу вопросы о том, пишет ли кто-то вообще на Qt под мобильные сист…
July 20, 2019, 2:41 p.m.
Andrej Jankovich

Очень полезная информация, увы уже выкинул поддержку 32 битных бедняг.
July 20, 2019, 9:31 a.m.
Mihailll

Вот так qDebug()<<"position:"<<event->scenePos();
July 20, 2019, 8:49 a.m.
Mihailll

Добрый день. Как можно узнать координату на графической сцене при отпускании клавиши мыши?
Now discuss on the forum
July 22, 2019, 8:41 a.m.
BlinCT

Вот только что нашел в инете, у человека такая же ошибка. Вроде бы таже самая проблема https://stackoverflow.com/questions/37633709/how-to-create-qtquick-window-outside-the-main-thread…
July 22, 2019, 3:58 a.m.
Evgenij Legotskoj

Добрый день! Нужен совет сообщества по разработке функционала проверки орфографии. Одна из идей - добавить проверку орфографии при наборе текста статей. Полагаю, что наиболее аде…
July 22, 2019, 3:01 a.m.
Evgenij Legotskoj

Возможно, если при сохранении файла установить права доступа на файл. Что-то такое должно быть у QFile
July 22, 2019, 3:01 a.m.
Evgenij Legotskoj

Я отрисовываю квадрат в его локальной системе координат от верхнего левого угла (-30,-30) до его правого нижнего угла (30,30). Поэтому мне нужно указать размеры объекта через boundingRect()…
July 20, 2019, 11:04 a.m.
Mihailll

Так и с ресурсами работает QImage image(":/Images/Images/1.png");
Looking for a Job?
5,000.00 руб. - 15,000.00 руб.
Дизайнер
Moskovskiy, Moscow, Russia
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