java 。如何将两个最初排序的队列合并到一个队列中？ (没有链表或其他东西)

Question

例如，我有第一个队列: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";
    }

}

我的解决方案:公共(public)类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;

Answer 1

问题出在这里:

    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);
    }

这段代码的意思是从第一个队列中删除一个元素，并从第二个队列中删除一个元素。将较小的元素添加到合并队列中，然后将较大的元素添加到合并队列中。

上面的代码在某些情况下不起作用。一个例子是这样的。考虑两个队列 Q1 = {1, 2, 3} 和 Q2 = {4, 5, 6}。在步骤 1(循环，k = 0)中，我们从 Q1 中删除 1，从 Q2 中删除 4。因为 1 小于 4，所以我们加 1，然后加 4。合并后的队列是 {1, 4}，Q1 现在是 {2, 3}，Q2 现在是 {5, 6}。在步骤 2(循环，k = 1)中，我们从 Q1 中删除 2，从 Q2 中删除 5。因为 2 小于 5，所以我们添加 2，然后添加 5。合并后的队列现在为 {1, 4, 2, 5}。请注意，虽然 2 小于 4，但我们在 4 后面添加 2，这是不正确的。这里的问题是，在步骤 1 中，我们不能立即添加 4，因为 Q1 中的下一个元素(即 2)可能小于 4。

你需要做的是这样的:

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();
  }
}

如果您有一个方法可以检索 head 元素，而不将其从队列中删除，那么代码会更加简洁。