# Making a Priority Queue a FIFO structure

Page 1 of 1

## 4 Replies - 7017 Views - Last Post: 28 September 2010 - 04:33 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=191866&amp;s=f599ca372a04b60fb084c34f0d4f4404&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Jayp806

• New D.I.C Head

Reputation: 1
• Posts: 35
• Joined: 26-October 09

# Making a Priority Queue a FIFO structure

Posted 24 September 2010 - 11:04 AM

I have an assignment for my advanced data structures class where I'm supposed to take the teacher's Priority Queue class and modify it as so:

"Modify the PriorityQueue class we developed so that when there is more than a single item in the PriorityQueue with highest priority, the one that has been in the longest is the one removed. The underlying data structure must still be the array representation of the heap, but otherwise you are free to make changes as long as they do not change the interface itself."

Here is the source code.

```public class PriorityQueue
{
private Comparable[] HeapArray;
int     Last, Limit;

public PriorityQueue(int Capacity)
{
HeapArray = new Comparable[Capacity+1];
Last      = 0;
Limit     = Capacity;
return;
}
// end constructor

public PriorityQueue()
{
HeapArray = new Comparable[101];
Last      = 0;
Limit     = 100;
return;
}
// end constructor

public void Insert(Comparable PQI)
{
if (Last == Limit)
{
System.out.println("Priority Queue Overflow!");
System.exit(0);
}
// end if

HeapArray[++Last] = PQI;
this.UpHeap(Last);
return;
}
// end public method Insert

private void UpHeap(int k)
{
Comparable V;

V = HeapArray[k];

while (k > 1  &&  HeapArray[k/2].compareTo(V) < 0)
{
HeapArray[k] = HeapArray[k/2];
k = k/2;
}
// end while

HeapArray[k] = V;
return;
}
// end private method UpHeap

public Comparable Remove()
{
Comparable PQI ;

if (Last == 0)
{
System.out.println("Priority Queue Underflow!");
System.exit(0);
}
// end if

PQI = HeapArray[1];
HeapArray[1] = HeapArray[Last--];
this.DownHeap(1);
return PQI;
}
// end public method Remove

private void DownHeap(int k)
{
Comparable V;
int    j;

V = HeapArray[k];

while (k <= Last/2)
{
j = k+k;

if (j < Last  &&  HeapArray[j].compareTo(HeapArray[j+1]) < 0)
j++;
// end if

if (V.compareTo(HeapArray[j]) >= 0)
break;
// end if

HeapArray[k] = HeapArray[j];
k = j;
}
// end while

HeapArray[k] = V;
return;
}
// end private method DownHeap

public boolean IsEmpty()
{
if (Last == 0)
return true;
else
return false;
// end if
}
// end public method IsEmpty

public boolean IsFull()
{
if (Last == Limit)
return true;
else
return false;
// end if
}
// end public method IsFull

public int Length()
{
return Last;
}
// end public method Length
}
// end class PriorityQueue

```

I've been told by former students of the class that a good idea would be to use an array as a time stamp to keep track of when something is inserted or removed from the Queue. I have no idea how to implement this.I'm thinking that modifying the upheap method is the way to do this. If you're able to put the item with highest priority and that has been in the longest at the front of the Queue, the remove function shouldn't have to be modified. Any help would be greatly appreciated.

Is This A Good Question/Topic? 0

## Replies To: Making a Priority Queue a FIFO structure

### #2 Dogstopper

• The Ninjaducky

Reputation: 2915
• Posts: 11,169
• Joined: 15-July 08

## Re: Making a Priority Queue a FIFO structure

Posted 24 September 2010 - 12:31 PM

""Modify the PriorityQueue class we developed so that when there is more than a single item in the PriorityQueue with highest priority, the one that has been in the longest is the one removed""

MY understanding of this problem is that if there items with highest priority (say two with a priority of one), then you are to remove the oldest highest priority item. Does this not mean that only one item can be the "highest" priority, cause if you add any highests, it removes the last highest one. Think about that.
Was This Post Helpful? 0

### #3 Jayp806

• New D.I.C Head

Reputation: 1
• Posts: 35
• Joined: 26-October 09

## Re: Making a Priority Queue a FIFO structure

Posted 24 September 2010 - 08:22 PM

The instructor explicitly said that if there are two items in the Queue with the same priority, the one that was put in the Queue is removed firstht For example, if you have two items with a priority of 9 and 9 is the highest priority, when you call the Remove function the 9 that was put in the Queue first is taken out.I'm sorry if the instructions weren't specific enough.

This post has been edited by Jayp806: 24 September 2010 - 08:24 PM

Was This Post Helpful? 0

### #4 codyH

• New D.I.C Head

Reputation: 0
• Posts: 7
• Joined: 31-August 06

## Re: Making a Priority Queue a FIFO structure

Posted 28 September 2010 - 01:03 PM

As you are storing Comparables inside the PQ you could simply add a data member to your comparable object that has the time inserted into the PQ as its value, so then when two or more items of equal priority occur you default based on time.
Was This Post Helpful? 0

### #5 pbl

• There is nothing you can't do with a JTable

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Making a Priority Queue a FIFO structure

Posted 28 September 2010 - 04:33 PM

The easiest way would be to have an array[][] of Comparable like [10][101]
[10] for priority 0 to 9

When inserting an element you put it in the array of its priority
When removing an element scan the 10 priority subarray for the first one with element(s) into it an retreive from that array the first oen put in
Was This Post Helpful? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }