例如，我有第一个队列：front[1 3 5 7]back 和第二个队列 front[2 4 6 8]back。新的合并队列必须是：front[1 2 3 4 5 6 7 8]back。或者第一个队列：front[1 3 3 7]back，第二个队列：front[2 4 5 7 8]back。新合并队列：front[1 2 3 3 4 5 7 7 8]back。我们不能使用任何类型的排序。这是我的队列实现：

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 change body of generated methods, choose Tools | Templates.
        }

        Q[r] = value;

        r = (r + 1) % capacity;

    }


    public int dequeue() throws Exception {
        int element;
        if (isEmpty()) {
            throw new Exception("Empty"); //To change body of generated methods, choose Tools | Templates.
        }
        element = Q[f];

        f = (f + 1) % capacity;
        return element;

    }


    public int getSize() {
        return (capacity - f + r) % capacity;
    }


    public boolean isEmpty() {
        return (f == r);
    }

    public String toString() {
        int z = f;
        String s;
        s = "f[";

        if (getSize() >= 1) {
            s += Q[0];
            for (int i = 1; i <= getSize() - 1; i++) {
                s += " " + Q[z + 1];
                z = (z + 1) % capacity;

            }
        }
        return s + "]b";
    }

}

我的解决方案：公共类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 = a - b;
    }

    for (int i = 0; i < k; i++) {

        a = 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()) {

        for (int i = 0; i < t; i++) {
            m = q1.dequeue();
            merged.enqueue(m);

        }
    } else if (q1.getSize() < q2.getSize()) {
        for (int i = 0; i < t; i++) {
            m = q2.dequeue();
            merged.enqueue(m);

        }
    }

    return merged;
}

}

这是有效并满足条件的代码：

IntQueue 合并 = new QueueImpl(); 整数a，b；

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

    return merged;

解决方案

问题就在这里：

    a = 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 one element from the first queue, and remove one element from the second queue. Add the smaller element into the merged queue, and then add the larger element into the merged queue.

The above code does not work for some cases. One example is this. Consider two queues Q1 = {1, 2, 3} and Q2 = {4, 5, 6}. In step 1 (loop, k = 0), we remove 1 from Q1 and 4 from Q2. Because 1 is smaller than 4, we add 1, followed by 4. The merged queue is {1, 4}, Q1 is now {2, 3}, and Q2 is now {5, 6}. In step 2 (loop, k = 1), we remove 2 from Q1 and 5 from Q2. Because 2 is smaller than 5, we add 2, followed by 5. The merged queue is now {1, 4, 2, 5}. Notice that although 2 is smaller than 4, we add 2 after 4, which is incorrect. The problem here is that in step 1, we cannot immediately add 4, because the next element in Q1 (which is 2) may be smaller than 4.

What you need to do is something like this:

int e1 = q1.dequeue();
int e2 = q2.dequeue();

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

If you have a method that can retrieve the head element, without removing it from the queue, the code can be much cleaner.