Page 1 of 1

Reputation:

# Priority queue using comparables

Posted 05 December 2010 - 05:59 PM

Hey I'm doing an exercise and having a bit of trouble with it. I'm required to represent my queue as a sequence of comparables. I'm doing it using a circular array. So joining the queue will involve finding the correct position based on it's priority.

Here's my compare to method:
```public int compareTo(Object o)
{
// 1:   films duration is greater than 'o'
if(this.duration > ((Film)o).duration)
return 1;
// 0:   films duration equals 'o'
else if(this.duration == ((Film)o).duration)
return 0;
// -1:   films durations is less than 'o'
return -1;
}
```

And my "enqueue" method for joining the queue which is unfinished:
```public void enqueue (Comparable o)
{

if(isEmpty())
{
int temp =rear;
rear= (rear + 1) % queue.length;
if (front ==rear)
{
rear = temp;
throw new FullQueueException ();
}
queue[rear] = o;
}

else
{

for(int i = 0; i <= queue.length; i++)
{
//duration is greater so everything must be moved right
if(o.compareTo(queue[i]) == 1 )
{
for(int x = 0; x <= queue.length; x++)
{
int temp =rear;
rear= (rear + 1) % queue.length;
if (front ==rear)
{
rear = temp;
throw new FullQueueException ();
}
queue[rear] = queue[rear+1];
}
queue[front] = o;
}

if(o.compareTo(queue[i]) == 0 )
{

}
```

Just wondering if i'm on the right track or if what i'm doing is way off. Sorry for such a long post, thanks.. any help appreciated

Is This A Good Question/Topic? 0

## Replies To: Priority queue using comparables

### #2 pbl

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

Reputation: 8066
• Posts: 31,310
• Joined: 06-March 08

## Re: Priority queue using comparables

Posted 05 December 2010 - 06:48 PM

complicated for nothing
```int compareTo(Object o) {
return duration - ((Film) o).duration;

```

Better to declare
class Film implements Comparable<Film>
```int compareTo(Film o) {
return duration - o.duration;

```

Reputation:

## Re: Priority queue using comparables

Posted 05 December 2010 - 07:00 PM

Ok thanks, ha suppose that one line of code is what i should have used.

Is my code cretaing the queue correct? seem to be having trouble with the last part, the maxElements part.

``` package PriorityQueue;
import entities.Film;

public abstract class ArrayCircularQueue implements Queue,  Comparable<Film>
{

private int front = 0, rear = 0;
private Comparable<Film> []queue;

public ArrayCircularQueue (int maxElements)
{
queue = new Comparable [maxElements];
}
```

### #4 pbl

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

Reputation: 8066
• Posts: 31,310
• Joined: 06-March 08

## Re: Priority queue using comparables

Posted 05 December 2010 - 07:08 PM

Not really, you missed the whole concept. Nothing to be shamed about
Queues are queues not ARRAY and they are there to AVOID array.
Queue are build out of nodes that have a pointer to the next node (null if there is not one) in the queue, and optionaly in a circular queue, to the previous node object

Reputation:

## Re: Priority queue using comparables

Posted 05 December 2010 - 07:54 PM

But is there still nodes when i'm doing it with the array circular queue? using the mod operater.. I'm having trouble trying to move all elements right in this queue. For example, I need to place something in between others because it's priority says it's in there, so how would i make space for it in my circular array queue?? thanks again, hope i'm making sense!

### #6 macosxnerd101

• Self-Trained Economist

Reputation: 9160
• Posts: 33,981
• Joined: 27-December 08

## Re: Priority queue using comparables

Posted 05 December 2010 - 08:02 PM

You'll have to manually resize your array. Almost better to just use ArrayList<Film>, as ArrayList does all the resizing and position adjustment for you. If you must use static arrays, you'll have to create a new array of a larger size, shift the elements, then insert the new element. Finally, set the old array equal to the new array.

Quote

But is there still nodes when i'm doing it with the array circular queue?

No. You must use a Linked List, which is what pbl was talking about. Basically, you have Nodes pointing to each other. When you go to insert elements, you use a single iteration of insertion sort to determine their ordering.

### #7 pbl

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

Reputation: 8066
• Posts: 31,310
• Joined: 06-March 08

## Re: Priority queue using comparables

Posted 05 December 2010 - 08:03 PM

A queue is NOT an array
A queue is composed of Node

```class Node {
Object data;     // whatever is own in the node
Node next;       // pointer no next Node
}

```

And the que is built from node

```Node firstNode = new Node()[
firstNode.data = "this is first node or whatever";

Node secondNode = new Node();
secondNode.data = "this is seond node"

firstNode.next = secondNode;
secondNode.next = null;  // end of list

```

now from fisrtNode you can scan all nodes until next == null

### #8 macosxnerd101

• Self-Trained Economist

Reputation: 9160
• Posts: 33,981
• Joined: 27-December 08

## Re: Priority queue using comparables

Posted 05 December 2010 - 08:06 PM

@pbl: Not entirely true. A Queue, like a Stack, is just a structure that enforces a certain ordering (FIFO for Queue, LIFO for Stack). With Queues, generally a LinkedList backs them. However, with Stacks an array backs them. In order for the Queue to be circular though, I agree with you that it *must* be Node based.

Reputation:

## Re: Priority queue using comparables

Posted 05 December 2010 - 08:16 PM

But can't you make a queue using a circular array which uses the mod(%) operator? or is the code in my first post going to have to be completely changed?

### #10 pbl

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

Reputation: 8066
• Posts: 31,310
• Joined: 06-March 08

## Re: Priority queue using comparables

Posted 05 December 2010 - 08:29 PM

```class Node {
Object data;     // whatever is own in the node
Node next;       // pointer no next Node
Node previous;
}

```

And the queue is built from node

```Node firstNode = new Node();
Node secondNode = new Node();
Node thirdNode = new Node();

firstNode.data = "this is first node or whatever";
secondNode.data = "this is second node";
thirdNode.data = "this is third node";

firstNode.next = secondNode;
firstNode.previous = thirdNode;

secondNode.next = thirdNode;
secondNode.previous = firstNode;

thirdNode.next = firstNode;
thirdNode.previous = secondNode;

```

### #11 CiRi

• New D.I.C Head

Reputation: 0
• Posts: 1
• Joined: 12-December 10

## Re: Priority queue using comparables

Posted 12 December 2010 - 02:08 PM

Hi I am having the exact same problems with this I understand what needs to be done i just cant get my head around coding it correctly and any help would be much appreciated

here is all my code so far and some of jklam as the project seems to be similar..

```package queue;

import entities.Film;

public class ArrayCircularQueue implements Queue {
private int front = 0, rear = 0;
private Object []queue;

public ArrayCircularQueue (int maxElements) {
queue = new Object [maxElements];
}

public void enqueue (Comparable o)
{

if(isEmpty())
{
int temp =rear;
rear= (rear + 1) % queue.length;
if (front ==rear)
{
rear = temp;
throw new FullQueueException ();
}
queue[rear] = o;
}

else
{

for(int i = 0; i <= queue.length; i++)
{
//duration is greater so everything must be moved right
if(o.compareTo(queue[i]) == 1 )
{
for(int x = 0; x <= queue.length; x++)
{
int temp =rear;
rear= (rear + 1) % queue.length;
if (front ==rear)
{
rear = temp;
throw new FullQueueException ();
}
queue[rear] = queue[rear+1];
}
queue[front] = o;
}

if(o.compareTo(queue[i]) == 0 )
{

}

public Object dequeue () {
Object result = null ;
if (front ==rear)
throw new EmptyQueueException ();
front= (front + 1) % queue.length;
result = queue[front] ;
queue[front] = null ;
return queue[front];
}

public boolean isFull () {
return ((rear + 1) %queue.length) ==front;
}

public Object getTop() {
int pos = (front + 1) % queue.length;
return queue[pos];
}

public boolean isEmpty() {
return front==rear;
}

public int compareTo(Film o)
{
// 1:   films duration is greater than 'o'
if(this.duration > ((Film)o).duration)
return 1;
// 0:   films duration equals 'o'
else if(this.duration == ((Film)o).duration)
return 0;
// -1:   films durations is less than 'o'
return -1;
}

public void enqueue(Object object) {
// TODO Auto-generated method stub

}

}
```

there are very basic coding errors i think and all help to fix and improve it would be appreciated if possible thanks again.