Queue's and linked lists

This is a discussion on Queue's and linked lists within the C++ Programming forums, part of the General Programming Boards category; Alright, so I'm creating a Queue class using pointers, but instead of only being able to insert things into the ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    26

    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!

  2. #2
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,765
    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.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    26
    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++;
    }

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,803
    So have you dropped the whole double-linked list or not? Looks like you only have a singly-linked list with that latest example.

    Just a guess:
    Code:
    QueNode<Element_Type> *ptr = front,
        *prevPtr = NULL,
        *newNode = new QueNode<Element_Type>;
    newNode->data = item;
    newNode->next = ptr;
    That looks like it's in the wrong place.

    Maybe:
    Code:
    else
    {
        prevPtr->next = newNode;
        newNode->next = ptr;
    }
    Maybe also:
    Code:
    else if (len == 1)
    {
        front = newNode;
        newNode->next = ptr;
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked lists, stacks and queues
    By aniramg69 in forum C Programming
    Replies: 10
    Last Post: 11-29-2008, 10:58 AM
  2. Little warning on linked lists example
    By Nazgulled in forum C Programming
    Replies: 10
    Last Post: 12-18-2007, 02:02 PM
  3. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  4. need help understanding Linked lists
    By Brain Cell in forum C Programming
    Replies: 6
    Last Post: 07-16-2004, 01:29 PM
  5. Queues
    By Orely in forum C++ Programming
    Replies: 2
    Last Post: 12-12-2001, 05:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21