c++ - 我们可以在 O(1) 时间内反转一个堆栈吗

Question

我必须在 O(1) 或恒定时间内反转堆栈。它是一个通常的基于“数组”的堆栈类，带有 push、pop 和 top 方法；其中必须添加额外的公共(public)逆转方法。反转方法必须在不固定的时间内工作才能实现反转。可以使用队列来实现这个目标，因为问题提示使用循环数组来实现这个目标？它是一个作业问题.. 任何提示？

Answer 1

您可以设计一个在恒定时间内可逆的堆栈，但是有许多堆栈需要 O(N) 时间来反转。例如，如果堆栈中的每个节点仅包含数据和指向下一个(朝向底部)元素的指针，则堆栈为 N。节点有 N要更改的指针，因为每个节点的“下一个”关系都在变化。
当所有 N节点需要改变，这个过程是(至少)O(N)。
要使堆栈在恒定时间内可逆，您可以使用双向链表并跟踪当前向下的方向。使用此设置，您可以通过翻转“向下的方向”标志来反转堆栈。请注意，这种方法会增加大多数其他堆栈操作的开销，因为每次需要查找“下一个”节点时都需要检查标志，例如在推送或弹出时。