Очереди на списках - EcsFlash/DataTypes GitHub Wiki

Исходный код - тут

Очередь

Название типа данных полностью отражает его суть. Представьте себе стандартную очередь возле ларька/кассы в магазине. Элементы(люди) добавляются в конец очереди, а выходят с начала. Соответственно весь код по сути, сводится к двум вещам - добавление элемента в конец связного списка и удаление элемента из начала этого же списка. Использовать будем обычный односвязный линейный список.

Структура узла списка

struct Node {
	T data;
	Node* next;
	Node(T elem) : data(elem), next(nullptr) {};
};

Инициализация очереди

Queue() {
	head = tail = nullptr;
	count = 0;
}

Добавление элемента в очередь

void enque(T elem) {
	Node* p = new Node(elem);
	if (!isEmpty()) {
		tail->next = p;
		tail = p;
	}
	else {
		head = tail = p;
	}
	count++;
}

Удаление элемента из очереди

void deque() {
	if (!isEmpty()) {
		if (head != tail) {
			Node* p = head;
			head = head->next;
			delete p;
			p = nullptr;
			count--;
		}
		else {
			delete head, tail;
			head = tail = nullptr;
                        count = 0;
		}
	}
}

Просмотр первого элемента в очереди

T peek() {
	if (!isEmpty()) {
		return head->data;
	}
}

тут тоже нужно кидаться ошибками, чуть подробнее почему это нужно написал в аналогичной ситуации в стеках.

Вывод очереди

friend std::ostream& operator<<(std::ostream& os, const Queue& a) {
	stringstream ss;
	Node* temp = a.head;

	while (temp != nullptr) {
		ss << temp->data;
		temp = temp->next;
	}
	return os << ss.str();
}

Проверка очереди на пустоту

bool isEmpty() {
	return head == nullptr && tail == nullptr;
}

Очистка очереди

void clear() {
	while (head != nullptr && tail != nullptr) {
		deque();
	}
}

Удаление очереди

~Queue() {
	clear();
}