Ad:

Java Discussion Thread
Marked Solved
Views: 649

Jan 21st, 2009

queue question: part 2.

Expand Post »

In a queue, where elements in integers are added, how do i do this:

Inside the queue:

1 2 3 5 6 8

when I want to add a number, say 4, the output should be like:

1 2 3 4 5 6 8

in which it inserts in between 2 and 5. Queues are FIFO but somehow this doesn't make sense. I think this has something to do with priority. the example above is just an ordinary queue, not to confused with a priority queue..
Can someone explain and help me?
thanks!

Similar Threads

Need help in making a queue system in C++
question in Java
Help With syntax in Visual Basic 4 / 5 / 6
Need new graphics card but need help first. in Monitors, Displays and Video Cards
Self documentation in C++

ezkonekgal

Reputation Points: 9

Solved Threads: 1

Junior Poster

Offline

109 posts
since Sep 2008

Permalink

Jan 22nd, 2009

Re: queue question: part 2.

This sounds like sorting an array rather than a queue. As you said, queues work on the FIFO format, so you can't sort a queue since you will lose track of which one should be removed next. Are you sure this is what your task requires?

darkagn

Reputation Points: 395

Solved Threads: 192

Veteran Poster

Offline

1,136 posts
since Aug 2007

Permalink

Jan 22nd, 2009

Re: queue question: part 2.

Well it depends she could be using a Priority Queue, in which members are organized in the ascending or descending order.

Also priority queue implementations may vary, some may do the selection of element to be removed at deletion time while others may do the sorting at insertion time so that elements in queue are always in a sorted order (based on priority which is what the O.P. wants here) for deletion.

Now to do the above, you will have to traverse your queue until you find an element that is greater than the element you wish to insert and then fit in your element there. Also let us see what you have tried.

<EDIT>
Also just my two cents, according to me a Linked List based implementation would be lot easier to implement than an Array based implementation.

Last edited by stephen84s; Jan 22nd, 2009 at 12:29 am.

stephen84s

Featured Poster

Reputation Points: 653

Solved Threads: 151

Nearly a Posting Virtuoso

Offline

1,316 posts
since Jul 2007

Permalink

Jan 22nd, 2009

Re: queue question: part 2.

Click to Expand / Collapse Quote originally posted by stephen84s ...

Now to do the above, you will have to traverse your queue until you find an element that is greater than the element you wish to insert and then fit in your element there. Also let us see what you have tried.

<EDIT>
Also just my two cents, according to me a Linked List based implementation would be lot easier to implement than an Array based implementation.

here is what i had so far:

java Syntax (Toggle Plain Text)
public int compareTo(int x){
    QueueNode temp = front;
    while(temp != null){
         if (temp.info > x)
           temp.info = new queueNode(x);
           temp = temp.link 
    }          
}
public int compareTo(int x){
    QueueNode temp = front;
    while(temp != null){
         if (temp.info > x)
           temp.info = new queueNode(x);
           temp = temp.link 
    }          
}

is this ryt?

ezkonekgal

Reputation Points: 9

Solved Threads: 1

Junior Poster

Offline

109 posts
since Sep 2008

Permalink

Jan 22nd, 2009

Re: queue question: part 2.

ok i made revisions on the code i just posted:

java Syntax (Toggle Plain Text)
 public void compareTo(int item){
    	QueueNode temp = front;
    	while(temp != null){
    		if (temp.info > item)
    			temp.info = item;
    			temp = temp.link;
    		}
    }
 public void compareTo(int item){
    	QueueNode temp = front;
    	while(temp != null){
    		if (temp.info > item)
    			temp.info = item;
    			temp = temp.link;
    		}
    }

And this is my enQueue, or my add to queue method:

java Syntax (Toggle Plain Text)
  public void enQueue(int item) {
        if(empty()){
            rear = new QueueNode(item);
            front = rear;
        }else{
        	compareTo(item);
        	rear.link = new QueueNode(item);
        	rear = rear.link;
 
        }
    }
  public void enQueue(int item) {
        if(empty()){
            rear = new QueueNode(item);
            front = rear;
        }else{
        	compareTo(item);
        	rear.link = new QueueNode(item);
        	rear = rear.link;

        }
    }

It seem that when i add, like, 4 to the qeue

1 2 5

it does this:

1 2 4 4

whereas it should be

1 2 4 5

the element 5 is gone and is know replaced by two 4's.. i believed that 5 is deleted.. can any help me with this?

ezkonekgal

Reputation Points: 9

Solved Threads: 1

Junior Poster

Offline

109 posts
since Sep 2008

Permalink

Jan 22nd, 2009

Re: queue question: part 2.

You will need to maintain a reference to the previous element also in the above code. Because as per your requirement you want to insert the new element before the element "temp" is holding a reference of when you are traversing the queue.

Now let us take analyse your code one line at a time :-

java Syntax (Toggle Plain Text)

    QueueNode temp = front;

This is fine, you are declaring the temporary reference to your start of Queue.

java Syntax (Toggle Plain Text)
    while(temp != null){
        if (temp.info > x)
    while(temp != null){
        if (temp.info > x)

Now your while condition states that you will should go through to the end of the queue. However there is a problem if your "if" condition, Consider you list contains the following elements :-

2 3 4 9 10

And you wish to insert the value "7",
Because of your "if" condition temp will enter the "if" block only when it is pointing to "9". And since this is a singly linked list you cannot traverse backwards. So you cannot insert "7" in the correct position in the list. For that you will need to also maintain a reference to node in your queue preceding the node to which "temp" is currently referring to.

java Syntax (Toggle Plain Text)
           temp.info = new queueNode(x);
           temp.info = new queueNode(x);

Now over here this statement at least appears to be incorrect. Although I do not know your structure for class "queueNode", I am guessing "info" should be of type "int". Also you are overwriting directly the value present at the current location, You should instead create a new node, and assign it to another temporary variable say "temp2", and then in order to maintain the "link" in your linked list, the "link" field of this new node should be assigned to current value in "temp". And the "link" field of the node preceding "temp" should be made to point to the new node. So your new element would be linked into your queue before "temp" which contains an element larger than it.

Also you will need to put a "break" in your "if" block else the new value will be inserted after every element greater than it. For example your list queue would become:-

2 3 4 7 9 7 10 ...

(Where 7 is the element being inserted in queue 2 3 4 9 ...)
EDIT:

Currently citing your previous code as I had reply already typed in earlier but just forgot to submit it.

Last edited by stephen84s; Jan 22nd, 2009 at 8:50 am.

stephen84s

Featured Poster

Reputation Points: 653

Solved Threads: 151

Nearly a Posting Virtuoso

Offline

1,316 posts
since Jul 2007

Permalink

Jan 23rd, 2009

Re: queue question: part 2.

Here's my idea, i have 2 queues, in which i kepp track of them by:
1st queue:
front and rear;

2nd queue:
front2 and rear.

before i had read your reply stephen84s, i decided to have two queues. When an integer is added, it goes into the 1st queue. when another " int" is added to queue, what happens is the element in queue1 is tranfered to queue2. Elements in queue2 would them be, one by one, compared to the incoming number which is 'held at bay', which would traverse from the head or front of the queue. If item at queue2 is less than item at bay, the first item at queue2 would be transferred back to queue1, this would go on until when an item at queue2 is greater than item at bay, item at bay is then inserted(dequeued from queue2 and enqueued in queue1) at queue1, them the item at queue2 is next to be inserted at at queue1. Whew, i don't know if that makes any sens.

And below was the code i made:

java Syntax (Toggle Plain Text)
    public void enQueue(int item) {
        if(empty()){
            rear = new QueueNode(item);
            front = rear;
        }else{
        	while (front != null){
        		int item2 = deQueue();
        		rear2 = new QueueNode(item2);
        		front2 = rear2;
        	}
        		compareTo(item);
        		rear.link = new QueueNode(item);
            	rear = rear.link;
        	//rear.link = new QueueNode(item);
        	//rear = rear.link;
 
        }
    }
    public void enQueue(int item) {
        if(empty()){
            rear = new QueueNode(item);
            front = rear;
        }else{
        	while (front != null){
        		int item2 = deQueue();
        		rear2 = new QueueNode(item2);
        		front2 = rear2;
        	}
        		compareTo(item);
        		rear.link = new QueueNode(item);
            	rear = rear.link;
        	//rear.link = new QueueNode(item);
        	//rear = rear.link;

        }
    }

java Syntax (Toggle Plain Text)
 public void compareTo(int item){
    	QueueNode temp = front2;
    	int x = 0;
    	while (temp != null){
    		if (temp.info < item){
    			 x = temp.info;
    			 rear = new QueueNode(x);
                 front = rear;
    		}else if(temp.info > item){
    			int item2 = temp.info;
    			rear = new QueueNode(item2);
                front = rear;
            	rear.link = new QueueNode(item);
            	rear = rear.link;
    		}else{
    			rear.link = new QueueNode(item);
            	rear = rear.link;
            }
    	}
    }
 public void compareTo(int item){
    	QueueNode temp = front2;
    	int x = 0;
    	while (temp != null){
    		if (temp.info < item){
    			 x = temp.info;
    			 rear = new QueueNode(x);
                 front = rear;
    		}else if(temp.info > item){
    			int item2 = temp.info;
    			rear = new QueueNode(item2);
                front = rear;
            	rear.link = new QueueNode(item);
            	rear = rear.link;
    		}else{
    			rear.link = new QueueNode(item);
            	rear = rear.link;
            }
    	}
    }

But i will consider what you suggested. Thanks .

ezkonekgal

Reputation Points: 9

Solved Threads: 1

Junior Poster

Offline

109 posts
since Sep 2008

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in Java Forum Timeline: JApplet KeyListener help

Next Thread in Java Forum Timeline: who knows?

DaniWeb Message

Cancel Changes

User Name
Password