我将如何仅使用一个附加队列对队列进行排序 [英] How would i sort a queue using only one additional queue

问题描述

所以基本上，我要求排序一个队列，而我只能使用一个助手队列，并且只允许恒定数量的额外内存。

So basically, Im asked to sort a queue, and i can only use one helper queue , and am only allowed constant amount of additional memory.

我将如何

推荐答案

我个人不喜欢这样带有任意限制的面试问题，除非它实际上反映了您必须在公司工作的条件。我认为它实际上没有找到合格的候选人，或者我认为它可以准确地剔除不合格的候选人。
当我为公司进行技术面试时，所有问题都是切合实际和相关的。

Personally, I don't like interview questions with arbitrary restrictions like this, unless it actually reflects the conditions you have to work with at the company. I don't think it actually finds qualified candidates or rather, I don't think it accurately eliminates unqualified ones. When I did technical interviews for my company, all of the questions were realistic and relevant. Setting that aside.

虽然肯定有几种方法可以解决此问题，但是使用递归当然是一种方法，我希望如果您尝试通过递归来解决问题，考虑到它们在限制您可以使用的内存和数据结构方面的限制，因此请您不进行递归进行操作。否则，他们可能会给您两个队列，一个堆栈和您想要的尽可能多的内存。

While there are surely several ways to solve this, and using recursion is certainly one, I would hope that if you tried to solve it with recursion they would have asked you to do it over without recursion, considering they are placing limits on the memory you can use and the data structures. Otherwise, they might as well as given you two queues, a stack and as much memory as you want.

这里是解决该问题的一种示例。最后，应该对queueB进行排序。它仅使用一个额外的局部变量。

Here is an example of one way to solve it. At the end of this, queueB should be sorted. It uses just one extra local variable. This was done in C#.

        queueB.Enqueue(queueA.Dequeue());
        while (queueA.Count > 0)
        {
            int next = queueA.Dequeue();
            for (int i = 0; i < queueB.Count; ++i)
            {
                if (queueB.Peek() < next)
                {
                    queueB.Enqueue(queueB.Dequeue());
                }
                else
                {
                    queueB.Enqueue(next);
                    next = queueB.Dequeue();
                }
            }
            queueB.Enqueue(next);
        }

这篇关于我将如何仅使用一个附加队列对队列进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！