Структура данных: очередь

Очередь — структура данных, которая, как и стек, имеет ограничения, по добавлению и удалению элементов. Чтобы понять очереди, представьте  очередь в  магазин: человек в начале очереди (тот, кто пришел первый) будет обслуживаться первым, вновь пришедшие люди будут добавляться в конец очереди. Таким образом, первый человек в очереди обслуживается первым, последний в очереди, обслуживается последним.Сокращенно очереди обозначаются как: FIFO — First In, First Out (первым пришел, первым ушел).

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

Немного терминологии:

• enqueue — добавление элемента в очередь;
• dequeue — удаления элемента из очереди.

Хотя концепция очереди может быть простой, в программировании очередь не так проста, как стек. Давайте вернемся к примеру с очередью в магазин. Скажем, один человек покидает очередь. Тогда что? Все в очереди должны пройти вперед, верно? Теперь, представьте себе, что только один человек может двигаться одновременно. Таким образом, второй человек делает шаг вперед, чтобы заполнить место, оставленное от первого лица, а затем третьим лицом делается шаг вперед, чтобы заполнить место, оставленное после второго человека, и так далее. Теперь представьте, что никто не может уйти или быть добавленным в очередь, пока все не шагнул вперед. Как вы уже поняли, очередь будет двигаться очень медленно. Конечно, не трудно  запрограммировать очередь, и она будет работать, но очень не просто сделать очередь, которая бы работала очень быстро!

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

Медлительность предыдущего метода заключается в том, что чем больше элементов в очереди, тем больше времени занимает перемещение. Есть еще один метод, не смещая элементы в очереди, выполняются функции постановки и удаления элементов из очереди. Представьте себе, снова, очередь в магазин. Представим, что не очередь движется к продавцу, а продавец движется к очереди, таким образом позиция начала очереди постоянно изменяется, стремится к концу очереди. Таким образом люди, которые стоят в очереди не делают шаг вперед или назад, что экономит время.

К сожалению, этот метод является гораздо более сложной задачей, чем очередь из массива. Вместо того, чтобы отслеживать только  «конец» очереди, мы также должны следить за началом очереди. Все это еще более усложняется, когда мы понимаем, что после того, как в очередь добавляется  и извлекается элемент, очередь будет нужно обернуть вокруг конца массива. Подумайте об очереди в магазин. Пока люди входят и выходят, очередь движется все дальше и дальше назад, и в конце концов очередь окружит магазин и в конечном итоге вернется на прежнее место.

Лучший способ понять как организована работа очереди — это разобраться в исходном коде. Наконец-то у меня появилось время, написал шаблон класса для структуры данных Очередь. Шаблон поместил в отдельный заголовочный файл, так это приемлемый способ утилизации кода. Как я уже говорил ранее, интерфейс шаблонов классов нельзя помещать в файл без реализации класса. Это связано с особенностью шаблонов классов в С++, поэтому просто следуем этому простом правилу. Кстати говоря, этот класс реализован по второму методу, более сложному. Смотрим код ниже:

#ifndef QUEUE_H
#define QUEUE_H

#include <cassert>

template<typename T>
class Queue
{
private:
    T *queuePtr;     // указатель на очередь
    const int size;  // максимальное количество элементов в очереди
    int begin,       // начало очереди
        end;         // конец очереди
    int elemCT;      // счетчик элементов
public:
    Queue(int =10);          // конструктор по умолчанию
    Queue(const Queue<T> &); // конструктор копирования
    ~Queue();                // деструктор

    void enqueue(const T &); // добавить элемент в очередь
    T dequeue(); // удалить элемент из очереди
    void printQueue();
};

// реализация методов шаблона класса Queue

// конструктор по умолчанию
template<typename T>
Queue<T>::Queue(int sizeQueue) :
    size(sizeQueue), // инициализация константы
    begin(0), end(0), elemCT(0)
{
    // дополнительная позици поможет нам различать конец и начало очереди
    queuePtr = new T[size + 1];
}

// конструктор копии
template<typename T>
Queue<T>::Queue(const Queue &otherQueue) :
    size(otherQueue.size) , begin(otherQueue.begin),
    end(otherQueue.end), elemCT(otherQueue.elemCT),
    queuePtr(new T[size + 1])
{
    for (int ix = 0; ix < size; ix++)
        queuePtr[ix] = otherQueue.queuePtr[ix]; // копируем очередь
}

// деструктор класса Queue
template<typename T>
Queue<T>::~Queue()
{
    delete [] queuePtr;
}

// функция добавления элемента в очередь
template<typename T>
void Queue<T>::enqueue(const T &newElem)
{
    // проверяем, ести ли свободное место в очереди
    assert( elemCT < size );

    // обратите внимание на то, что очередь начинает заполняться с 0 индекса
    queuePtr[end++] = newElem;

    elemCT++;

    // проверка кругового заполнения очереди
    if (end > size)
        end -= size + 1; // возвращаем end на начало очереди
}

// функция удаления элемента из очереди
template<typename T>
T Queue<T>::dequeue()
{
    // проверяем, есть ли в очереди элементы
    assert( elemCT > 0 );

    T returnValue = queuePtr[begin++];
    elemCT--;

    // проверка кругового заполнения очереди
    if (begin > size)
        begin -= size + 1; // возвращаем behin на начало очереди

    return returnValue;
}

template<typename T>
void Queue<T>::printQueue()
{
    cout << "Очередь: ";

    if (end == 0 && begin == 0)
        cout << " пустая\n";
    else
    {
        for (int ix = end; ix >= begin; ix--)
            cout << queuePtr[ix] << " ";
        cout << endl;
    }
}

#endif // QUEUE_H

Класс реализован с помощью шаблонов, а размер определяется динамически при инициализации (хотя по умолчанию составляет 10 элементов).

Обратите внимание на строку 34 или — 42, в этих строках выделяется память под очередь, так вот памяти выделяется на одно место больше. Это сделано для того, чтобы удобнее было организовывать круговую работу очереди, чтобы не получилось так, что очередь будет перемещаться по всей памяти.

Чтобы понять метод круговой реализации очереди, представьте массива в виде круга. Когда элемент удаляется из очереди, оставшиеся элементы не сдвигаются, вперед, к началу очереди. Вместо этого, начало очереди сдвигается к элементам. В конце концов, начало очереди, будет сдвинуто так далеко, что очередь будет выходить за пределы конца массива. Это где кругом приходит дюйма Когда очередь доходит до конца массива, она обтекает к началу массива.

Чтобы такого не происходило. нам поможет алгоритм круговой организации очереди. Когда очередь подходит к концу массива, она возвращается на его начало. Для тестирования класса я разработал программу-драйвер, код которой вы сможете увидеть ниже:

#include <iostream>

using namespace std;

#include "queue.h" // подключаем шаблон класса

int main ()
{
    Queue<char> myQueue(14); // объект класса очередь

    myQueue.printQueue(); // вывод очереди

    int ct = 1;
    char ch;

    // добавление элементов в очередь
    while (ct++ < 14)
    {
        cin >> ch;
        myQueue.enqueue(ch);
    }

    myQueue.printQueue(); // вывод очереди

    // удаление элемента из очереди
    myQueue.dequeue();
    myQueue.dequeue();
    myQueue.dequeue();

    myQueue.printQueue(); // вывод очереди

    cout << "\n\nСработал конструктор копирования:\n";
    Queue<char> newQueue(myQueue);

    newQueue.printQueue(); // вывод очереди

  return 0;
}

В этой программе последовательно запускаются различные методы класса и выполняется вывод содержимого очереди, для того, чтобы отследить изменения. Результат работы программы показан ниже:

Очередь:  пустая
STREET WORKOUT
Очередь:  T U O K R O W T E E R T S 
Очередь:  T U O K R O W T E E 

Сработал конструктор копирования:
Очередь:  T U O K R O W T E E