Очередь

очередь, сортировка, 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 могут использоваться только после сброса очереди, когда все элементы удалены.

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

Возврат 10% от суммы заказа отеля на Booking
Возврат 10% от суммы заказа отеля на Booking
Предлагаем ссылку с 10% возвратом от суммы заказа при бронировании отеля через Booking

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
s
26 мая 2019 г. 14:33
simpleunderground

Qt - Тест 001. Сигналы и слоты

  • Результат:31баллов,
  • Очки рейтинга-10
НД
25 мая 2019 г. 23:25
Николай Демиденко

C++ - Тест 003. Условия и циклы

  • Результат:64баллов,
  • Очки рейтинга-1
НД
25 мая 2019 г. 23:19
Николай Демиденко

C++ - Тест 002. Константы

  • Результат:50баллов,
  • Очки рейтинга-4
Последние комментарии
21 мая 2019 г. 20:10
Дмитрий

Приветствую! Я думаю дойдёт и до этого, но пока изучать его у меня нет желания.
20 мая 2019 г. 19:20
Евгений Легоцкой

Добрый день! Вы не думали разместить репозиторий проекта на GitHub?
P.
18 мая 2019 г. 14:03
PELMYACH .

Спасибо большое! Вскоре буду разбираться!
18 мая 2019 г. 9:13
Евгений Легоцкой

Добрый день! Отнимать значение общего счётчика можно в деструкторе класса кнопки QDynamicButton::~QDynamicButton(){ ResID--;} При этом я бы ещё переустанавливал значения вс...
P.
14 мая 2019 г. 22:33
PELMYACH .

Здравствуйте!А не подскажите, как можно при удалении какой либо кнопки, у щётчика отнять значение?Дабы например четвёртой кнопке соответствовал ID 4, а не 5 скажем
Сейчас обсуждают на форуме
26 мая 2019 г. 6:49
Михаиллл

Скачал dll от сюда и заработало
24 мая 2019 г. 6:48
Евгений Легоцкой

Если там будут только перечисления внутри namespace, то жа, достаточно будет заголовочного файла
24 мая 2019 г. 6:28
Андрей Янкович

работает любой http сервер, и можно использовать обсалютно любой портпример <RemoteRepositories> <Repository> <Url>http://178.124.160.6:3030/A/B&l...;
23 мая 2019 г. 10:42
Михаиллл

Спасибо, помогло.
23 мая 2019 г. 6:31
Евгений Легоцкой

Для задач и граф-то не нужен. Достаточно будет таблицы в локальной базе данных SQLite, в которой указывается задача, время и т.д. В этом разделе есть примеры по работа с базой д...

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

EVILEG
О нас
Услуги
Присоединяйтесь к нам
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB