Способ объединения двух очередей в определенном порядке - PullRequest
Новая
       20

Способ объединения двух очередей в определенном порядке

0 голосов
/ 06 февраля 2011 
private ArrayQueue<E> merge( ArrayQueue<E> q1, ArrayQueue<E> q2 ) throws ArrayQueueException 
{
    ArrayQueue<E> mergeQueue = new ArrayQueue<E>( q1.size() + q2.size() );

    ArrayQueue<E> smallestQueue = smallestQueue( q1, q2 );
    ArrayQueue<E> biggestQueue = biggestQueue( q1, q2 );

    for ( int index = 0; index < smallestQueue.size(); index++ )
    {
        E elementOne = smallestQueue.dequeue();
        E elementTwo = biggestQueue.dequeue();

        if ( elementOne.compareTo( elementTwo ) < 0 )
        {
            mergeQueue.enqueue( elementOne );
            mergeQueue.enqueue( elementTwo );
        }
        else
        {
            mergeQueue.enqueue( elementTwo );
            mergeQueue.enqueue( elementOne );
        }
    } 

    for ( int index = 0; index < biggestQueue.size(); index++ )
    {
        mergeQueue.enqueue( biggestQueue.dequeue() );
    }

    return ( mergeQueue );
}

Я занимался упражнением, которое включает создание метода для объединения двух очередей.Моя попытка выше работает, когда обе очереди имеют одинаковый размер, но в противном случае это неправильно.

Каков наилучший способ реализовать это?

Спасибо.

1 Ответ

1 голос
/ 06 февраля 2011

Это не единственная проблема с вашим методом.

Псевдокод правильного метода выглядит так: 

while (both queues are not empty) {
    retrieve first elements without removing them from their queues
    compare them
    put the appropriate element into the new queue and remove it from its old queue
}

if any of old queues is not empty, put its elements into the new queue
...