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

Question

Учитывая две очереди, поддерживающая операции епдиеей/push_back, DEQUEUE/pop_front и размер

Q1: A1 A2 A3 
Q2: B1 B2 B3 

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

Q3: A1 B1 A2 B2 A3 B3 

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

Answer 1

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

Answer 2

Вот некоторые псевдокод:

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

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

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

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

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

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