如何使用两个队列实现堆栈?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (17)

鉴于两个队列与他们的标准操作(enqueuedequeueisemptysize),实现堆栈与它的标准操作(poppushisemptysize)。

应该有两个版本的解决方案。

  • 版本A:推送物品时堆叠应该高效; 和
  • 版本B:弹出一个项目时堆栈应该是有效的。

提问于
用户回答回答于

版本A(高效推送):

    • 排队在队列1中

    • 当队列1的大小大于1时,管道将队列1中的项目排入队列2
    • 出队并返回队列1的最后一项,然后切换队列1和队列2的名称

版本B(高效流行):

    • 排队在队列2中
    • 将队列1的所有项排入队列2,然后切换队列1和队列2的名称

    • 队列1的请求

用户回答回答于

最简单的(也可能是唯一的)这样做的方法是将新元素推入空队列,然后将另一个元素出队并将队列存入之前为空的队列中。通过这种方式,最新的信息总是在队列的前端。这将是版本B,对于版本A,您只需通过将元素出队到除最后一个之外的第二个队列来反转进程。

第0步:

"Stack"
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

步骤1:

"Stack"
+---+---+---+---+---+
| 1 |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

第2步:

"Stack"
+---+---+---+---+---+
| 2 | 1 |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  | 2 | 1 |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

第3步:

"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 3 | 2 | 1 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

扫码关注云+社区