C++ - 使用单链表的Stack Pop（）函数

Question

对于初学者来说，这是我目前为我的数据结构类做的家庭作业的一部分。我不是在寻求答案，而是在寻求帮助。

我有一个实现链接列表而不是数组的堆栈类。我目前正在尝试写我的pop()函数。我有一个节点用于我的theBack部分。

我只是感到困惑，以得到我的theBack节点的predecesor。

任何帮助，这将是太棒了！谢谢！

Answer 1

由于受限制的推送和弹出操作，堆栈实际上很容易实现为单向链表。如果您在列表的首部处插入推送元素，实际上会更容易。由于它是作业，我会提供伪代码。

初始化堆栈，它只是创造：

top -> null 

与此代码：

def init (stk): 
    stk->top = null     # just initialise to empty. 

推的项目在列表的开始实际插入它。所以，当你把3，4和5，您可以：

 +---+ 
top -> | 3 | -> null 
     +---+ 
     +---+ +---+ 
top -> | 4 | -> | 3 | -> null 
     +---+ +---+ 
     +---+ +---+ +---+ 
top -> | 5 | -> | 4 | -> | 3 | -> null 
     +---+ +---+ +---+ 

用下面的代码：

def push (stk, val): 
    item = new node      # Create the node. 
    item->value = val     # Insert value. 
    item->next = stk->top    # Point it at current top. 
    stk->top = item      # Change top pointer to point to it. 

和弹出，然后只是除去第一个节点。

def pop (stk): 
    if stk->top == null:    # Catch stack empty error. 
     abort with "stack empty" 
    first = stk->top     # Save it for freeing. 
    val = first->value     # Get the value from the top. 
    stk->top = first->next    # Set top to the top's next. 
    free first       # Release the memory. 
    return val       # Return the value. 

Answer 2

如果你实现一个栈，那么你会想反正弹出顶级节点，所以你会设置theTop成一直线的下一个节点（这应该是在theTop节点的指针）

Answer 3

每单链表中的节点链接到前一个节点。被推入堆栈的第一个项目有一个NULL，所有其他项都指向堆栈中它们（前任）下面的项目。

因此，在您销毁顶层节点之前，您需要获取反向链接并将其保存为新顶端。事情是这样的伪代码，它假定int类型的堆栈：通过“前身”

pop() 
    ALink *poppedLink = myTop; 
    myTop = poppedLink.nextNode; // point to next node 

    int returnValue = poppedLink.value; // save the value 
    delete poppedLink; // destroy the instance 

    return returnValue; 

如果，你的意思是：“这是在此之前弹出的东西”：这是早就没了，是不是？

Answer 4

你是什么意思的顶级“前任”？顶级节点是你的列表的头，它没有任何前辈。