Pedagogical issues with Stack Implementation
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.