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

你是什麼意思的頂級「前任」？頂級節點是你的列表的頭，它沒有任何前輩。