Pedagogical issues with Stack Implementation

Question

I am new to teaching the particular syllabus I have been asked to teach and I am confused by the approach given for several of the algorithms. For example the stack implementation based on the course materials given below seems very convoluted. I'm curious to hear if others would share my concerns if they had to teach about stacks in this way, or if they can offer any insight into the advantages of this approach.

The concerns I have which I'm curious to hear your opinion about are:

• Using the call by reference approach makes the push and pop calls very unwieldy

• The algorithm appears to be O(n) rather than O(1)

• The algorithm is hard to follow (IMO)

• It is possible to implement a stack in a much simpler fashion, which would allow student to focus more on conceptual understanding of the behavior and use of stacks, and to see the link between the concept and the implementation more clearly.

# NullPointer should be set to -1 if using array element with index 0
NULLPOINTER = -1

#Declare record type to store data and pointer
class Node:
        def __init__(self):
                self.Data = ""
                self.Pointer = NULLPOINTER

def InitialiseStack():
        Stack = [Node() for i in range(8)]
        TopOfStack = NULLPOINTER  # set start pointer
        FreeListPtr = 0  # set starting position of free ist
        for Index in range(7):
                Stack[Index].Pointer = Index + 1
        Stack[7].Pointer = NULLPOINTER  # last node of free list
        return (Stack, TopOfStack, FreeListPtr)


def Push(Stack, TopOfStack, FreeListPtr, NewItem):
        if FreeListPtr != NULLPOINTER:
        # there is space in the array
        # take node from free list and store data item
                NewNodePtr = FreeListPtr
                Stack[NewNodePtr].Data = NewItem
                FreeListPtr = Stack[FreeListPtr].Pointer
                # insert new node at top of stack
                Stack[NewNodePtr].Pointer = TopOfStack
                TopOfStack = NewNodePtr
        else:
                print("no space for more data")
        return (Stack, TopOfStack, FreeListPtr)


def Pop(Stack, TopOfStack, FreeListPtr):
        if TopOfStack == NULLPOINTER:
                print("no data on stack")
                Value = ""
        else:
                Value = Stack[TopOfStack].Data
                ThisNodePtr = TopOfStack
                TopOfStack = Stack[TopOfStack].Pointer
                Stack[ThisNodePtr].Pointer = FreeListPtr
                FreeListPtr = ThisNodePtr
                return (Stack, TopOfStack, FreeListPtr, Value)

def OutputAllNodes(Stack, TopOfStack) :
        CurrentNodePtr = TopOfStack # start at beginning of list
        if TopOfStack == NULLPOINTER :
                print("No data on stack")
        while CurrentNodePtr != NULLPOINTER : # while not end of list
                print(CurrentNodePtr, " ",Stack[CurrentNodePtr].Data)
        # follow the pointer to the next node
                CurrentNodePtr = Stack[CurrentNodePtr].Pointer

Stack, TopOfStack, FreeListPtr = InitialiseStack()
Stack, TopOfStack, FreeListPtr = Push(Stack, TopOfStack,
FreeListPtr, "first item")
Stack, TopOfStack, FreeListPtr = Push(Stack, TopOfStack,
FreeListPtr, "second item")
Stack, TopOfStack, FreeListPtr = Push(Stack, TopOfStack,
FreeListPtr, "third item")
Stack, TopOfStack, FreeListPtr, value = Pop(Stack, TopOfStack, FreeListPtr)
print(value)
OutputAllNodes(Stack, TopOfStack)
```

Answer 1

Actually, the code is terrible, but I don't think its purpose is to illustrate a stack so much as to illustrate in a very rudimentary way how heap allocation works. (Worse than "terrible", it isn't "pythonic").

But you are wrong about the efficiency. Only the initialize function is O(n). Push an pop are O(1) as should be obvious.

But no serious code should print as a solution to a failure condition. The program itself should fail in some predictable way. Likewise no general implementation of a stack should hard code the maximum size. As such, this code teaches very bad programming habits.

The reason I don't think it is intended to represent a stack structure is the tuples that are returned from push and pop. Normally push is a mutator returning nothing and pop is an accessor returning only the top value in the stack.

Also, a stack as an abstraction should encapsulate the free list pointer (i.e. next free slot if any) and this reveals it.

The capitalization of variables is also oddly done for a Python program.

I agree that it is hard to follow, but that is a consequence of the above.

One thing positive that I will say about the code and how it might be actually valuable pedagogically, has to do with a philosophical interpretation.

When you modify a stack (or anything, really), one way to think of it is that you have a different stack - a new thing that didn't exist before. This code emphasizes that view of mutation. So to push onto a stack, you supply a stack, etc, and you get back a stack. A stack goes in and a stack comes out, a conceptually new thing.

So, it works if that is your main lesson, but less so as a stack per se.

But it is valuable only if you want to emphasize that view of mutation. But this is at odds with the normal (philosophical) view of an encapsulated data structure - that its identity is maintained in the face of change.

However, it is valuable for students to consider both views as different programming languages stress one over the other. Haskell, for example, has the "new value" idea built in rather than the "modified value" that you normally see in OOP. In Haskell if you push onto a stack, you get back a stack.

---

I'll also note that there is a Pedagogical Pattern called Toy Box that suggests that one can introduce a complex topic with a trivial implementation that get across key ideas without going into the complexity. While I might prefer simpler code to show how a heap grabs blocks but must know where they are, this code might be considered an example of a Toy.

Another pedagogical pattern is called Spiral and implies that teaching can introduce simple versions of complex topics early before students are ready for the full explanation. Then later, when it is time to learn it in detail (another loop in the spiral) they have been primed to integrate it into their thinking.