Java. How to merge two initially sorted queues in one queue? (without linked lists or something else) -

Java. How to merge two initially sorted queues in one queue? (without linked lists or something else) -

for illustration have first queue: front[1 3 5 7]back , sec queue front[2 4 6 8]back. new merged queue must be: front[1 2 3 4 5 6 7 8]back. or first queue: front[1 3 3 7]back, second: front[2 4 5 7 8]back. new merged queue: front[1 2 3 3 4 5 7 7 8]back. , can't utilize types of sorting. here implementation of queue:

public class queueimpl implements intqueue { protected int capacity; public static final int capacity = 100; protected int q[]; protected int f = 0, r = 0; public queueimpl() { this(capacity); } public queueimpl(int cap) { capacity = cap; q = new int[capacity]; } public void enqueue(int value) throws exception { if (getsize() == capacity - 1) { throw new exception("full"); //to alter body of generated methods, take tools | templates. } q[r] = value; r = (r + 1) % capacity; } public int dequeue() throws exception { int element; if (isempty()) { throw new exception("empty"); //to alter body of generated methods, take tools | templates. } element = q[f]; f = (f + 1) % capacity; homecoming element; } public int getsize() { homecoming (capacity - f + r) % capacity; } public boolean isempty() { homecoming (f == r); } public string tostring() { int z = f; string s; s = "f["; if (getsize() >= 1) { s += q[0]; (int = 1; <= getsize() - 1; i++) { s += " " + q[z + 1]; z = (z + 1) % capacity; } } homecoming s + "]b"; } }

my solution: public class assign2problem3solution {

public static intqueue merge(intqueue q1, intqueue q2) throws exception { intqueue merged = new queueimpl(); int a, b, k, t, m; if (a < b) { k = a; t = b - a; } else { k = b; t = - b; } (int = 0; < k; i++) { = q1.dequeue(); b = q2.dequeue(); if (a < b) { merged.enqueue(a); merged.enqueue(b); } else if (b < a) { merged.enqueue(b); merged.enqueue(a); } } if (q1.getsize() > q2.getsize()) { (int = 0; < t; i++) { m = q1.dequeue(); merged.enqueue(m); } } else if (q1.getsize() < q2.getsize()) { (int = 0; < t; i++) { m = q2.dequeue(); merged.enqueue(m); } } homecoming merged; }

}

here code works , satisfies conditions:

intqueue merged = new queueimpl(); int a, b;

if (!q1.isempty() && !q2.isempty()) { = q1.dequeue(); b = q2.dequeue(); while (true) { if (a < b) { merged.enqueue(a); if (q1.isempty()) { merged.enqueue(b); break; } = q1.dequeue(); } else { merged.enqueue(b); if (q2.isempty()) { merged.enqueue(a); break; } b = q2.dequeue(); } } } if (q1.getsize() > 0) { while (!q1.isempty()) { = q1.dequeue(); merged.enqueue(a); } } else if (q2.getsize() > 0) { while (!q2.isempty()) { b = q2.dequeue(); merged.enqueue(b); } } homecoming merged;

the problem here:

= q1.dequeue(); b = q2.dequeue(); if (a < b) { merged.enqueue(a); merged.enqueue(b); } else if (b < a) { merged.enqueue(b); merged.enqueue(a); }

this code means remove 1 element first queue, , remove 1 element sec queue. add together smaller element merged queue, , add together larger element merged queue.

the above code not work cases. 1 illustration this. consider 2 queues q1 = {1, 2, 3} , q2 = {4, 5, 6}. in step 1 (loop, k = 0), remove 1 q1 , 4 q2. because 1 smaller 4, add together 1, followed 4. merged queue {1, 4}, q1 {2, 3}, , q2 {5, 6}. in step 2 (loop, k = 1), remove 2 q1 , 5 q2. because 2 smaller 5, add together 2, followed 5. merged queue {1, 4, 2, 5}. notice although 2 smaller 4, add together 2 after 4, incorrect. problem here in step 1, cannot add together 4, because next element in q1 (which 2) may smaller 4.

what need this:

int e1 = q1.dequeue(); int e2 = q2.dequeue(); while (true) { if (e1 < e2) { merged.enqueue(e1); if (q1.isempty()) { // add together remaining q2 elements while (!q2.isempty()) { merged.enqueue(q2.dequeue()); } break; } // take element q1 e1 = q1.dequeue(); } else { merged.enqueue(e2); if (q2.isempty()) { // add together remaining q1 elements while (!q1.isempty()) { merged.enqueue(q1.dequeue()); } break; } // take element q2 e2 = q2.dequeue(); } }

if have method can retrieve head element, without removing queue, code can much cleaner.

java merge queue sorted