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
popcalls very unwieldy
It looks like new items are added to the end of the list, making the algorithm 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.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) ```