0

我正在做一个处理 2 个堆栈的练习堆栈问题。堆栈 S 和堆栈 T 并且它希望我们基本上进行一个称为底部的新操作，该操作返回但不删除 s 的底部元素。所以我对问题的分解以及如何去做是首先用元素填充堆栈 S。接下来是用堆栈 S' 的所有元素填充堆栈 T，但顺序相反，这样现在底部在顶部。我的问题是我知道如何创建初始堆栈 S，但我不知道如何以相反的顺序填充堆栈 T。另外，运行时间是多少，因为它会反过来？

4

2 回答 2

2

如果你反复从堆栈 S 中弹出元素并在弹出时将它们推入堆栈 T，那么当 S 为空时，T 将包含以前在 S 中的内容，但顺序相反。

  S      T

| 1 |  -----
| 2 |
| 3 |
-----

T.push(S.pop())=>

  S      T

| 2 |  | 1 |
| 3 |  -----
-----

T.push(S.pop())=>

  S      T

| 3 |  | 2 |
-----  | 1 |
       -----

T.push(S.pop())=>

  S      T

-----  | 3 |
       | 2 |
       | 1 |
       -----

运行时间将与 S 中的元素数量成线性关系。

于 2013-10-23T01:48:55.747 回答
0

堆栈 S 和堆栈 T，它希望我们基本上进行一个名为 bottom 的新操作，该操作返回但不删除 s 的底部元素

我看不出如何在不违反Stack操作基础的情况下直接完成。您应该让用户查看的唯一内容是堆栈顶部的元素。

如果您想让用户看到底部的内容，您将需要另一个堆栈，您可以从 S 中推送所有弹出的元素。然后，这个新堆栈顶部的东西就是堆栈底部的东西S。

现在，这似乎导致了您的第二个问题，不是吗？

因此，考虑这个可能的解决方案：
1. 您将有一个名为int pushInto(Stack S,Stack T)
2. 当用户想要查看堆栈 S 的底部元素时，调用此方法。
3. 然后这个方法会返回栈顶的元素，即 S 的底端。
4. 这个方法需要和方法一起使用：int getBottomElement(Stack S)
我想用一块石头打两只鸟

于 2013-10-23T01:55:17.360 回答