我刚刚浏览了我大学提供的其中一门课程的幻灯片。
这是提到这个问题的幻灯片：http ://www.cse.psu.edu/~asmith/courses/cse565/F10/www/lec-notes/CSE565-F10-Lec-03.pptx.pdf
但是，我不确定我是否正确理解了这个问题，因此对解决方案也一无所知。
关于问题是什么以及如何考虑的任何指示？
问问题
177 次
3 回答
2
要模拟数组，您需要允许索引查找。
插入：
给定 2 个无界堆栈，将它们称为 foo 和 bar，最初您可以继续插入 foo。
抬头：
当用户尝试查找元素时，您只需将 stack.size - 索引时间弹出到栏中。下一个弹出窗口将为您提供用户正在寻找的元素。但是此时您可以进行 peek 而不是 pop，因为该数组不会在查找时删除其元素。
现在您可以将所有元素从 bar 推回到 foo 上，或者将其余元素从 bar 推到 foo 上。但在后一种情况下，您需要反转索引。
删除：
要实现删除，您只需将元素标记为已删除。如果用户尝试在该索引处插入元素，您可以弹出并推送新元素。而在查找时，您应该返回代表空索引的任何内容。
于 2013-10-07T04:38:22.817 回答
2
主要任务：
- 附加
- 移动
- 插入
- 索引查找
让我们将两个堆栈称为“S1”和“S2”
追加
添加一些东西，从 S2 弹出所有内容，将它们推送到 S1，然后将新值推送到 S1
流行音乐
从 S2 弹出所有内容，将它们推送到 S1，然后在 S1 上弹出最后一项
索引删除
将 S2 中的所有内容弹出到 S1。将第一个项目从 S1 弹出i到 S2。弹出 S1 的顶部。
插入
要在索引处插入i（基于 0），请将 S1 中的所有内容弹出到 S2 中，然后从 S2 中弹出第一个i项目并将它们推回 S1。现在将你的价值推到 S1 上。
索引查找
从 S2 中弹出所有内容并将它们推到 S1 上。现在从 S1 中弹出第一个i项目并将它们推入 S2。您要查找的项目应该是 S1 上的顶部项目。
笔记
通过跟踪总共有多少项目以及您当前所在的位置，可以大大简化 Pop-everything 和推送到另一个过程。如果您跟踪这两个（或反映这些的任何其他数字），那么您可以准确计算需要转移多少，而不是从头开始计数。
此实现不像“列表”实现那样是“数组”实现。它本质上是一个简化的链表（下一个节点位于当前节点的下方，前一个节点位于另一个堆栈的顶部），其中您拥有的唯一数据是当前节点。
于 2013-10-07T04:45:09.167 回答
1
将 bogo-index 和当前值保存在内存中，将较低索引的值保存在一个堆栈中，将较高索引的值保存在另一个堆栈中。要转到另一个索引，请继续从适当的堆栈中弹出并将当前值推送到另一个索引，然后递减/递增 bogo-index 直到它到达您想要的位置。如果你愿意，你可以用边界检查把它包起来。
于 2013-10-07T04:42:38.123 回答