Jiopik Ответов: 1

Реализация Deque с помощью DLL


У меня есть эта реализация Deque с использованием двусвязного списка, это правильный путь?

Что я уже пробовал:

struct DEQueue
{
	void  enqueueBack(int value);
	void enqueueFront(int value);
	int dequeueFront();
	int dequeueBack();
	bool empty();

private:
	struct Node
	{
		int value;
		Node* next;
		Node* prev;


		Node(int value)
			: value(value), next(nullptr), prev(nullptr)
		{};
	};
	Node* head = nullptr;
	Node* tail = nullptr;
};

void DEQueue::enqueueFront(int value)
{
	Node* tmp = new Node(value);
	if (head)
	{
		tmp->next = head;
		head->prev = tmp;
		head = head->prev;
	}
	else
	{
		tail = head = tmp;
	}
}

void DEQueue::enqueueBack(int value)
{
	Node* tmp = new Node(value);
	if (head)
	{
		tmp->prev = tail;
		tail->next = tmp;
		tail = tail->next;
	}
	else
	{
		head = tail = tmp;
	}
}

int DEQueue::dequeueFront()
{
	if (!head)
	{
		throw out_of_range("queue empty");
	}

	int value = head->value;
	Node* tmp = head;
	head = head->next;
	head->prev = nullptr;
	delete tmp;
	return value;
}

int DEQueue::dequeueBack()
{
	if (!head)
	{
		throw out_of_range("queue empty");
	}

	int value = tail->value;
	Node* tmp = tail;
	tail = tail->prev;
	tail->next = nullptr;
	delete tmp;
	return value;
}

bool DEQueue::empty()
{
	return head == nullptr;
}

Gerry Schmitz

Если это работает, то это "правильно".

1 Ответов

Рейтинг:
5

KarstenK

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

Замечания:
- Я бы из кода класса
- Я пропустил функцию, которая удаляет все узлы за один шаг
- Я скучаю по дополнительным функциям, таким как функция поиска и удаления для некоторого значения
- исключение throw должно быть поймано в любой реализации