The Stack Data Structure in Python

The stack is a wonderfully simple data structure which despite its simplicity makes many powerful algorithms possible.

Some of the uses for a stack data structure in software development are:

  • The Depth-First Search Algorithm
  • Reverse Polish Notation for evaluating arithmetic expressions
  • Syntax parsing for compilers and interpreters
  • Storing function call frames inside the CPU
  • Matching parentheses/braces in IDEs
  • Reversing the order of data
  • Recursion
  • Undo/redo operation in word processors and browsers
  • Low-level/assembly programming

Stacks are a very important data structure in programming and Computer Science. Think of a stack of plates. The top plate is the only easy access point, whether you want to add a new plate or remove an existing one… This leads to to the idea of a Last In First Out data structure.

A stack is a LIFO data structure – last in, first out.

You will see in this article how this essential property is useful.

The fundamental operations associated with the stack data structure are:

  • push(item) – push item to the top of the stack
  • pop() – Remove & return the top item

There are other methods too, which we will look at later, but push and pop are the essential, signature methods of a stack.

We use the term top to refer to the “access point” of the stack – i.e. the place where we either add or remove items. This is purely a conceptual tool though. In practice a stack is likely to be implemented using an array or list, both of which tend to be thought of a horizontal. It is an implementation detail as to whether the left- or right-hand end of a list/array is used as the top.

A Simple, Practical Implementation of a Stack in Python.

If you are more concerned about using a stack than in the details of its implementation, you can just go ahead and use a Python list, just being careful to only add or remove items from one end. An example is give below.

What do you expect the output to be?

A couple of points about the above code:

  • We use a Python list as the basis for our stack
  • The top of the stack is the right-hand end of the list
  • The pop() list operation does two things: it removes the item at the top of the stack, AND returns it.

As a side note, do you think this version using for instead of while would work in the same way?

A Python Class to Represent the Stack Data Structure

We are now going to write Python class to represent a stack for learning purposes, because the abstraction is helpful for gaining a deep understanding of how the data structure works, including using the appropriate terminology, such as push and pop. In practical situations, you might just use a list as described above. However, there is another reason to us a more detailed implementation such as a Python class. If your code needs a stack and you provide a list, there’s nothing stopping another programmer from calling insert, remove or other list functions that will affect the order of your stack! This fundamentally ruins the point of defining a stack, as it no longer functions the way it should.

Here is a Python class you can use for a stack, which abstracts the implementation details behind semantically named methods.

Reversing a String Using a Stack in Python

One of the natural uses of a stack is to reverse data. You can see why if you get a bunch of plates, stack them on top of each other and then remove them one-by-one from the top. We are going to write a Python program to use this property of stacks to reverse the characters in a string.

Here’s a template for you to try to write this algorithm for yourself. You will only need the push and pop operations, but of course in the right place and with the right values. The goal is to reverse string and print the result. If you run this code in the same file as the Stack class from above, you will have access to that class. Otherwise you will need it import it using from stack import Stack.

Array Based Implementation of the Stack Data Structure

Depending on why you are learning about stacks (for example it may be as part of a course such as A Level Computer Science in the UK), you may need to know how to implement a stack inside of an array, as opposed to using a dynamic data structure such as a Python list which resizes to fit your requirements. This can be done in different ways which entail varying levels of complexity and provide varying levels of pedagogical value depending on the context.

A common approach used by A Level exam boards is demonstrated by the code below. This approach involves keeping track of the position of the top and bottom of the stack using external “pointers” (not actual pointers as in C for example, but variables containing the index positions.

A Really Complex Implementation of a Stack in Python

If you are a fan of complexity for complexity’s sake and/or your exam board has decided that you should do it this way, there is another approach which involves storing the pointer to the next position inside the array as a data attribute, alongside the data “cargo”. I will post an example of this for reference, but with the caveat that I don’t believe it is a suitable approach for students at A Level and certainly doesn’t help them with understanding the abstract part of the topic called Abstract Data Types. There is some commentary on the pedagogical issues with this approach on the CS Educators Stack Exchange site.

This has been an introduction to the stack data structure in Python. I hope you found it helpful. Any questions or comments, please put them in the comments section below and I will try to address them.

Happy computing!

Leave a Reply

Your email address will not be published. Required fields are marked

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}