data-structures - 检查两个堆栈在 O(1) 空间中是否相等

Question

我在面试中被问到这个:

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

堆栈应保持其早期状态(元素顺序)。

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

我的一位 friend 建议使用 String 变量并将一个堆栈中的元素附加到其中，然后将弹出的内容推送到另一个堆栈，然后从 S2(S1 的旧元素)推送到 S1，并对 S2 执行相同的操作。但这取决于堆栈的大小，因为字符串会根据堆栈的大小而增长。

Answer 1

递归 vs 迭代不是这里的问题。问题是如何保持堆栈完好无损，因为检查完整堆栈的唯一方法是清空它。

所以您需要做的是将弹出的成员存储到临时堆栈中。这不会改变整体空间需求，因为您只需要压入在其他地方弹出的临时堆栈对象，因此您可以满足 O(1) 的备用需求。

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

<b>function</b> stacks_are_equal
  <b>precondition</b>: stacks <i>s1</i>, <i>s2</i><br/>
  <b>set</b> <i>equal?</i> to true<br/>
  <b>while</b> <i>s1</i> is not empty and <i>s2</i> is not empty
    pop <i>x</i> from <i>s1</i>
    pop <i>y</i> from <i>s2</i>
    push <i>x</i> onto <i>temp1</i>
    push <i>y</i> onto <i>temp2</i><br/>
    <b>if</b> <i>x</i> ≠ <i>y</i> then
      <b>set</b> <i>equal?</i> to false
      <b>break</b> out of loop<br/>
  <b>if</b> <i>s1</i> is not empty or <i>s2</i> is not empty <b>set</b> <i>equal?</i> to false<br/>
  <b>while</b> <i>temp1</i> is not empty
    pop <i>x</i> from <i>temp1</i>
    pop <i>y</i> from <i>temp2</i>
    push <i>x</i> onto <i>s1</i>
    push <i>y</i> onto <i>s2</i><br/>
  <b>return</b> <i>equal?</i>

这是递归的解决方案:

<b>function</b> stacks_are_equal(<i>s1</i>, <i>s2</i>)
  <b>if</b> <i>s1</i> is empty and <i>s2</i> is empty <b>return</b> true
  <b>if</b> <i>s1</i> is empty or <i>s2</i> is empty <b>return</b> false<br/>
  pop <i>x</i> from <i>s1</i>
  pop <i>y</i> from <i>s2</i><br/>
  <i>empty?</i> := <i>x</i> = <i>y</i> and stacks_are_equal(<i>s1</i>, <i>s2</i>)<br/>
  push <i>x</i> onto <i>s1</i>
  push <i>y</i> onto <i>s2</i><br/>
  <b>return</b> <i>empty?</i>