C++ Queue example

#include "pch.h"
#include <iostream>

using namespace std;

/*------------------------------------------------------------------- СТЭК ---------------------------------------------------------------*/

/*
Тип данных для очереди целых чисел Queue (первый пришёл - первый ушёл).
Тип данных очереди основывается на другом типе данных - Линейный список LinearList:
@data - значение целого числа в узле
@next - указатель на следующий узел (nullptr, если это последний элемент списка)
*/
struct LinearList
{
    int data;                           // поле данных
    LinearList* next;                   // указатель на следующий элемент списка
};

// но сама очередь по сути - пара указателей на первый и последний элементы списка.

struct Queue
{
    LinearList* first;                  // указатель на первый элемент очереди
    LinearList* last;                   // указатель на последний элемент очереди
};


/*
Операции над очередью Queue -----------------------
В линейном списке мы использовали для доступа к оригинальному списку двойной указатель LinearList**, т.е. указатель на указатель на наш тип данных - вроде как (LinearList*)*,
это было необходимо для того, чтобы в наших функциях можно было менять исходный список.
Здесь используем альтернативный подход: будем прямо в функции явно ждать адрес передаваемого указателя (Queue* &que)
Теперь чтобы менять исходные данные, нам можно передавать их в функцию как обычную переменную, что упрощает читабельность кода.
*/

// инициализация очереди
void initQueue(Queue* &que)
{
    que = new Queue;                            // выделение памяти
    que->first = nullptr;                       // ...и инициализация конца и начала очереди que нулями (пустыми указателями NULL)
    que->last = nullptr;
}

// проверка очереди на пустоту (очередь инициализирована, т.е. память выделена, а начало и конец очереди - пустые)
bool isEmptyQueue(Queue* que)
{
    return ((que != nullptr) && (que->first == nullptr) && (que->last == nullptr));
}

// постановка в очередь нового элемента списка со значением value
void enQueue(Queue* &que, const int value)
{
    if (isEmptyQueue(que))                      // если очередь пуста
    {
        que->first = new LinearList;            // создаем новый элемент списка в качестве первого элемента очереди (que->first)
        que->first->data = value;               // и заполняем его данными
        que->first->next = nullptr;
        que->last = que->first;                 // приравнивам последний элемент очереди к свежесозданному первому
    }
    else                                        // ...если же в очереди что-то есть
    {
        LinearList* e = new LinearList;         // созадем новый элемент списка e
        e->data = value;                        // заполняем его данными
        e->next = nullptr;
        que->last->next = e;                    // обновляем последний элемент очереди (добавляем новый элемент в конец)
        que->last = e;                          // смещаем указатель конца очереди que->last на новый элемент
    }
}

// извлечение из очереди целочисленного значения
int deQueue(Queue* &que)
{
    //cout << que->first << " [" << que->first->data << "]" << endl;
    LinearList* tmp = que->first;               // создаем временную переменную для хранения указателя на извлекаемый элемент списка (для последующего освобождения памяти)
    int result = que->first->data;              // переменная для извлечения значения первого элемента очереди

    if(que->first != que->last)                 // если в очереди осталось больше одного элемента
    {
        que->first = que->first->next;          // смещаем указатель на первый элемент очереди дальше по списку
    }
    else                                        //...если остался один элемент
    {
        que->first = que->first->next;          // сдвигаем указатель на первый элемент дальше (на NULL)
        que->last = que->first;                 // ...и приравниваем к нему указатель на последний элемент
    }
    delete tmp;                                 // чистим память, возвращаем результат извлечения
    return result;
}

// Последовательный вывод содержимого линейного списка root (здесь нам не надо менять исходный список, поэтому можно обойтись простым указателем на первый элемент списка LinearList*)
void printLinearList(LinearList* root)
{
    LinearList* e = root;                       // создаем временную переменную e для движения по списку от положения root
    while (e != nullptr)                        // пока не достигнут конец списка, т.е. пока временная переменная e не приняла значение равное пустому указателю nullptr
    {
        std::cout << "[" << e->data << "] -> "; // выводим данные из узла списка @data
        e = e->next;                            // ...и переходим к следующему узлу, сдвигая временный указатель e дальше по списку.
    }
    std::cout << "NULL" << endl;                // конец списка у нас всегда указывает на nullptr (NULL)
}

// вывод элементов очереди
void printQueue(Queue* que) {
    std::cout << endl << "Очередь:" << endl;
    printLinearList(que->first);                // по сути эта функция - обертка над выводом элементов списка
}

// Создание очереди que и инициализация её значениями на основе массива values длины length
void createQueue(Queue* &que, int* values, const int length)
{
    if (isEmptyQueue(que))                      // если очередь инициализирована и пуста
    {
        for (int i = 0; i < length; i++)        // в цикле по массиву
        {
            enQueue(que, values[i]);            // ставим элементы в очередь
        }
    }
}

// Очищаем очередь от элементов
void clearQueue(Queue* &que)
{
    while (!isEmptyQueue(que))                  // пока очередь не опустеет
    {
        deQueue(que);                           // извлекаем элемент из очереди (сдвигая очередь к началу)
    }
}



//-------------------------------------------------------------------------------//
// Задача 3 лабораторной (по варианту 1)
//-------------------------------------------------------------------------------//
void operateQueue(Queue* &que)
{
    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " Определение количества положительных значений элементов очереди: " << endl;
    cout << "------------------------------------------------------" << endl;

    int num = 0;                                // количество найденных положительных элементов

    if (isEmptyQueue(que))
    {
        cout << "Очередь пуста...";
        return;
    }

    cout << "Положительные значения:" << endl;
    while (!isEmptyQueue(que))                  // пока очередь не закончилась
    {
        int pop = deQueue(que);             // извлеваем верхнее значение...
        if (pop > 0)                        // проверяем нечетность значения, извлеченного из стэка
        {
            cout << pop << endl;
            num++;                              // ...и подсчитываем количество найденных элементов, удовлетворяющих условиям задачи
        }
    }

    if (num > 0)                                // если в результате обхода списка что-то нашлось, значит можно выводить произведение
    {
        cout << "Количество положительных значений = " << num << endl;
    }
    else                                        // иначе считать особо нечего, не делить же 0 на 0...
    {
        cout << "Чисел удовлетворяющим условиям задачи в очереди не найдено" << endl;
    }
}



int main()
{
    setlocale(LC_ALL, "Russian");

    const int default_length = 5;                               // длина инициализационного массива
    int default_data[default_length] = { 1, -4, 3, -44, 7 };    // инициализационный массив значений для инициализации структур

    Queue* q;                               // переменная для хранения указателя на вершину стэка
    initQueue(q);                           // инициализируем начало и конец очереди
    printQueue(q);

    cout << "------------------------------------------------------" << endl;
    cout << " Создание стэка из массива [1,4,3,44,7]: " << endl;
    cout << "------------------------------------------------------" << endl;
    createQueue(q, default_data, default_length);
    printQueue(q);

    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " Добавление элемента в очередь: " << endl;
    cout << "------------------------------------------------------" << endl;

    int QData = 0;
    cout << "Введите целое число: ";
    cin >> QData;                           // записываем введенное число в переменную
    enQueue(q, QData);
    printQueue(q);

    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " Извлечение элемента из очереди: " << endl;
    cout << "------------------------------------------------------" << endl;
    deQueue(q);
    printQueue(q);

    // задание лабораторной по варианту 1
    operateQueue(q);

    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " ОЧИСТКА всей очереди: " << endl;
    cout << "------------------------------------------------------" << endl;

    clearQueue(q);
    printQueue(q);

    return 0;
}