CODEWITHSUNDEEP
java
Adam Thompson
Adam Thompson

Reputation: 306

Java Priority Queue With Linked Lists

I have been trying to figure out a question on a recent assignment for a few days now, and I can't seem to wrap my head around it. The question reads as follows:

Create a PriorityQueue class that contains two fields noOfPriorities and a LinkedList… It should have one constructor that takes in an int value assign that value to the noOfPriorities… at the same time add as many LinkedLists as numberOfPriorities.. Enqueue method that takes in a priority and an object.. Dequeue method that returns the next priority element… and remove it from the list…

A large part of my problem is that I can't determine exactly what the professor is looking for because the wording seems a bit weird to me... simply asking about it yielded no help either.

Just to clarify, I'm not looking for anyone to give me the answer. I'm simply looking for a push in the right direction. If anyone could help It would be greatly appreciated.

Upvotes: 2

Views: 2144

Answers (3)

Wug
Wug

Reputation: 13196

I think you'd need an array of linked lists instead of just one. The problem description is contradictory, saying that you need both a class that has one linked list, and to create a number of them when you construct an object.

Here's a constructor for your class:

MyPriorityQueue(int npriorities)
{
    noOfPriorities = npriorities;
    queueArray = new ArrayList<List<T>>();
    for (int i = 0; i < npriorities; ++i) queueArray.add(new LinkedList<T>());
}

You'd then have a mapping of priorities to queues. Your enqueue method would take an object and a priority (an int representing a priority) and would add the object to the queue specified by the priority. Your dequeue method would simply return the end of the highest priority queue with an element in it.

Make any sense?

Upvotes: 0

Matt Stephenson
Matt Stephenson

Reputation: 8620

Agreed, the assignment's badly worded.

at the same time add as many LinkedLists as numberOfPriorities..

This should probably be "at the same time add as many nodes to the LinkedList as numberOfPriorities.."

The next question to ask yourself is, just what type of thing should I store in all these linked nodes...?

Upvotes: 0

stacktrace
stacktrace

Reputation: 319

Cheers on being honest about this being homework.

I think you can understand the problem better if you read up on what a priority queue is.

Let's take a small example. You have a few tasks to do, and each task has a priority.

  • Pri 1 - breathe, eat, sleep
  • Pri 2 - study, play
  • Pri 3 - watch a movie

All the above information can be handled by your PriorityQueue. You have 3 kinds of priorities, so you have 3 lists. Each list is to maintain tasks with the same priority.

Once you construct the empty PriorityQueue by calling PriorityQueue(3), you can add tasks to it.

Let's say you want to add the task "study" that has priority 2. You can say, priorityQueue.enqueue(2, "study"). You would then go to the list that maintains priority 2 items, and add the task "study" to that list.

Similarly, when you want to find out what the next priority 3 item is, you can say, priorityQueue.dequeue(3). You would then find the list that handles priority 3 items, and remove the last element from that list.

This should give you a good understanding to start working. :)

Upvotes: 3

Related Questions