Stacks

This post is best viewed using Crunchy.

Stacks

A stack is a simple but very useful data structure. As explained in Wikipedia.

In computer science, a stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. 

The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list. A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition: therefore, the lower elements are typically those that have been in the list the longest.

A stack is like a Python list, except that it has much fewer methods.
We can easily simulate a stack in Python as follows.

class Stack(object):
    def __init__(self, verbose=True):
        self.items = []
        self.verbose = verbose

    def push(self, item):
        self.items.append(item)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            if self.verbose:
                print("Attempted to pop element from empty stack.")
            raise


stack = Stack()     # stack = []
stack.push(1)       # stack = [1]
stack.push(2)       # stack = [1, 2]
print stack.pop()   # prints 2; stack = [1]
stack.push(3)       # stack = [1, 3]
print stack.pop()   # prints 3; stack = [1]
print stack.pop()   # prints 1; stack = []
print stack.pop()   # raises IndexError

Suggestions

• Try it out with various test cases.
• Try implementing a similar Stack class in another language.
• Read the Wikipedia article.

Testing video embedding.

This is a test to add a video preview of crst2s5.

Get the Flash Player to see this movie.

Original location: 'Crunchy'
at ShowMeDo from the Python category.

Crunchy is not dead ... far from it.

In spite of the lack of activity on this blog, Crunchy is alive and well.  As of today, Crunchy 1.0.1 has been released and soon version 1.1 should be released as well.  Please go to the main Crunchy site for up to date information.

Being labeled a spam blog

I have not been posting very often on this blog. Most of the "cute" tricks for Crunchy are incorporated in the documentations if and when I find them. While this blog is rather unknown, and has never attracted a comment, it has attracted Google's attention in an unwanted way. Google labeled this blog as a spam blog - probably because of the combination of a relatively small number of posts and comparatively large number of links. This is the second time (that I notice) it has done so. When this happens, it becomes impossible to post anything. To revert the rating, which is done through an automated process, I had to contact Google so that a real human could take a look at it. Within about 24 hours, they reverted the status so that I could post. The first time, I felt I had nothing useful to post so I did nothing, hoping that my blog would somehow be white-listed. The second time ... lead to this post.

So, to quote Monty Python: "Move along, there is nothing to see...". Hopefully, there soon will be :-)

Unending loops and the magic of threads.

Many months ago, I started this blog with a test post using the simplest possible template that I could find with blogger, hoping that Crunchy would be able to handle it. Alas, that was not the case.

Now that Crunchy can handle this blog (and much more), it is perhaps time to start again with a small but non-trivial example that illustrates some aspect of threads and infinite loops. I'm assuming you are viewing this blog using Crunchy, otherwise what I will be describing will simply not work.

Imagine you have a simple program such as the following:

>>> import time
>>> a = 1
... while a == 1:
...   print "-",
...   time.sleep(1)
...

How long will it take before this program ends? The answer is, of course, never. Such a program includes an infinite loop. Try typing it in the above interpreter to see it in action.

Crunchy is running this program in a separate thread, which allows you to continue using Crunchy while the program is running. Furthermore, the "Borg interpreter" used by Crunchy above has been designed so as to share its state with all other such interpreter (hence the name "Borg"). To see this, try using the interpreter below, running in a separate thread, to change the value of a.

>>> a = 0

If it does not work the first time (you may be getting a syntax error with Crunchy 0.9x), try it again. Eventually, it will allow you to break out of the seemingly infinite loop above.
====
Update: When you enter "a=0" the first time, the syntax error that it gives is due to the fact that the Borg interpreter is taking input assuming that you are still in the body of the while loop - therefore, it expects the code to be indented. If you write "a=0" in the second interpreter with the same indentation as you used in the original loop, you will see that you get Python's continuation prompt (...). Press "enter" a second time and you will get out of the loop; you may have to wait a few seconds to see the result.

An alternative to avoid the syntax error is to enter "break" in the second interpreter, with the same indentation as used in the loop, and pressing "enter" a second time. Then you can proceed with typing "a=0" in that second interpreter and everything will be fine.

Note: do not simply press "enter" first in the second interpreter, thinking that this will break out of the loop: it won't. In fact, this will result in the second interpreter being stuck in the loop. The only way out will be to reload the page and start from the beginning.

Testing Crunchy

The intention behind this blog is to post Crunchy ready Python tutorials. In this first blog, I will start with the simplest possible test, that of embedding a Python interpreter.

print "Hello world!"

If this works, it will be a lot of fun!