Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-09T13:08:13.257Z
Answers.Text: 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?
Answers.UserDisplayName: Robin Andrews
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-09T13:16:37.807Z
Answers.Text: I'm wondering where you found the code.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-09T13:51:21.457Z
Answers.Text: https://www.cambridge.org/gb/education/subject/computing/computer-science/cambridge-international-and-a-level-computer-science
Answers.UserDisplayName: Robin Andrews
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-09T23:38:15.043Z
Answers.Text: @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.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T09:47:23.637Z
Answers.Text: @Buffy Actually, the Push method modifies the content of the Stack array given as a parameter.
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T11:40:17.157Z
Answers.Text: @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.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-09T11:44:16.867Z
Answers.LastActivityDate: 2019-04-09T12:54:32.713Z
Answers.LastEditDate: 2019-04-09T12:54:32.713Z
Answers.UserDisplayName: Buffy
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-09T10:20:25.897Z
Comments.Text: The question is, what is this implementation supposed to illustrate? Clumsy linked-list C programming in Python?
Comments.UserDisplayName: Michel Billaud
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-09T10:49:07.550Z
Comments.Text: I think it's meant to illustrate how a stack works. Is it as bad as it seems for this purpose?
Comments.UserDisplayName: Robin Andrews
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-09T11:30:22.900Z
Comments.Text: 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)
Comments.UserDisplayName: Michel Billaud
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-25T08:10:49.650Z
Comments.Text: @MichelBillaud, given the source, I suspect it's clumsy linked-list *Visual Basic* code badly ported to Python.
Comments.UserDisplayName: Peter Taylor
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-25T09:43:28.613Z
Comments.Text: @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?
Comments.UserDisplayName: Michel Billaud
Tags: <algorithms><python>
Title: Pedagogical issues with Stack Implementation
ThreadText: # 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.
  
  ```py
  # 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**: @username_1, given the source, I suspect it's clumsy linked-list *Visual Basic* code badly ported to Python.  
  > **username_1**: @username_2 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**: @username_1, 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.  
  
  ---
  
  