Saturday, April 24, 2010

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.