Thread: Queue's and linked lists

Alright, so I'm creating a Queue class using pointers, but instead of only being able to insert things into the back, I want to also insert things in the front, and in the middle. the problem I'm having is actually inserting things into the middle of the queue, mainly because I have to keep track of the middle element, thus necessitating a doubly linked list (for proper dequeue-ing). The parts that are in italics are the parts I put in to create a doubly-linked list and I'm not sure on:

here's my code for enqueue:

Code:

template <class Element_Type>
void Queue<Element_Type>::enqueue(const Element_Type item)
{
   if(len != 0) //if the queue is not empty
   {
      back->next = new QueNode<Element_Type>; //create a new node
	  back->prev = back;
      back = back->next; //set the new node as the back node
      back->data = item;       back->next = NULL;    
   }
   else
   {
      back = new QueNode<Element_Type>; //create a new node
      back->data = item;       back->next = NULL; back->prev = NULL;      front = back;
	  mid = back;
   }
   len++; //increment the amount of elements in the queue

   if(len%2 != 0 && len > 1)
   {
	   mid = mid->next;
   }

Here's for inserting something in the front of the queue:

Code:

template <class Element_Type>
void Queue<Element_Type>::High_priority_enqueue(const Element_Type item)
{
	   QueNode<Element_Type> *ptr = new QueNode<Element_Type>;
		ptr->data = item;
		ptr->next = front;
		front = ptr;
		if (ptr->next == NULL)
		{
			back = ptr; 
			front = ptr;
			mid = ptr;
		}
   len++; //increment the amount of elements in the queue
   if(len%2 != 0 && len > 1)
   {
	   mid = mid->next;
   }
}

And the trouble one - inserting in the middle of the queue:

Code:

template <class Element_Type>
void Queue<Element_Type>::Medium_priority_enqueue(const Element_Type item)
{
	QueNode<Element_Type> *ptr = new QueNode<Element_Type>;
		ptr->data = item;
		ptr->next = mid->next;
		ptr->prev = mid;
		mid->next = ptr;
		if (ptr->next == NULL)
		{
			back = ptr; 
			front = ptr;
			mid = ptr;
		}
	
   len++; //increment the amount of elements in the queue
   if(len%2 != 0 && len > 1)
   {
	   mid = mid->next;
   }
}

It crashes when I try to run it, and debugging is really hard since I'm dealing with pointers

I think the error comes in me not correctly creating a doubly linked list, thus creating an invalid mid pointer when it tries to use it for inserting into the middle of the queue.

If you need any more info, just let me know.

Thanks!

Why don't you show some code to call these classes to create such a crash scenario? I think it would be easier to debug the code then.

Alright, I fixed things up a little bit by traversing to the middle instead of trying to keep tabs on the middle of the list at all times (a little less efficient, but at the same time, a lot easier).
The problem is that it seems to create a loop from the beginning to the middle (i.e. if I have a list of 1,2,3,4,5,6 and insert 99 into the middle, it will output 1,2,3,99 then crash <But debugging, 'this' has values 1,2,3,99,1,2,3,99>). It's so close!! haha

Code:

 template <class Element_Type>
void Queue<Element_Type>::Medium_priority_enqueue(const Element_Type item) 
{
	QueNode<Element_Type> *ptr = front,
	*prevPtr = NULL,
	*newNode = new QueNode<Element_Type>;
	newNode->data = item;
	newNode->next = ptr;

	int mid = len / 2;

	for (int i = 0; i < mid; i++) 
	{
		prevPtr = ptr;
		ptr = ptr->next;
	}

	if (len == 0)
	front = back = newNode;
	else if (len == 1)
	front = newNode;
	else
	prevPtr->next = newNode;

	len++;
}