Click here to Skip to main content
15,881,173 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I am having this implementation of Deque using doubly linked list, is this the correct way?

What I have tried:

C++
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;
}
Posted
Updated 3-Jan-20 22:46pm
Comments
[no name] 3-Jan-20 16:41pm    
If it works, it's "correct".

1 solution

Looks correct, but best is to write some test code with known results to prove your implementation.

Remarks:
- I would code DEQueue as class
- I miss a function which deletes all nodes in one step
- I miss additional functions like search function and remove for some value
- the exception throw must get catched in any implementation
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900