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

如何在O(1)中为LinkedStack编写pop()方法？
我的LinkedStack类中有两个私有(private)数据成员:ListNode* head和ListNode* tail。
head指向LinkedStack的开头，tail指向LinkedStack的结尾。
pop()将删除ListNode指向的tail，然后tail将指向 ListNode之前为的tail。

知道这一点后，我将如何在pop()中编写O(1)？显然，我可以编写一个for循环，在ListNode之前紧接先前的tail，但是pop()不会是O(1)。

由于这是用于家庭作业，因此我不是在寻找代码解决方案，而只是在正确方向上提供一些提示。

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

编辑2 :谢谢@ user4581301。 假定pop()为空时，不会调用LinkedStack。

最佳答案

如您陈述的那样，任何必须遍历列表以查找特定元素的情况都将使恒定时间要求无法满足。这包括一个单链列表，您可以在其中将项目推到最后。双链列表会更容易，因为您可以从尾到倒数第二项，而无需遍历。

但是，我不确定您为什么要坚持到底。如果要将新元素放在列表的最前面，则为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 -|