Thread: Priority Queue Array

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    5

    Priority Queue Array

    I have written a priority queue program using an array. It works except that the values pop out highest first. I could probably change the pop function to read from the end, but I would like to just fix whatever is wrong with the push function.

    Here is the function:
    Code:
    void PArrayClass:: pushData(int num)
    {
    	if(rear<(MAX_SIZE-2))//make sure there is room to add something
    	{
    		for (int check=0; num<=data[check]; check++)
    		{
    			cout << check << ", " << data[check] << endl; //added to make sure this loop really did something
    		}//find where to insert new cell
    		for (int move=rear; move>=check; move--)
    		{
    			data[move+1]=data[move];
    		}//move all cells over one
    		data[check]=num;
    		rear++;
    		noOfItems++;
    	}
    	else
    	{
    		cout << "\nNo more room to add data.\n";
    	}
    }
    The example I am using is the set {4, 5, 2}. I think the data should end up being stored in the array as {2, 4, 5} with 2 at index 0. This program is putting 5 at index 0.

    If it makes any difference, I initialized the array to all 0's.

    Thank you for your help.

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    I have written a priority queue program using an array. It works except that the values pop out highest first.
    Isn't that the definition of a priority queue? This is how it should work.
    "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

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Isn't that the definition of a priority queue? This is how it should work
    Depends on what your priority is In his case the smaller number takes priority.

    change this line:
    Code:
    for (int check=0; num<=data[check]; check++)
    to this:
    Code:
    for (int check=0; num>=data[check]; check++)
    and it should work.

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    5
    Changing the

    num<=data[check]

    to

    num>=data[check]

    creates an infinite loop with the code the way it is since the array is initialized to zero. Maybe if I added a part to just put the first number into the array at index [0], then move on from there....that should work.

    Thanks!!!

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Oops, my bad. You would need to change it to this I believe - unfort I'm at work so can't test it.

    if rear points to the first empty spot:
    for (int check=0; num<=data[check] && check<rear; check++)

    if rear points to last item in the array (what does it point to when array is empty? if it points to the zero spot, then you would need an extra check to see if queue is empty):
    for (int check=0; num<=data[check] && check<=rear; check++)

  6. #6
    Registered User
    Join Date
    Apr 2003
    Posts
    5
    Rear is set to -1 and front is 0 if there is no data in the array. Rear is incremented when an element is added (push), and front gets incremented when an element is used (pop).

    I can't test anything right now either. At work too, otherwise the rotten thing would work by now.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  3. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 09:51 AM
  4. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM