检查O（1）空间中两个堆栈是否相等

Question

在采访中有人问我：

使用O（1）空间检查给定的两个堆栈是否相等（元素的大小和顺序）。

堆栈应保持其早期状态（元素顺序）。

递归使用堆栈空间，因此无效。

[我的一个朋友建议使用String变量，并将一个堆栈中的元素追加到其中，然后将弹出窗口推入另一个堆栈，然后从S2（S1的旧元素）推入S1，并对S2执行相同的操作。但这取决于堆栈的大小，因为字符串会根据堆栈的大小而增长。

Answer 1

Recursion vs迭代在这里不是问题。问题在于如何保持堆栈完整无缺，因为检查堆栈满的唯一方法是将其清空。

所以您需要做的是将弹出的成员存储到临时堆栈中。这不会改变总体空间需求，因为您仅将临时堆栈对象压入其他位置弹出的对象，因此可以满足O（1）备用需求。

这是迭代解决方案的伪代码：

function stacks_are_equal
  precondition: stacks s1, s2

  set equal? to true

  while s1 is not empty and s2 is not empty
    pop x from s1
    pop y from s2
    push x onto temp1
    push y onto temp2

    if x ≠ y then
      set equal? to false
      break out of loop

  if s1 is not empty or s2 is not empty set equal? to false

  while temp1 is not empty
    pop x from temp1
    pop y from temp2
    push x onto s1
    push y onto s2

  return equal?