单链表的C++堆栈POP()函数

由于堆栈的推送和弹出操作受到限制,它实际上相当容易实现为单链表。实际上,如果在 头 名单上的。既然是作业,我就提供伪代码。

要初始化堆栈,只需创建:

top -> null

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

推一个项目实际上是在 开始

       +---+
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.

单个链接列表中的每个节点都链接到上一个节点。推送到堆栈上的第一个项有一个空值,所有其他项都指向堆栈中它们(前一个)下面的项。

因此,在销毁top节点之前,先获取反向链接并将其保存为新的top。类似于这个伪代码,它假定一堆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;

如果说“前任”,你的意思是:“在此之前被爆出的东西”:那早就过去了,不是吗?

你说托普的“前任”是什么意思?顶部节点是列表的头部,它没有任何前置节点。