1. ## Priority Queue

Hello all. I have a problem today where I do not understand the instructions and was wondering if anyone could help me understand what I am supposed to do.

Java Code:
```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package integerqueue;

/**
*
*
*/
// This class stores a queue (a list) of integers
import java.util.ArrayList;

public class IntegerQueue
{
private ArrayList<Integer> ints = new ArrayList<Integer>();

// Default constructor
public IntegerQueue()
{
// Intentionally blank
}

// Returns true if the queue is empty
public boolean isEmpty()
{
if (ints.size() == 0)
return true;
return false;
}

// Adds a new number to the beginning of the list (at index 0)
{
}

// Removes the number from the beginning of the list and returns it
public int removeInteger()
{
// Does nothing if the list is empty
if (!isEmpty())
{
return ints.remove(0);
}

return -1;
}
public static void main(String[] args)
{
// Create a queue and add some numbers to it
IntegerQueue q = new IntegerQueue();

// Output the queue
System.out.println("The contents of the queue are:");
while (!q.isEmpty())
{
System.out.println(q.removeInteger());
}
}
}```
And the instructions given:
Another special type of queue is a priority queue. A priority queue behaves like a regular queue except the removeInteger method always extracts the item with the smallest value (this is the item with the highest priority). Create a IntegerPriorityQueue class that is derived from the IntegerQueue class. Override the removeInteger method in the IntegerPriorityQueue class to extract the item with the smallest value. Test the IntegerPriorityQueue class by changing the sample main method to create a IntegerPriorityQueue instead of a IntegerQueue. . The numbers should be output in order from smallest to largest. You may need to change the modifier on the ints variable to protected rather than private.

How do I have one class derived from another?
Last edited by Suende; 04-25-2011 at 04:57 AM.

2. I suggest you read the tutorials for a detailed explanation with examples.

You extend the base class,
Java Code:
`class Derived extends Base`
the derived class inherits from the base class. Try to see what you can do, and view the tutorials for more help. When you finish your code attempt, post it with errors/problems you are running into.

3. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
How do I have one class derived from another?
Use the "extends" keyword.

4. Okay!
Got that bit, so it seemed to me like by changing the IntegerQueue into a IntegerPriorityQueue it would remove the int with the lowest value but it does not seem to remove any of the numbers.

Java Code:
```public class IntegerPriorityQueue extends IntegerQueue {

@Override
public int removeInteger()
{
// Does nothing if the list is empty
if (!isEmpty())
{
return ints.remove(0);
}

return -1;

}
public static void main(String[] args)
{
// Create a queue and add some numbers to it
IntegerPriorityQueue q = new IntegerPriorityQueue();

// Output the queue
System.out.println("The contents of the queue are:");
while (!q.isEmpty())
{
System.out.println(q.removeInteger());
}
}
}```

5. One of the most important things your priority queue should do is keep the array list sorted. That way you can remove the lowest int at all times.

6. Java Code:
```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package integerqueue;

import java.util.Collections;
import java.util.List;

/**
*
* @author Brett
*/
public class IntegerPriorityQueue extends IntegerQueue {

@Override
public int removeInteger()
{
Collections.sort(ints);
// Does nothing if the list is empty
if (!isEmpty())
{
return ints.remove(0);
}

return -1;

}
public static void main(String[] args)
{

// Create a queue and add some numbers to it
IntegerPriorityQueue q = new IntegerPriorityQueue();

// Output the queue
System.out.println("The contents of the queue are:");

while (!q.isEmpty())
{
System.out.println(q.removeInteger());
}
}
}```
The Collections.sort(ints); does that right?
its all in order now....how do I make it remove the lowest/first from the ArrayList now...
Last edited by Suende; 04-25-2011 at 06:31 AM.

7. Yup, using that you can sort the array list, and then remove the lowest number.

8. I kind of though the bit where it says return ints.remove(0); would have removed the first value from the ArrayList?
Thank you for walking me through this sunde

9. You are welcome, be sure to test it and make sure it works as you expect. If you are done in this thread, please mark it solved with the thread tools at the top.

10. Almost there, I am just trying to see why the return ints.remove(0);l isn't actually removing anything.

11. Since ints is private, I don't believe it is available, add a getter to the super class, and then use the getter to get access to it in the base class.

12. I changed int to protected and so it prints out the contents, but the only change between the original and what I have overridden is that the overridden version prints out in numerical order, neither actually remove the int that occupies the 0 spot in the arrraylist.

13. Would you mind posting both codes?

14. This is the one I have I need to make work to remove the lowest int in the ArrayList
Java Code:
```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package integerqueue;

import java.util.Collections;
import java.util.List;

/**
*
*
*/
public class IntegerPriorityQueue extends IntegerQueue {

@Override
public int removeInteger()
{
Collections.sort(ints);
// Does nothing if the list is empty
if (!isEmpty())
{
return ints.remove(0);
}

return -1;

}
public static void main(String[] args)
{

// Create a queue and add some numbers to it
IntegerPriorityQueue q = new IntegerPriorityQueue();

// Output the queue
System.out.println("The contents of the queue are:");

while (!q.isEmpty())
{
System.out.println(q.removeInteger());
}
}
}```

This is the entire code
Java Code:
```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package integerqueue;

/**
*
* @author Brett
*/
// This class stores a queue (a list) of integers
import java.util.ArrayList;

public class IntegerQueue
{
protected ArrayList<Integer> ints = new ArrayList<Integer>();

// Default constructor
public IntegerQueue()
{
// Intentionally blank
}

// Returns true if the queue is empty
public boolean isEmpty()
{
if (ints.size() == 0)
return true;
return false;
}

// Adds a new number to the beginning of the list (at index 0)
{
}

// Removes the number from the beginning of the list and returns it
public int removeInteger()
{
// Does nothing if the list is empty
if (!isEmpty())
{
return ints.remove(0);
}

return -1;
}

public static void main(String[] args)
{
// Create a queue and add some numbers to it
IntegerPriorityQueue q = new IntegerPriorityQueue();

// Output the queue
System.out.println("The contents of the queue are:");
while (!q.isEmpty())
{
System.out.println(q.removeInteger());
}
}
}```

15. If you call Collections.sort it will modify ints arrayList, to avoid having a sorted arrayList, try using a loop to find the index of the lowest number, then remove it.

16. but even the equation without the Collections.sort isn't removing any numbers from the array.....?

17. What makes you say that? What happens if you remove every element from the queue and then try removing another element after the loop?

ArrayList remove looks like this
Java Code:
``` E 	remove(int index)
Removes the element at the specified position in this list.```
E is the return type, which is the parametrized argument. Since your remove method returns the return value of arrayList method it returns the element at 0. Since your goal is to remove the lowest element in the queue it will print out all the elements in order.

18. What makes me say that? When I run the program without the Collections.sort in it I get the same numbers returned that I can see are in the ArrayList so I know none of them are being removed from that one either
Yes I want my method to remove the element that is held at the 0 position because after it is sorted that is where the the element with the least value will be.
That makes sense right? I guess I do not understand what you are asking me to do.

19. It does remove them, in main, add a call to remove as the last line in main and see what is returned. Also, re read my last post, it explains what happens. The elements are being removed.

20. Originally Posted by sunde887
One of the most important things your priority queue should do is keep the array list sorted. That way you can remove the lowest int at all times.
That is not really necessary (although much easier for this exercise); you should keep the queue in a 'heap' form which can be a full binary tree such that if a node N is at position i in the array (where we store the nodes) its possible left and right children are at positions 2*(i+1)-1 and 2*(i+1) and the value of the node is less than or equal to both of its chuldren. This definition ensures that the smallest node is always at the root of the tree which is stored in location 0 of the array. If you remove that node you have to 'reheap' the tree which is faster than entirely sorting the array again. Google for 'heapsort' to find out how that is done.

kind regards,

Jos

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•