2

我在 Java 中使用 2 Stacks 实现了一个队列，我遵循这个算法：

enQueue(x)
将 x 推入 stack1

deQueue()
1) 如果两个堆栈都是空的，则错误。
2) 如果 stack2 为空而 stack1 不为空，则将 stack1 中的所有内容推送到 stack2。
3）从stack2中弹出元素并返回它。

现在，这里的问题是第一个deQueue()操作非常慢（因为它将所有内容传输到stack2）。我们可以以某种方式修改算法，使其deQueue始终为 O(1) 吗？还有其他选择吗？

4

3 回答 3

0

当我们说first deQueue() operation is very slow (since it transfers everything to stack2).

我假设我们正在谈论这个

2) 如果 stack2 为空而 stack1 不为空，则将 stack1 中的所有内容推送到 stack2。

我们是否只是以相同的顺序将 stack1 中的所有内容转移到 stack2 中。这将是简单的赋值 ( stack2=stack1;)，因此是 O(1)。

或者，如果我们说我们需要从 stack1 中逐一弹出所有内容，然后添加到 stack2。我们基本上是在讨论反转一个列表（stack1），并分配给 stack2（我们知道，分配是 O(1)）。有多种很好的算法可以反转列表http://www.codeproject.com/Articles/27742/How-To-Reverse-a-Linked-List-3-Different-Ways。

如果您使用 Java（根据标签），您可以简单地使用Collections.reverse(arrayList);来反转列表。

于 2012-08-21T19:04:58.600 回答
0

我会咬：为什么不使用双向链表？这应该是 O(1) 推送和 O(1) 弹出。

于 2012-08-21T18:41:23.917 回答
0

您可以交换两个堆栈。

去队列（）

  1. 如果两个堆栈都是空的，则错误。
  2. 如果 stack2 为空，而 stack1 不为空，则交换两个堆栈。
  3. 从 stack2 中弹出元素并返回它。

使用交换，操作总是 O(1)

如果您需要一个 FIFO 队列，请使用两个队列。仅当您需要 LIFO 行为时才使用堆栈。

如果是这种情况，使用一个队列或两个队列没有区别，所以你也可以只使用一个队列。如果您使用线程，请使用包装队列和线程池的 ExecutorService。

于 2012-08-21T18:38:28.523 回答