queue question: part 2.

[ezkonekgal]

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!

[darkagn]

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?

[stephen84s]

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.

[ezkonekgal]

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:

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]

ok i made revisions on the code i just posted:

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:

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?

[stephen84s]

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 :-

QueueNode temp = front;

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

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.

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.

[ezkonekgal]

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:

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 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 .