0

我有一个包含 n 个元素的队列,前面位于0. 0我需要在顶部创建一堆这些数字。

它只能通过EnQueueDeQueuePushPop以及常量存储来完成。我不需要答案,而是想知道如何解决这个问题。

请不要为我回答这个问题,而只是尝试了解我是编程新手,并且可以使用一种可以完成的方法的想法。

  • 这是一种类似河内塔的方法吗?
  • 那只使用常量存储吗?

这不是家庭作业,我只需要一些关于如何进行的建议。我的第一个想法,反转队列然后推送它不起作用。我什至尝试勾勒出其他情况,但无济于事。然后我想知道是否将它们全部出列并推送,然后将它们全部弹出并入列,然后再次出列并推送。

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

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

4

2 回答 2

4

DeQueue 队列中的所有内容,立即将每个元素推送到 Stack。现在从 Stack 中弹出所有内容,立即 EnQueueing 到 Queue。现在队列中有什么?

假设您的 Queue 和 Stack 保存固定大小的项目,上述ahem子例程当然只使用恒定的额外存储:当每个项目从 Queue 传输到 Stack 时,只需要存储 1 个项目,反之亦然。

编辑:正如您所指出的,我的子程序反转了队列的内容。这样做之后,将队列再次排入堆栈以获得所需的结果是相当简单的。

而且,正如您所指出的,这需要传输3n = O(n)项目,n队列的初始大小在哪里。你能做得更好吗?我不这么认为,或者至少不是很明显。从某种意义上说,即使没有计数器(这会占用O(log n) > O(1)额外的存储空间),唯一合理的做法是将队列排入堆栈,反之亦然。

于 2012-07-14T06:22:10.570 回答
3

我面临什么?

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

队列通常是 FIFO 1容器,而堆栈是 LIFO 2。这意味着您不能仅将数据按顺序从队列复制到堆栈,因为这会使元素以“错误”的顺序出现(按照您的描述)。

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

你的stack也有同样的问题。

前面描述的事情放在一起使这个问题变得相当乏味,尽管有一些解决方案它们并不总是最直接的。


有关如何解决此问题的提示..

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

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

它将需要一些额外的存储空间,因为在从一个容器复制到另一个容器期间将分配额外元素的空间。这是不可避免的,尽管存储空间是恒定的。

请记住,复制初始化可以通过使用右值引用进行优化,并在 C++11 中移动。

似乎无法在剧透中突出显示语法。

示例实现可以在 此处找到。

它利用队列是 FIFO 和堆栈LIFO 的事实,通过将数据队列复制到堆栈,然后将堆栈复制到队列,最后再次排队到堆栈,我们以符合您描述的方式有效地颠倒了元素的顺序。


脚注1. FIFO = 先进先出2. LIFO = 后进先出
   
   

于 2012-07-14T06:32:16.023 回答