Способ отменить очередь, используя только две временные очереди и ничего более?

Question

Есть ли способ изменить порядок элементов в очереди, используя только две временные очереди (и никаких других переменных, таких как счетчики)? Доступны только стандартные операции с очередями: ENQUEUE (e), DEQUEUE (), EMPTY ()?

Решения на любом языке или псевдокод приветствуются.

Answer 1

Вы можете:

• Используйте две очереди для имитации стека .
• Вставьте все элементы исходной очереди в этот стек.
• Теперь вытолкните каждый элемент из стека и добавьте его в исходную очередь.

Answer 2

Я понимаю, что этот поток давно мертв, но я считаю, что нашел довольно хорошее решение, которое отвечает всем требованиям.

Вам понадобится только одна временная очередь. То, что вы делаете, пока исходная очередь не пуста, вы перемещаете последний узел в очереди вперед, устанавливая указатель на последний узел и запрашивая и повторно вводя узлы в исходную очередь. Затем вы удаляете очередь из исходной очереди и ставите ее во временную очередь. После этого вы просто копируете темп обратно в исходную очередь.

Вот мое решение в стиле C, ADT: (По крайней мере, мне не нужно беспокоиться о том, чтобы делать за тебя домашнее задание)

QUEUE * reverseQueue (QUEUE * очередь) {

QUEUE *temp;
QUEUE_NODE *pLast;
void *dataPtr;

//Check for empty queue
if(emptyQueue(queue))
    return NULL;

//Check for single node queue
if(queueCount(queue) == 1)
    return queue;

temp = createQueue();   
while(!emptyQueue(queue))
{   
    pLast = queue->rear;
    //Move last node to front of queue
    while(queue->front != pLast)
    {
        dequeue(queue, &dataPtr);
        enqueue(queue, dataPtr);
    }
    //Place last node in temp queue
    dequeue(queue, &dataPtr);
    enqueue(temp, dataPtr);

}
//Copy temp queue back to original queue
while(!emptyQueue(temp))
{
    dequeue(temp, &dataPtr);
    enqueue(queue, dataPtr);
}
destroyQueue(temp);
return queue;

}

Answer 3

// REVERSE OF QUEUE USING 1 QUEUE N OTHER DEQUEUE
void reverse() {
  int q1[20],q2[20],f1,r1,f2,r2;
  while(f1!=r1) {
     q1[r2]=q1[f1];
     r2=r2+1;
     f1=f1+1;
  }
  //whole elements of temporary queue is transfered to dequeue.
  while(r2!=f2) {
     q1[r1]=q2[r2];
     r2=r2-1;
     r1=r1+1;
  }
}

Answer 4

Чтобы перевернуть строку из очереди, которая является содержимым очереди, нам нужно еще две очереди в первой очереди удалите все элементы, кроме последнего, и поместите их в очередь во второй очереди. Теперь поставьте в очередь последний элемент в 3-й очереди, которая является результирующей очередью. Сделайте транзакции из 2-й в 1-ю очередь и поставьте в очередь последний элемент в 3-м стеке Повторяется до тех пор, пока оба стека не будут пустыми.

Answer 5

Это похоже на Ханойская башня пазл:)

Вот решение в C #:

static Queue<T> ReverseQueue<T>(Queue<T> initialQueue)
{
    Queue<T> finalQueue = new Queue<T>();
    Queue<T> intermediateQueue = new Queue<T>();

    while (initialQueue.Count > 0)
    {
        // Move all items from the initial queue to the intermediate queue, 
        // except the last, which is placed on the final queue.
        int c = initialQueue.Count - 1;
        for (int i = 0; i < c; i++)
        {
            intermediateQueue.Enqueue(initialQueue.Dequeue());
        }
        finalQueue.Enqueue(initialQueue.Dequeue());

        // Swap the 'initialQueue' and 'intermediateQueue' references.
        Queue<T> tempQueue = initialQueue;
        initialQueue = intermediateQueue;
        intermediateQueue = tempQueue;
    }

    return finalQueue;
}

Answer 6

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

Если вы можете использовать только эти три операции, вы должны использовать обе временные очереди.

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

Я бы дал псевдокод, но опять же, я боюсь, что делаю твою домашнюю работу для тебя.

Answer 7

while(!queue.EMTPY())
{
    while(!finalQueue.EMPTY())
    {
        tempQueue.ENQUEUE(finalQueue.DEQUEUE());
    }
    finalQueue.ENQUEUE(queue.DEQUEUE());
    while(!tempQueue.EMPTY())
    {
        finalQueue.ENQUEUE(tempQueue.DEQUEUE());
    }
}

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

Answer 8

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