This is a series of articles in which I will teach you data structures and algorithms in python. There will be 10 articles in total published right here on substack. So please consider subscribing to my newsletter, so you can read all of the published articles.
These data structures will be introduced and challenged:
Stacks
Singly Linked Lists
Circular Linked Lists
Doubly Linked Lists
Arrays
Binary Trees
Binary Search Trees
It is important to note that this article requires basic Python knowledge.
Let’s get started! I hope you have a great experience that enhances your problem-solving skills regarding data structures and algorithms in Python.
Stack
The stack data structure and its Python implementation will be discussed in this part.
Stacks — what are they?
To begin with, let me explain what a stack is. Namely, it is a concept that should be familiar to most people.
Consider the following four titles for four riveting books:
A
B
C
D
We want to stack up these books neatly because they are currently strewn across the floor.
The books are now neatly stacked! We can take a book from the top of the stack if we want to retrieve it. As you can see, it can be a bit risky to take a book from the bottom and we don’t want to topple the entire stack if we do so. The top book in the stack of books will therefore be taken down, and we will continue to read it or do whatever we wish with it.
For instance, let’s say we want to take Book A out of the stack. As it stands, it is at the bottom of the stack, so we need to take Book D, put it on the bottom of the stack, and then we need to do the same for Book C and Book B before we can take out Book A.
It is important to understand what a stack is and how it works. You’ll most likely be familiar with the physical stack used to keep data structures. A data structure stack is very similar to that. In our example stack, we were able to place a book in it, which is a programming artefact, and we were able to use this data structure to store any programming artefact, variable, or object.
Stack Operations
Push
There is an operation called push which allows elements to be inserted into a stack. The book is pushed onto the previous top element in the stack when it is pushed onto the stack, so when the book is pushed onto the stack, it becomes the new book’s top element. In other words, we push elements onto a stack when we use the push operation to add them to a list. In this process, elements are placed onto a stack, and the last element to be added to the stack is what becomes the new top of the stack.
Pop
The stack can also be used for another type of operation, which is popping. It is the process of taking the book which is at the top of the stack and placing it at the bottom of the stack. This means that when an element is removed from the stack, the stack then follows the rule that the elements are removed in the order they were added. In other words, when we perform the pop operation, we are removing the top element, the last one to be inserted, during the process.
In order to create this data structure, we are going to need two basic routines called Push and Pop.
Peek
Secondly, we can also look at the top element of the stack, which will allow us to ask the data structure: “What is the top element of the stack?” and it can give that to us using the peek operation. There is no removal of the top element when the peek operation is done, it simply returns the top element.
The stack can also be checked to see if it is empty as well, and we can do a few other things as we go along, in the process of implementing the code.
My next step is to create a stack class and then initialize a Python list as part of the constructor of that class. We’re looking for a combination of things that is available in the Python list, and that is going to make it easier for us to tweak Python’s implementation of the list in order to make it more similar to what we would expect in a stack, namely, push and pop operations.
This is an empty list that I’m assigning to a class variable called items. Now let’s create the push method using self.items, which is created when we create a stack object:
An item will be passed as an argument to push, which is a member of this class. That item is the book in our example. This is done by pushing or putting the book’s name at the top.
Appending an item to a Python list is done using the append method. This is exactly what we want to do in the push method for our stack.
The second method that needs to be implemented is pop. Python makes this very easy as well, since we’re based on a list. The last element inserted into the list is returned by the pop method implicitly.
I’m going to do a test drive before we add a few more methods.
Get_stack() is a method we make. Stacks consist of a list of items, which form the core. In lines 18–19, I push A and B onto the stack after defining a stack object, myStack. MyStack is output as [‘A’, ‘B’] after these operations. The stack starts with A at the bottom, and it culminates with B at the top. In line 21, we push C, which results in [‘A’, ‘B’, ‘C’], meaning C is at the top.
We have a solid understanding of the stack’s core fundamentals. Additionally, we can include a method called is_empty in this, which would be helpful. If the stack is empty, it will return true.
The stack is empty at this point, so we get True here. Calling is_empty() on something pushed should return False. Feel free to give it a try.
Our stack of items now has the topmost element, which we can find out by the peek operation on line 17 of the code.
Using the code above, when peek is called on the stack, it should return D in the code above. On line 18, peek tests whether the stack isn’t empty, and if it isn’t, it returns the last element of the list, in this case, the top element of the stack. The last element of the list is the last element of the stack if it is not empty. On line 19, we return the last item in the list, which is self.items[-1] for Python, which is the last item in the list. As a result, at first, Python assumes that D is at the top of the stack, and hence, D is the element that comes up first.
It is important to note that in the previously implemented methods, you can also check whether or not the stack is empty. In order to keep things as simple as possible, this step has been omitted from the other methods in order to keep things simple.
Create a stack object by going ahead and doing so. In addition to letters and strings, you could also push numbers if you wish, so it doesn’t matter what you push, you just have to push something. Get a sense of how this data structure works by playing with it for a while and getting a feel for it. My next lesson will be in about a week, so I will see you then.
Check to see if brackets are balanced
In this lesson, we are going to take advantage of the stack data structure that we defined in the previous lesson in order to investigate whether or not a set of brackets is balanced or not.
First of all, let’s understand what it means to have a set of brackets that is balanced.
There are two types of balanced brackets: one is a set of brackets that matches both the number and type of opening and closing brackets, and the other is a set of brackets that is nestled properly within the string of brackets as well.
Balanced bracket examples
{ }
{ } { }
( ( { [ ] } ) )
Unbalanced bracket examples
( ( )
{ { { ) } ]
[ ] [ ] ] ]
Algorithm
You can get a better understanding of how we will solve this problem by looking at the slides below.
In addition to what was shown above, our algorithm consists of the following steps:
There are a number of characters in the string that we iterate through.
In the event that an opening bracket is received, it should be pushed onto the stack.
If we come across a closing bracket in the stack, we need to pop off an element from the stack and find an element that matches the closing bracket. We conclude it is a successful match if it is an opening bracket, and if it is also of the same type as the closing bracket, then we move on to the next step. As a result, if it’s not, we will conclude that there is not an equal number of brackets in the set.
If the brackets are balanced, the stack will be empty at the end of the iteration. If they are unbalanced, we will still have some elements in the stack.
Let’s move on to a special case now that we’ve covered the balanced and unbalanced bracket examples.
Cases of special importance
An example would be: ))
Can we pop off an element from the stack if we encounter a closing bracket without any elements? In the above example, we do not encounter an opening parenthesis, but rather a closing parenthesis. There is no balance in the use of brackets in this string. In order to avoid an empty stack, we need to ensure that our implementation does not contain an empty stack.
Let’s walk through the Python implementation now that you have a good understanding of the algorithm.
Is_paren_balanced is the first function we should look at:
Explanation
As you can see on lines 2–4, we declare a stack called s and two variables called index and is_balanced, both set to True.
When is_balanced equals True and the index is less than the length of parent-string, the while loop will execute. Our program will exit the while loop if any of the conditions are false. By indexing over each character in the paren_string with the index variable, we iterate over each character in the paren_string and save it in the paren variable.
On line 8, we check whether stop is an opening bracket and if it is, we push it onto the stack. We set is_balanced to False if the opening brackets aren’t any type of opening bracket. As discussed in the previous section, this handles our special case.
It is possible to pop off the top element if the stack does not contain an empty element, and then we need to check if the current parent, which is a closing bracket, matches the type of the top element, which is supposed to be an opening bracket. We update the value of is_balanced to False if the types do not match.
In order to perform the next iteration, we have to increment the index. If the index is equal to or greater than the length of paren_string or if is_balanced is False, the while loop keeps executing until the index equals or exceeds the length of paren_string.
Upon exiting the while loop, on line 21, we check if the stack is empty, and determine if it is balanced by checking if is_balanced is True, at this point we return True. We return False if the condition is not met.
You were introduced to an algorithm and the code given above is a simple implementation of it.
Is_match can now be implemented as follows:
This function evaluates whether p1 and p2 are valid brackets given two characters as input. The opening bracket in p1 must be an opening bracket, while the closing bracket in p2 must be the corresponding closing bracket. Our return value is False if p1 and p2 do not meet any of the valid conditions.
It’s easy peasy, isn’t it?
In the following, we present the entire implementation for determining whether bracket usage in a string is balanced. You are welcome to experiment with it!
Reverse String
A string can be reversed very easily in Python. Consider, for instance,
The following algorithm can be used for reversing a string if you need to use a stack:
Algorithm
Don’t you think the algorithm is pretty straightforward? When we pop the characters off the stack, they are arranged in reverse order because they are placed on the stack First-In, Last-Out.
We are now left with only coding the algorithm shown above. It’s time to get started!
In the file stack.py, we have provided the stack implementation from our first lesson. Feel free to experiment with the code below:
Explanation
In the code above, there is a reverse_string function that we will discuss in more detail. In the for loop on line 3, each character in input_str is iterated over and pushed onto the stack through the for loop. As a result, we create rev_str to be an empty string, and then we initialize it. Upon removing all the elements from the stack, we append them to rev_str and wait until it becomes empty, at which point the while loop is terminated, and all the elements are appended to rev_str one by one. On line 9, we are returning the rev_str back to the caller.
Convert Decimal Integer To Binary
This exercise is under paid subscription, so please consider subscribing.