C++ - Stack Pop() Function with Singly Linked list

Question

For starters this is apart of my current homework assignment for my Data Structures class. I am not asking for answers, I am asking for help.

I have a stack class that is implementing a Linked List instead of an array. I am currently trying to write my pop() function. I have a node for my theBack part of the stack.

I am just confused as to getting to the predecesor of my theBack node.

Any help with this would be awesome! Thanks!

Answer 1

A stack is actually reasonably simple to implement as a singly linked list, due to its restricted push and pop operations. It's actually a lot easier if you insert pushed elements at the head of the list. Since it's homework, I'll provide pseudo-code.

To initialise a stack, it's simply creating:

top -> null

with this code:

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

Pushing an item is actually inserting it at the start of the list. So, when you push 3, 4 and 5, you get:

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

with the following code:

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.

And popping is then just removing that first node.

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

if you're implementing a stack, then you would want to pop the top node anyways, so you would set theTop to be the next node in line (which should be a pointer in theTop node)

Answer 3

Each node in the singly-linked list links to the previous node. The very first item pushed onto the stack has a NULL, all the others point to the item 'below' them (the predecessor) in the stack.

So before you destroy the top node, you grab the backlink and save it as the new top. Something like this pseudocode, which presumes a stack of int values:

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;

If by "predecessor", you mean: "the thing that was popped before this": that's long gone, isn't it?

Answer 4

What do you mean the "predecessor" of top? Top node is the head of your list, it doesn't have any predecessors.