c++ - 在 O(1) 中为 LinkedStack 编写 pop() 方法

Question

如何在 O(1) 中为 LinkedStack 编写一个 pop() 方法？我的 LinkedStack 类中有两个私有(private)数据成员:ListNode* head 和 ListNode* tail。

head指向LinkedStack的开头，tail指向LinkedStack的结尾。

pop() 将删除 tail 指向的 ListNode，然后 tail 将指向ListNode 之前 tail。

知道了这一点，我将如何在 O(1) 中编写 pop()？显然，我可以编写一个 for 循环，在 tail 之前获取前一个 ListNode，但是 pop() 不会是 O(1).

由于这是家庭作业，我不是在寻找代码解决方案，只是寻找正确方向的提示。

编辑:我可能看到的一种解决方案是使用 ListNode* prev 数据成员，它始终指向 tail 之前的前一个 ListNode。但我觉得有一种更有效的方法....

Edit2:谢谢@user4581301。 假设 LinkedStack 为空时不会调用 pop()。

Answer 1

如您所说，任何您必须遍历列表以定位特定元素的情况将使常数时间要求无法满足。这包括一个单链表，您可以在其中将项目推到最后。 双向链接列表会更容易，因为您可以从尾部到达倒数第二个项目而无需遍历。

但是，我不确定您为什么要坚持到最后。如果您要将新元素推送到列表的前面，实现push 和pop 的恒定时间是微不足道的。

我的意思是(伪代码，因为正如您提到的，“这是作业”):

def push(x):
    allocate node          # get new node and set data.
    node.data = x

    node.next = head       # insert at head of list
    head = node

def pop():
    assert head != null    # catch pop on empty stack

    node = head            # get first node and data
    retval = node.data

    head = head.next       # set head to be second node

    free node              # free node and return data
    return retval

可以看到这两个操作都没有遍历链表。首先，将 7 压入质数堆栈:

Starting list:
    head
        \
         5 -> 3 -> 2 -|

Create new node, point to current head:
     head
         \
     7 -> 5 -> 3 -> 2 -|

Point head at new node:
    head
        \
         7 -> 5 -> 3 -> 2 -|

现在让我们弹出相同的值。

Starting list:
    head
        \
         7 -> 5 -> 3 -> 2 -|

Save head as node, and value to return (7):
    head
        \
         7 -> 5 -> 3 -> 2 -|
        /
    node

Adjust head:
         head
             \
         7 -> 5 -> 3 -> 2 -|
        /
    node

Free node and return stored value (7):
    head
        \
         5 -> 3 -> 2 -|