Results 1 to 20 of 20

Thread: Priority Queue

  1. #1
    Suende's Avatar
    Suende is offline Member
    Join Date
    Apr 2011
    Posts
    22
    Rep Power
    0

    Default 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)
    	public void addInteger(int num)
    	{
    		ints.add(0, num);
    	}
    
    	// 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();
    		q.addInteger(3);
    		q.addInteger(14);
    		q.addInteger(1);
    		q.addInteger(5);
    		q.addInteger(9);
    
    		// 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. #2
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #3
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    How do I have one class derived from another?
    Use the "extends" keyword.

  4. #4
    Suende's Avatar
    Suende is offline Member
    Join Date
    Apr 2011
    Posts
    22
    Rep Power
    0

    Default

    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();
    		q.addInteger(3);
    		q.addInteger(14);
    		q.addInteger(1);
    		q.addInteger(5);
    		q.addInteger(9);
    
    		// Output the queue
    		System.out.println("The contents of the queue are:");
    		while (!q.isEmpty())
    		{
    			System.out.println(q.removeInteger());
    		}
    	}
    }

  5. #5
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #6
    Suende's Avatar
    Suende is offline Member
    Join Date
    Apr 2011
    Posts
    22
    Rep Power
    0

    Default

    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();
    		q.addInteger(3);
    		q.addInteger(14);
    		q.addInteger(1);
    		q.addInteger(5);
    		q.addInteger(9);
    
    		// 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. #7
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

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

  8. #8
    Suende's Avatar
    Suende is offline Member
    Join Date
    Apr 2011
    Posts
    22
    Rep Power
    0

    Default

    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. #9
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #10
    Suende's Avatar
    Suende is offline Member
    Join Date
    Apr 2011
    Posts
    22
    Rep Power
    0

    Default

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

  11. #11
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #12
    Suende's Avatar
    Suende is offline Member
    Join Date
    Apr 2011
    Posts
    22
    Rep Power
    0

    Default

    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. #13
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    Would you mind posting both codes?

  14. #14
    Suende's Avatar
    Suende is offline Member
    Join Date
    Apr 2011
    Posts
    22
    Rep Power
    0

    Default

    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();
    		q.addInteger(3);
    		q.addInteger(14);
    		q.addInteger(1);
    		q.addInteger(5);
    		q.addInteger(9);
    
    		// 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)
    	public void addInteger(int num)
    	{
    		ints.add(0, num);
    	}
    
    	// 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();
    		q.addInteger(3);
    		q.addInteger(14);
    		q.addInteger(1);
    		q.addInteger(5);
    		q.addInteger(9);
    
    		// Output the queue
    		System.out.println("The contents of the queue are:");
    		while (!q.isEmpty())
    		{
    			System.out.println(q.removeInteger());
    		}
    	}
    }

  15. #15
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #16
    Suende's Avatar
    Suende is offline Member
    Join Date
    Apr 2011
    Posts
    22
    Rep Power
    0

    Default

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

  17. #17
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #18
    Suende's Avatar
    Suende is offline Member
    Join Date
    Apr 2011
    Posts
    22
    Rep Power
    0

    Default

    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. #19
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #20
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,380
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by sunde887 View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. priority
    By simorgh in forum Threads and Synchronization
    Replies: 4
    Last Post: 01-07-2012, 12:49 AM
  2. Priority Queue experts needed !!!
    By niu_niu in forum New To Java
    Replies: 48
    Last Post: 06-11-2010, 08:48 AM
  3. Priority Queue Question
    By Taz_84 in forum New To Java
    Replies: 0
    Last Post: 01-29-2009, 03:23 AM
  4. How to implement Priority queue with Java
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-12-2008, 08:49 PM
  5. How to get/set thread priority
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-09-2008, 06:40 PM

Posting Permissions

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