c++ - 将队列转换为堆栈？

Question

我有一个队列，里面有 n 个元素，前面是 0。我需要创建一堆顶部为 0 的数字。

只能通过EnQueue、DeQueue、Push、Pop和常量存储来完成。我不需要答案，只需要知道如何解决这个问题。

请不要为我回答这个问题，只是试着了解我是编程新手，可以使用一种想法来完成这件事。

• 这是一种类似汉诺塔的方法吗？
• 是否只使用常量存储？

这不是作业，我只是需要一些关于如何进行的建议。我的第一个想法，颠倒队列然后推送它并没有奏效。我什至尝试勾勒出其他情况，但无济于事。然后我想知道是否将它们全部出队并压入，然后将它们全部弹出并入队，然后再次出队并压入。

• 这有效率吗？
• 这是否使用常量存储？

我仍在学习基本的编程概念。请友好一点! :)

Answer 1

我面对的是什么？

您面临的最大问题是您的两个容器彼此不直接兼容。

queue 通常是一个 FIFO¹ 容器，而 stack 是 LIFO²。这意味着您不能只是按顺序从您的队列复制数据到您的堆栈，因为这会使元素出现在“错误”中em> 顺序(按照您的描述)。

另一个问题是没有好的方法(性能方面)来反转队列。 队列 是一个单向容器，在内部，一个元素只需要知道行中的下一个元素，而不需要知道前一个元素。这意味着您不能从后面开始遍历队列，并且该迭代总是O(n)。

您的堆栈也有同样的问题。

The things described earlier put together makes this quite a tedious problem, though there are solutions they aren't always the most straight forward.

---

关于如何解决这个问题的提示..

您需要某种中间状态来存储您的元素，或者我们可以利用容器的 LIFO/FIFO 属性来发挥我们的优势吗？

下面是一个执行您想要的操作的实现，如果您不想知道问题的答案不要将鼠标悬停在这个灰色区域上。

这将需要一些额外的存储空间，因为在从一个容器复制到另一个容器的过程中会为额外的元素分配空间。这是不可避免的，尽管存储空间是不变的。

^{请记住，复制初始化可以通过使用 C++11 中的右值引用和移动来优化。}

^{似乎无法在剧透中使用语法高亮显示..}

可以找到示例实现 here .

它利用了 queue 是 FIFO 和 stack LIFO 的事实，通过复制数据 queue 到 stack，然后 stack 到queue 最后再次 queue to stack 我们已经有效地颠倒了元素的顺序，这与您的描述相匹配。

---

<sup>脚注
1. FIFO = 先进先出
2. LIFO = 后进先出</sup>