你能用 O(1) 的运行时间翻转堆栈吗？

Question

我正在构建一个使用双向链表构建堆栈的程序。我需要以 O(1) 的运行时间翻转堆栈或反转堆栈的顺序。例如：

1 -> 2 -> 3 -> 4

变成

4 -> 3 -> 2 -> 1

我能想到的最快方法是使用 O(N) 作为运行时。由于被要求使用 O(1) 的运行时，所有循环都是不可能的，因为它们都将不可避免地取决于堆栈中的节点数。

有人可以推荐一种合理的方法来解决这个问题吗？

Answer 1

只需将方向标志全局存储到列表中，并翻转它以翻转列表的方向。将您的列表节点定义为：

struct node {
    struct node *link[2];
    bool *dir;
};

每个节点的dir指针应指向bool整个列表共享的单个对象（例如，在单独分配的内存中）。然后，无论您通常访问p->nextor 的地方p->prev，p->link[*p->dir]还是p->link[!*p->dir]分别访问or 。现在，你可以通过反转方向标志翻转prev和next整个列表的意义：*p->dir = !*p->dir;。

请注意，在每个节点中存储一个指针是有成本的，您可以通过将标志单独保持在“带外”来避免这种情况，但这限制了您只能访问列表（至少在了解当前方向的情况下）拥有带外信息；然后你不能只从列表中的一个成员开始。