From LiteratePrograms

Other implementations: C | Java | Python

Overview

A simple Stack in Python, implemented as an object-oriented, recursive data structure, a singly linked list. Note that Python's built-in list structure can already be used as a stack, using the "append()" and "pop()" methods.

Implementation

The Stack consists of two classes: the stack, which has a head element and the element, which has a next element, visualized by the following UML class diagram.

The stack has a head element and three methods: push, for adding to the stack, pop, for retrieving and removing items and empty to test if the stack is empty.

• Push: add an element at the beginning (prepend), by setting the head to the new element and the next element to the old head:

<<push>>=
def push(self, element):
    self.head = Element(element, self.head)

• Pop: return the reference to the first element in the stack, removing it from the stack by setting the head to the next element.

Note: When the stack is empty, we return "None" here. This is potentially ambiguous to the user, because since "None" is a valid value, it could be that there was an actual item of value "null". We could have alternately returned an exception.

<<pop>>=
def pop(self):
    if self.empty(): raise EmptyStackException
    result = self.head.value
    self.head = self.head.next
    return result

• Empty: return true if the stack is empty, indicated by an empty head:

<<empty>>=
def empty(self):
    return self.head == None

Usage

• Sample usage: push some elements onto the stack. Pop them from the stack while it isn't empty. The effect of this is that the order is reversed (LIFO):

<<usage>>=
stack = Stack()
elements = ["first", "second", "third", "fourth"]
for e in elements:
    stack.push(e)
result = []
while not stack.empty():
    result.append(stack.pop())
assert result == ["fourth", "third", "second", "first"]

• The complete program:

<<stack.py>>=
class EmptyStackException(Exception):
    pass
class Element:
    def __init__(self, value, next):
        self.value = value
        self.next = next
class Stack:
    def __init__(self):
        self.head = None
    push
    pop
    empty
if __name__ == "__main__":
    usage

Download code