我将如何仅使用一个附加队列对队列进行排序

Question

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

我如何仅使用一个额外的队列对队列进行排序？

Answer 1

就我个人而言，我不喜欢这种带有任意限制的面试问题，除非它确实反映了您在公司必须面对的条件。我不认为它实际上找到了合格的候选人，或者更确切地说，我不认为它准确地消除了不合格的候选人。当我为我的公司做技术面试时，所有的问题都是现实的和相关的。搁置一边。

虽然肯定有几种方法可以解决这个问题，并且使用递归肯定是其中一种，但我希望如果您尝试使用递归来解决它，他们会要求您在不使用递归的情况下重新完成，考虑到他们正在放置您可以使用的内存和数据结构的限制。否则，他们还不如给你两个队列，一个堆栈和你想要的任意多的内存。

这里是解决该问题的一种方法的示例。最后，应该对 queueB 进行排序。它只使用一个额外的局部变量。这是在 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);
        }

我将如何仅使用一个附加队列对队列进行排序

How would i sort a queue using only one additional queue

algorithm

queue

constants

analysis