Custom Implementation of a Priority Queue

Question

I've an assignment and the requirements are described in the code comment below:

package com.abc.exercise;

/**
 * 1) Implement a priority queue class with the interface given below. 
 * 2) Multiple items with the same priority can be added to the queue
 * 3) java.util package should not be used
 * 4) You can add your own behaviour as required 
 */

public interface PriorityQueue<T> {

    // An item with the given priority is added into the queue
    public void add(int priority, T value);

    //finds the item with the highest priority and removes it from the queue
    public T remove();

    //finds the item with the highest priority but does not remove it from the queue
    public T find();

    //Returns the number of items in the queue.
    public int qsize();
}

How should I proceed?

Answer 1

When you add things to your data structure, what do you imagine the data structure looks like? Is it one dimensional like a bunch of things in a file folder, or two-dimensional like things on a chess board? Straight like a bunch of things in a line, or branching like a tree?

What kind of operation does the addition need to perform on that data structure - that is, where does it need to put it?

Where do your remove and find routines need to look within the data structure?

How would your qsize function go about counting things in the data structure?

Answer 2

I'd suggest to start learning array basics. Here's a Java tutorial about that. Use that "under the hoods", if necessary with here and there a little help of System#arraycopy() to resize the array. It's the only which is helpful outside the java.util package.

Answer 3

It's not urgent to anyone here. I'd fix that title and make it more descriptive.

Wow, you have an interface given to you and you don't know where to start?

If you aren't willing to take your failing grade now, I'd recommend starting with a concrete implementation of the interface:

package com.abc.exercise;

/**
 * 1) Implement a priority queue class with the interface given below. 
 * 2) Multiple items with the same priority can be added to the queue
 * 3) java.util package should not be used
 * 4) You can add your own behaviour as required 
 */

public class PriorityQueueImpl<T> implements PriorityQueue<T> 
{

    // An item with the given priority is added into the queue
    public void add(int priority, T value)
    {
    }

    //finds the item with the highest priority and removes it from the queue
    public T remove()
    {
    }

    //finds the item with the highest priority but does not remove it from the queue
    public T find()
    {
        T value;

        return value;
    }

    //Returns the number of items in the queue.
    public int qsize()
    {
    }
}

Since you can't use java.util classes, think about an array of type T and see where that goes.

Write a regular queue, without the priority. Get that working, then add priority.