C++ - 使用单链接列表的Stack Pop()函数

Question

对于初学者来说,这是我目前的数据结构课程作业的一部分.我不是在寻求答案,我正在寻求帮助.

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

我很困惑到达我的theBack节点的前身.

任何帮助都会很棒!谢谢!

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.