java - 将 Queue 和 Stack 相互复制

Question

我想用一个空栈S来检查队列Q是否包含元素x，因此我的解决方案是将Q的元素复制到S中并检查是否包含x，但我也被要求将S元素返回到Q中再次因为它是原始的，这必须只使用 Q 和 S 而不使用任何其他 SL 数组来完成，所以我写了这个算法:

Boolean found ← false
int element ←  0
While(Q is not empty) 

  element ← Q.dequeue()
  if(element equal x)
           found ← true
  S.push(element)

While(S is not empty)
 ( elements back to Q) ?

卡在最后一步，如果我使用 Q.enqueue(S.pop) 那么 Q 中元素的顺序将被颠倒

Answer 1

正确，顺序会颠倒。 这意味着如果您再次重复该算法(所有到 S 并返回到 Q)，您将再次反转它，这意味着您将回到元素的原始顺序，这就是您想要的。