具有 2 个堆栈的队列实现 - 最少的入栈和出栈操作

Question

队列 Q 使用 2 个堆栈 S1 和 S2 实现，并尽可能使用 算法。考虑在以下操作中执行 空队列按顺序：入队（A），入队（B），入队（C）， 出队()、入队(E)、入队(F) 出队()、出队()、出队()

执行上述操作最少的PUSH和POP次数 所需的操作分别是x和y。价值是多少 x * y？

这是一道家庭作业，答案是90，但我认为应该是56。

如果我们使用以下算法，答案是 90。

Enqueue:
Push the new element onto inbox

Dequeue:
If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
Pop and return the top element from outbox

但是，如果我们对 Dequeue oprtaion 进行以下更改，我们也可以获得 56 作为答案。

Updated_Dequeue:
If outbox is empty:
   Refill it by popping each element from inbox and pushing it onto outbox except the last one.
   Pop and return the top(which is the last one) element from inbox
else:
   Pop and return the top element from outbox

每次我们在出列操作时将元素从收件箱复制到发件箱时，这将为我们节省一次 Pop 和一次 Push 操作。

我不认为这种改变会让算法渐近更好，但由于问题特别要求 PUSH 和 POP 操作的最小数量，它应该是 56，不是吗？

谢谢！

Answer 1

在最基本的堆栈实现中，您无法知道堆栈上有多少元素。这种基本实现的唯一操作是

push

和

pop

，当尝试弹出空堆栈时会发生错误（或错误值）。一个小的扩展是有一个

isEmpty

方法，这样就能够防止错误。

我想这个挑战所预设的就是这种类型的堆栈接口，因此如果不执行弹出操作，您将无法知道收件箱堆栈上只剩下一个元素。