Как объединить две очереди в одну очередь?

Question

Учитывая две очереди, поддерживающие операции enqueue / push_back, dequeue / pop_front и size

Q1: A1 A2 A3
Q2: B1 B2 B3

как мне объединить их в третью очередь (также поддерживающую те же операции), получив:

Q3: A1 B1 A2 B2 A3 B3

Меня больше интересует используемый алгоритм, а не какие-либо конкретные языковые реализации.

Answer 1

Вот какой-то псевдокод:

Queue mergeQueues(Queue A, Queue B)
{
    Queue newQ;
    while(A.nonempty() OR B.nonempty())
    {
        if (A.nonempty())
            newQ.push(A.pop());
        if (B.nonempty())
            newQ.push(B.pop());
    }
    return newQ;
}

Где push вставляет элемент в очередь, а pop удаляет следующий элемент в очереди и возвращает его.

Обратите внимание, что это не работает для стека. Вы будете в конечном итоге с элементами в обратном направлении. Если бы вы могли перевернуть стек (например, путем многократного переноса в другой стек), он бы работал.

Answer 2

Пока обе очереди не пусты, удалите элемент из очереди A и добавьте его в newQ. Затем удалите элемент из очереди B. Если одна из очередей (A или B) пуста, удалите из очереди остальную часть другой очереди и поместите каждый элемент в newQ.

Answer 3

Это кажется вполне поддающимся рекурсивной реализации:

mergeQueues :: Queue a -> Queue a -> Queue a
mergeQueues qa qb =
    merge qa qb emptyQueue
    where
        merge qa qb qr
            | isEmpty qa = append qb qr
            | otherwise  = move (merge qb) qa qr
        append q qr
            | isEmpty q  = qr
            | otherwise  = move append q qr
        move f q qr =
            let (val,q') = pop q
             in f q' (push val qr)

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

Обратите внимание, что, хотя это больше, чем императивная версия, заданная ribond, она выполняет минимальное количество проверок isEmpty. Если вы не против сделать столько проверок, сколько он делает в немного более оптимизированной версии (присвоение значений isEmpty переменным для повторного использования ниже), вы можете удалить функцию append и просто вместо этого вызывать merge, после добавления начального теста к merge, который проверяет, чтобы обе очереди были пустыми, и, если это так, завершил рекурсию.

Для тех, кто не знаком с Haskell, мы переходим, чтобы переместить следующую вызываемую функцию (это функциональное программирование высшего порядка); в случае append это просто добавление, в случае move это «частично примененная» функция перемещения: она получает первый параметр, qb, примененный до того, как мы вызовем move, а затем move применяет два других параметра.

Это звучит как разумная задача, с которой можно столкнуться в повседневном деловом программировании. Однако, если это функция домашней работы, я предлагаю вам внимательно изучить, как работает приведенный выше код, и я думаю, что вы чему-то научитесь.

Также есть вероятность, что в приведенном выше коде есть ошибка; Доказать, что это работает (или найти ошибку) было бы отличным упражнением.