<p>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"). </p>

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

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

<p>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 <em>only</em> the top value in the stack. </p>

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

<p>The capitalization of variables is also oddly done for a Python program. </p>

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

<p>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. </p>

<p>When you <em>modify</em> 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. </p>

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

<p>But it is valuable <em>only</em> 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. </p>

<p>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. </p>

<hr>

<p>I'll also note that there is a <a href="https://rads.stackoverflow.com/amzn/click/com/1479171824" rel="noreferrer" rel="nofollow noreferrer">Pedagogical Pattern</a> called <em>Toy Box</em> 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. </p>

<p>Another pedagogical pattern is called <em>Spiral</em> 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. </p>

CC BY-SA 4.0
2019-04-09T13:08:13.257Z
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?
Robin Andrews
CC BY-SA 4.0
2019-04-09T13:16:37.807Z
I'm wondering where you found the code.
Buffy
CC BY-SA 4.0
2019-04-09T13:51:21.457Z
https://www.cambridge.org/gb/education/subject/computing/computer-science/cambridge-international-and-a-level-computer-science
Robin Andrews
CC BY-SA 4.0
2019-04-09T23:38:15.043Z
@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.
Buffy
CC BY-SA 4.0
2019-11-25T09:47:23.637Z
@Buffy Actually, the Push method modifies the content of the Stack array given as a parameter.
Michel Billaud
CC BY-SA 4.0
2019-11-25T11:40:17.157Z
@MichelBillaud, Conceptually the stack is "new", since it is returned from push. There is a mismatch between the interface protocols and the implementation. Nothing in the interface guarantees the stack returned is the same as the argument. Another flaw in the code, actually.
Buffy
CC BY-SA 4.0
2019-04-09T11:44:16.867Z
2019-04-09T12:54:32.713Z
2019-04-09T12:54:32.713Z
Buffy
<p>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.</p>

<p>The concerns I have which I'm curious to hear your opinion about are:</p>

<ul>
<li><p>Using the call by reference approach makes the <code>push</code> and <code>pop</code> calls
very unwieldy</p></li>
<li><p>The algorithm appears to be O(n) rather than O(1)</p></li>
<li><p>The algorithm is hard to follow (IMO)</p></li>
<li><p>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.</p></li>
</ul>

<pre class="lang-py prettyprint-override"><code># 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)
<span class="math-container">```</span>
</code></pre>

CC BY-SA 4.0
2019-04-09T10:20:25.897Z
The question is, what is this implementation supposed to illustrate? Clumsy linked-list C programming in Python?
Michel Billaud
CC BY-SA 4.0
2019-04-09T10:49:07.550Z
I think it's meant to illustrate how a stack works. Is it as bad as it seems for this purpose?
Robin Andrews
CC BY-SA 4.0
2019-04-09T11:30:22.900Z
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 https://docs.python.org/2/tutorial/datastructures.html)
Michel Billaud
CC BY-SA 4.0
2019-11-25T08:10:49.650Z
@MichelBillaud, given the source, I suspect it's clumsy linked-list *Visual Basic* code badly ported to Python.
Peter Taylor
CC BY-SA 4.0
2019-11-25T09:43:28.613Z
@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?
Michel Billaud
<algorithms><python>
Pedagogical issues with Stack Implementation
# Pedagogical issues with Stack Implementation

(Asked by: username_0 on 2019-04-09)

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)
```

**Tags:** algorithms, python

> **Comments:**
> **username_1**: The question is, what is this implementation supposed to illustrate? Clumsy linked-list C programming in Python?  
> **username_0**: I think it's meant to illustrate how a stack works. Is it as bad as it seems for this purpose?  
> **username_1**: 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 https://docs.python.org/2/tutorial/datastructures.html)  
> **username_2**: @MichelBillaud, given the source, I suspect it's clumsy linked-list *Visual Basic* code badly ported to Python.  
> **username_1**: @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?  

---

## 1 answers

### Answer by username_3 on 2019-04-09. Score: 9

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](https://rads.stackoverflow.com/amzn/click/com/1479171824) 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.

> **Comments:**
> **username_0**: 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?  
> **username_3**: I'm wondering where you found the code.  
> **username_0**: https://www.cambridge.org/gb/education/subject/computing/computer-science/cambridge-international-and-a-level-computer-science  
> **username_3**: @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.  
> **username_1**: @username_3 Actually, the Push method modifies the content of the Stack array given as a parameter.  
> **username_3**: @MichelBillaud, Conceptually the stack is "new", since it is returned from push. There is a mismatch between the interface protocols and the implementation. Nothing in the interface guarantees the stack returned is the same as the argument. Another flaw in the code, actually.  

---

