5 Replies - 1295 Views - Last Post: 09 January 2013 - 03:07 AM Rate Topic: -----

#1 jimbob1872  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 20
  • Joined: 08-January 13

Priority Queue Unsorted Enqueue Implementation

Posted 08 January 2013 - 03:57 PM

Hi, I managed today to create a sorted implementation of my given interface using a similar basis as shown here. I have used an inner class to help bind the two characteristics of my Priority Queue instead of going with two linked lists running in parallel. I am trying to figure out how to enqueue to the list in 0(1) fashion and then dequeue my element by sorting the priority first and then removing the element with the smallest integer 0(N). I am trying to use the code for the sorted class but It currently outputs the last entry on the priority queue as the highest priority and does not dequeue. any help would be great. here is my code.

public class UnsortedList<E> implements PriorityQueueADT<E>{

	private Link<E> queue;
	private int size = 0;
	
	public UnsortedList(){
		
		queue = null;
	}
	
private class Link<E>{
		
		E element;
		int priority;
		Link<E> next;
	

		public Link(E e, int p, Link<E> n){
			
			this.element = e;
			this.priority = p;
			this.next = n;
		}
		}
	@Override
	public int size() {
		
		return size;
	}

	@Override
	public boolean isEmpty() {
	
		return queue == null;
	}

	@Override
	public E getHighest() throws EmptyQueueException {
		
		if (!isEmpty()){
			return queue.element;
		} else throw new EmptyQueueException("Empty");
	}

	@Override
	public void enqueue(E element, int priority) {
	
		queue = new Link<E>(element,priority,queue);
		
	}

	@Override
	public E dequeue() throws EmptyQueueException {
		
		if (!isEmpty() ||  queue.priority< queue.priority){
			E temp = (E) queue.element;
		
			while(queue.next != null && queue.next.priority <= queue.priority){
				queue = queue.next;
			}
			return temp;
		} else throw new EmptyQueueException("empty");
			 
	}

	
		}



Is This A Good Question/Topic? 0
  • +

Replies To: Priority Queue Unsorted Enqueue Implementation

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1152
  • View blog
  • Posts: 2,530
  • Joined: 05-May 05

Re: Priority Queue Unsorted Enqueue Implementation

Posted 08 January 2013 - 05:03 PM

Quote

I am trying to figure out how to enqueue to the list in 0(1) fashion and then dequeue my element by sorting the priority first and then removing the element with the smallest integer 0(N).


It looks like enqueue works fine. As for dequeue, run through the list and store a pointer to the highest priority node (and its predecessor). Then remove it.

On another note, why not name the class something more specific like PriorityQueue? I'd say the list is sorted (by priority).

This post has been edited by blackcompe: 08 January 2013 - 05:05 PM

Was This Post Helpful? 1
  • +
  • -

#3 farrell2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 823
  • View blog
  • Posts: 2,531
  • Joined: 29-July 11

Re: Priority Queue Unsorted Enqueue Implementation

Posted 08 January 2013 - 05:21 PM

PriorityQueue is an existing class. Pick another name.
Was This Post Helpful? 1
  • +
  • -

#4 jimbob1872  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 20
  • Joined: 08-January 13

Re: Priority Queue Unsorted Enqueue Implementation

Posted 08 January 2013 - 05:39 PM

I can certainly change the class names but I have another class that puts the highest priority in order when enqueing and so that is why I went with unsorted with this one. As it is unsorted when enqueing. Will change them to make them more understandable. I'm trying to get my head around the idea of nodes but thought I could use a similar system with my enqueue as my dequeue in my other class?
Was This Post Helpful? 0
  • +
  • -

#5 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1152
  • View blog
  • Posts: 2,530
  • Joined: 05-May 05

Re: Priority Queue Unsorted Enqueue Implementation

Posted 08 January 2013 - 05:45 PM

Quote

I'm trying to get my head around the idea of nodes but thought I could use a similar system with my enqueue as my dequeue in my other class?


Links...nodes....it's the same thing (in this case). Technically, a link is the thing connecting two nodes. I don't understand what you're asking. Did you understand what I was saying in my first post?

This post has been edited by blackcompe: 08 January 2013 - 05:54 PM

Was This Post Helpful? 0
  • +
  • -

#6 jimbob1872  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 20
  • Joined: 08-January 13

Re: Priority Queue Unsorted Enqueue Implementation

Posted 09 January 2013 - 03:07 AM

Yes sorry I was half asleep last night. I understand your pointer logic and I will attempt that today
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1