单链表实现栈时,如何正确移除本栈中存在于给定目标栈的元素
问题根因定位
- 比对逻辑完全偏离需求:你最初的需求是「删除当前栈中所有值存在于目标栈的元素」,但实际代码是对齐两个栈的栈顶位置逐一比对,只有位置刚好匹配、值相等的元素才会被跳过存回原栈,根本没有判断元素是否在目标栈的任意位置存在。结合测试用例,两个栈的对齐比对过程中没有一次值相等,所有元素都被存入临时栈s1,最后全部压回原栈,结果自然和初始状态完全一致。
- 循环条件设计错误:循环设置了
!this.isEmpty() && !s.isEmpty()的停止条件,只要两个栈任意一个被弹空就终止流程,根本没有遍历到两个栈的全部元素。 - 存在严重副作用:代码全程对传入的目标栈
s执行pop操作,最后没有将其恢复到初始状态,外部调用时会发现传入的s被完全清空,这是违反方法设计常识的。 - 相等判断的潜在bug:如果栈内存储的是包装类型对象,使用
!=比较只会判断对象引用是否相同,当数值超出基础类型缓存范围时,会出现值相等但判断不相等的误判。
正确实现思路
全程遵循栈的操作规则,不依赖其他线性结构,贴合栈练习的学习目标,通过多临时栈中转的方式完成需求,核心步骤:
- 中转保存目标栈的元素,同时恢复原目标栈状态:
- 建两个临时栈:
tempRestore用来还原目标栈的状态,targetValues用来存储所有需要删除的目标值。 - 循环弹出传入栈
s的栈顶元素,每弹出一个值,就依次压入targetValues和tempRestore,直到s被弹空。 - 循环弹出
tempRestore的所有元素压回s,此时s就完全恢复到方法调用前的状态,targetValues中完整留存了所有需要匹配的删除值。
- 建两个临时栈:
- 遍历当前栈筛选需要保留的元素:
- 建临时栈
tempKeep用来存放需要保留的元素。 - 循环弹出当前栈
this的栈顶元素,每弹出一个值currentVal,就检查它是否存在于targetValues中:- 建临时栈
tempCheck来辅助比对,全程不打乱targetValues的原有顺序:依次弹出targetValues的元素压入tempCheck,期间如果发现元素和currentVal相等,标记为「需要删除」。 - 比对完成后,把
tempCheck的所有元素压回targetValues,恢复其原有状态。 - 如果
currentVal没有被标记为需要删除,就把它压入tempKeep;如果需要删除,直接跳过即可。
- 建临时栈
- 直到当前栈
this被完全弹空为止。
- 建临时栈
- 还原当前栈的顺序:
- 把
tempKeep里的所有元素依次弹出压回this,因为tempKeep里的元素是逆序存储的,压回后就能保持当前栈原本的元素顺序。
- 把
修正后的代码示例
public void deleteEqualToOther(Stack s) { Stack tempRestore = new Stack(); Stack targetValues = new Stack(); // 保存目标栈所有值,同时为恢复s做准备 while(!s.isEmpty()) { Object val = s.stackTop(); s.pop(); targetValues.push(val); tempRestore.push(val); } // 恢复目标栈s到调用前的原始状态 while(!tempRestore.isEmpty()) { s.push(tempRestore.stackTop()); tempRestore.pop(); } Stack tempKeep = new Stack(); // 遍历当前栈,筛选需要保留的元素 while(!this.isEmpty()) { Object currentVal = this.stackTop(); this.pop(); boolean needDelete = false; Stack tempCheck = new Stack(); // 检查当前值是否在目标删除集合中 while(!targetValues.isEmpty()) { Object targetVal = targetValues.stackTop(); targetValues.pop(); tempCheck.push(targetVal); // 使用equals做值比对,避免引用比较的问题 if(currentVal.equals(targetVal)) { needDelete = true; } } // 恢复targetValues的原有状态,不影响下一次比对 while(!tempCheck.isEmpty()) { targetValues.push(tempCheck.stackTop()); tempCheck.pop(); } // 不需要删除的元素存入保留栈 if(!needDelete) { tempKeep.push(currentVal); } } // 将保留的元素压回当前栈,恢复原有顺序 while(!tempKeep.isEmpty()) { this.push(tempKeep.stackTop()); tempKeep.pop(); } }
按照你的测试用例,修正后运行的预期结果为:原s1中的2、4元素因为存在于目标栈s2中会被删除,最终s1仅保留1、-5两个元素,display时会按栈顶到栈底的顺序输出-5、1。
内容的提问来源于stack exchange,提问作者Parasite
相关产品推荐
相关产品推荐

