Stacks in Python
A Stack
A stack is a standard computer science data structure that can be described as LIFO (Last In First Out). We "stack" each data item on top of the previous one (actually this is just a convenient mental model we use to visualise what's going on).
Picturing them as a stack of plates where we can only get to the top plate is a good analogy, for how stacks work.
Source:
Wikimedia Commons
Stack Class Description
There are some standard methods that a stack is expected to do (we'll use standard names for them):
- Stack() this will call the constructor to create a new empty stack object and return it.
- push(item) add the item that is passed in as an argument to the "top" of the stack.
- pop() remove the top item from the stack and return it. The stack will no longer contain this top item.
- peek() return the top item from the stack but don't remove it. The stack remains unchanged.
- is_empty() will return True or False depending on whether there are any items on the stack.
- size() returns the number of items currently on the stack.
We're going to use a list to hold the items on the stack, in this version but we could use any other suitable structure that will keep the order of the items (as an exercise we could use the linked list we will create later).
Exercise
Create a Stack class with each of the methods described above, but just insert the keyword pass as the contents of each method body for now.
For the body of the constructor method, create an empty list and assign it to an attribute of the class. This sounds complicated but actually just means, do the following:
self.contents = []Implement the other methods in a similar fashion.
- push(item) can just use the python append command to add it to the list.
- pop() can just use the python pop command to remove and return the last item from the list.
- peek() just look at the last item in the list, but don't change the list.
- size() can just return the length of the list.
- is_empty() can be implemented in various ways.
Once we have the stack implemented, we need to test that it works by creating a stack, pushing stuff on to it, popping stuff off it, checking if it is empty, checking the size etc.
Stacks are a useful structure, we can use them for a variety of things. Your history in your internet browser is implemented as a stack, the undo command in various applications uses a stack, whenever you call a new function in python the previous function's data is pushed onto a stack when the function completes then the previous function's data is popped back off the stack.
There's a Python file of this class including some code to test it out here: Daves Stack
My name is Dave Ames. I've been a teacher for 25 years and for the last few of those I've been teaching both children and other adults, especially teachers to program in a variety of environments, but mostly Python.
This is the first of a series of posts I'm going to be posting, on Data Structures in Python. This one is actually part of the content of a workshop I'm delivering to some teachers tomorrow.