Stacks (theory and Python implementation)
In this article, we will talk about a simple but very useful data structure called Stack. Stacks, like simply linked listed, we analyzed in the previous article, are data structures that help us to develop algorithms with better performance as far as time complexity. In the next lines, we will have the opportunity to discuss the theory behind the stack data structure, to see the main operations, and of course to make implementation in Python programming language. We will do that in three ways, using python lists, simply linked lists, and finally using the deque module. After that, we will see together a real-world example. So let’s start.
Description
A stack, like a simply linked list, is a linear data structure that follows the LIFO (Last In First Out) prinical. So, the last element inserted in the data structure is removed first. To visualize a stack, image you have a pile of plates on top of another. If you want to add a new plate, you put it at the top of the pile. Similarly, if you want to remove a plate you will remove the plate at the top of the pile. So, if you want to take the last plate of the pile, you must remove all the other places.
Operations
The main operations are performed in a stack are the following:
- Push: Add a new element to the top of the stack.
- Pop: Remove the element from the top of the stack.
- IsEmpty: Check if the stack has any elements or not.
- Top: Get the value of the element on the top without removing that element.
Implementation of Stack using Python List
In the following example, we create a stack using Python List, with the end of the list as the head (top) of the stack. So let’s see the code below:
Implementation of Stack using Simply Linked List
In the previous article, we learned about simply Linked List. Now, we can use them in order to create a stack. In this case, all the new nodes (elements) will be added at the front of the linked list like the image below:
You can see the code below:
Implementation of Stack using deque module
Another way to create a stack is using the deque. Deque (double-ended queue) is a specific object in the collections module that you can use for linked lists. In the following example, we will add and pop elements to the right of the deque.
Example
To wrap up, we will see together a simple example. Suppose we want to find errors in the usage of different types of brackets in a text. The input text can contain any brackets from the set {}, [], (). The idea to solve this problem is to use a stack to push opening brackets like {, [, and (. Then for each character equal to closing brackets }, ], ) pop the element of the stack. If the two elements match ((), {}, []), then check the following elements until the end of the text. If we find a symbol that does not match, then we stop the procedure and return ‘Failure’. In the end, we check if the stack is empty so we return ‘Success’, otherwise we return ‘Failure’. That’s because, if we have a non-empty stack at the end of the procedure, means that an opening bracket has been found but not the equal closing bracket. See the whole code below:
Conclusion
In this article, we talked about Stack data structure. Stacks are really useful in many cases, as can help us to solve complicated problems in an elegant way. In the future, we will have the opportunity to discuss about other data structures like queues, trees, etc. Until then keep learning, and keep coding. Thanks for reading.
