#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;
}