2
$\begingroup$

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)
```
$\endgroup$
  • 4
    $\begingroup$ The question is, what is this implementation supposed to illustrate? Clumsy linked-list C programming in Python? $\endgroup$ – Michel Billaud Apr 9 at 10:20
  • $\begingroup$ I think it's meant to illustrate how a stack works. Is it as bad as it seems for this purpose? $\endgroup$ – Robin Apr 9 at 10:49
  • $\begingroup$ Definitely. Why the heck use a linked list structure + free list inside a fixed size array (list), where an array + index of the top is sufficient - and is the most common low-level implementation? (better : with python use a list with append/pop docs.python.org/2/tutorial/datastructures.html) $\endgroup$ – Michel Billaud Apr 9 at 11:30
  • 1
    $\begingroup$ @MichelBillaud, given the source, I suspect it's clumsy linked-list Visual Basic code badly ported to Python. $\endgroup$ – Peter Taylor Nov 25 at 8:10
  • $\begingroup$ @PeterTaylor To me, it is written in a "Instructions as State Transformer" style, as the array and top/free list pointers are passed as parameters AND returned, instead of being encapsulated into an object. Also the original stack array is modified during the process, so it is not really functional style with immutable object. The question is: what point is this code supposed to support? $\endgroup$ – Michel Billaud Nov 25 at 9:43
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting. Heaps are not part of the syllabus and when I showed my students the code today they were totally baffled. It took me several hours of thinking and tracing to understand it myself. Since we are talking about A Level (pre university) study I think it's fair to conclude that the code is not level-appropriate. It would take considerable experience with a fairly low level language to be able to write this from scratch, which is one of the exercises in the text book. The question is - what can I do about it? Maybe just emphasize the key features and/or contact the exam board? $\endgroup$ – Robin Apr 9 at 13:08
  • 1
    $\begingroup$ I'm wondering where you found the code. $\endgroup$ – Buffy Apr 9 at 13:16
  • $\begingroup$ cambridge.org/gb/education/subject/computing/computer-science/… $\endgroup$ – Robin Apr 9 at 13:51
  • $\begingroup$ @ScottRowe, study a pure functional language an you will understand it. It is fundamental there. Or program in OO with a large proportion of immutable objects. $\endgroup$ – Buffy Apr 9 at 23:38
  • $\begingroup$ @Buffy Actually, the Push method modifies the content of the Stack array given as a parameter. $\endgroup$ – Michel Billaud Nov 25 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.