Python is one of the most versatile and fastest-growing programming languages as of the late 2010s. From web development to machine learning, from app-building to data analytics, Python wears many feathers in its cap. This has led to Python becoming an ecosystem of ambitious developers, who share information and developments with each other. However, to become fluent in technology, one has to master certain aspects, such as solving stack in Python.
For those who might have lost touch with their computer science fundamentals, ‘stack’ is one of the most common data structure concepts that talks about data being inserted and removed from a ‘pipeline’ of sorts made from continuous pieces of data put together.
Here’s an interesting fact about Stacks in Python:
The use of stack in Python is not just limited to applications like web-development and creating complex applications, but they are also actively used in robotics.
In this guide, we are going to talk about the concept of stack and queue in general and then help you understand how to solve stack and queue in Python.
Understanding A Stack Before Solving Stack In Python
Implementing a stack program in Python becomes quite easy if we are able to understand the basic concept of a stack. A stack is a type of data structure that stores data items in the last in-first out method. This method is popularly known as LIFO, in short. This is very much the opposite of the method of a queue, which utilizes the first in-first out method, also known as the FIFO.
The closest practical example for understanding stack implementation in Python comes in the form of the Undo feature that comes as a part of your text editor.
So, as a programmer, we’ll assume that you are editing a Python file and you add a new function, which will add a new item to your ‘undo stack’ :
We have two undo stacks in this stack implementation in Python, namely, the before and the after. So when we add the Add Function to the stack, it gets added to the after stack since it’s the first thing that we have brought in.
Download Detailed Brochure and Get Complimentary access to Live Online Demo Class with Industry Expert.
Now after adding the add function, you want to delete a word from the comments. This action, annotated as Delete Word also gets added to the undo stack and is placed on the top of it:
Then, you indent a comment which is annotated by Indent Comment which is then placed on the top of the after undoing stack:
These actions of adding new actions to the ‘after stack’ are called push.
So after carrying out these actions, you want to undo these actions. Therefore, when you will undo your actions, the text editor is going to do it starting from the immediate last action and going further back from there onward. This action in data structures jargon is called pop.
When you carry out the pop action, the item in the after the stack is taken off and added to the before stack. The process keeps going on as you pop three items one after the other. As a result, the before undo stack gets emptied:
Now that the given stack implementation in Python is empty, performing the undo operation is not going to have any effect on the stack
Practical Uses Of Stack Programming
Stack implementation is carried out for any process where data points need to be stored one after the other for the execution of one event. And what could be a better example than a game? Let’s take the example of a fighting game where the character makes a move which is a result of multiple keypress inputs. The value of these input keys can be stored in the form of a stack.
A stack in Python can also be used for carrying out undo operations as we talked about earlier in the discussion. The undo operations use after and before stacks where actions can be pushed to, stored and removed as soon as their utility becomes redundant.
The back button in web browsers also uses the concept of a stack in Python. Think it this way. You visit web page 1, then web page 2 and then web page 3 and so on. If you click the back button on your browser, you will follow the reverse of the above-given order. Therefore, the browser would need to store the information of the web pages in a stack that will enable it to access these pages in reverse order.
Understanding The Method For Solving Stack In Python.
When carrying out stack implementation in Python there are a couple of methods, however, we are going to cover only the basics which will be enough. Therefore, we will be using data structures which are a part of the Python library, instead of writing our own packages or using the third-party ones.
These implementations for stack in Python are:
- List
- Collections.deque
- queue.LifoQueue
List, one of the most commonly used Python data structures is used for creating a Python stack. This is because the functions in Python that come close to push and pop are used with lists in Python. While the append() function adds new elements to the list, the pop() function removes elements from the list.
While programming for the stack implementation in Python, you will notice that if you attempt to call the pop() function on an empty stack, it will show you an error (which is quite common for a stack and queue in Python).
However, it’s important at this point to mention why the list has its own merits (and certain demerits) is being used as the primary data structure for executing a stack program in Python.
First and foremost, it provides the advantage of being familiar since you, as a Python programmer has used it in various of your programs.
On the other hand, this leads to a trade-off with the execution speed of your code. This won’t happen in the beginning, but rather with the rapid growth of the program. This is so because the items are stored next to each other in the memory allocation which makes a stack in Python carry out memory allocation procedures, which makes calling the append() function take longer than calling other functions.
If you are thinking that you can get around this issue by using the insert() function, you are in for a disappointment since using this function will take much longer.
Solving Stack In Python With The Help Of collections.deque
Python comes ready with the collections module which contains the dequeue() function which can be used for creating Python stacks. With the function, you can use the same old methods used in the above explanations:
>>> myStack = []
>>> myStack.append('a')
>>> myStack.append('b')
>>> myStack.append('c')
>>> myStack
['a', 'b', 'c']
>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'
>>> myStack.pop()
Traceback (most recent call last):
File "<console>", line 1, in <module>
IndexError: pop from empty list
In the above code, you get an error, when you call the pop() function on an empty stack.
The code is more or less the Python-based rendition of the above. However, some might have a question at the back of their minds that why would the Python team create two data structures that are so alike?
Dequeue v/s List: What Separates Them?
As mentioned above, the data structure List is built on blocks of memory adjacently placed to each other or stored next to each other.
And this method for stack and queue in Python works very well for a lot of operations such as indexing a List. Say, for example, fetching a list element in theList[2] is a quick process as Python knows where to look in the memory in order to find it. It also works for slicing data items in a List.
However, the continuous nature of the memory layout can also be the reason for the append() method taking more time for some data items than others. So if the block of memory is full, the program will need to get another block, which will take longer for the .append() function to execute.
On the other hand, dequeue utilizes the doubly linked list for its core operation. While in a linked list structure, every slice of memory stored in the memory block references the next entry in the list, a doubly-linked list does the same, except that it references both the previous as well as the next entry in the list.
This allows programmers to add nodes to either end of the said list. Adding a new data into the linked list requires you to only set the reference to the new entry to point toward the current top of the stack, which will then point to the top to a new entry.
However, this process of addition and removal of data on a stack comes with its share of trade-off. Fetching myDequeue[3] is slower than it was for a list since Python needs to check each and every node of the list to get to the third element.
However, you won’t be doing much slicing and indexing on any stack program in Python, and most of your operations are going to be push or pop.
In conclusion, we can say that the frequent use of the .append() and .pop() operations make dequeue the best choice when implementing a stack in Python in the absence of threading in your code.
Using Threading In Python Stacks
A stack in Python can prove to be very useful in multi-thread programs. So far, you have seen that the data structures List and Deque function differently when your program utilizes threads. However, the most important caveat to remember here is that you should never use lists with any data structure which is accessible by multiple threads because Lists are not ‘thread-safe’.
Deque, on the other hand, is complex and hence safer. Deque documentations highlight the atomicity of the .append() and .pop() functions, which means that there would be no interference by another thread.
So you can say that if you will be using only the functions .append() and .pop(), for your stack program in Python is going to be thread-safe.
However, despite Deque being compatible with multi-threading, the concern remains that other functions in the program do not comply with the atomicity principle or being thread-safe.
So even if it is possible to create a thread-safe stack in Python using deque, it opens up the possibility of someone misusing the feature and thus leading to race conditions.
Now, it has been established that you cannot use List if you are threading in a stack, and nor using deque would be tamper-proof, so what could be the right way to create a stack in Python for a program with threading feature?
Simply use the queue module and LifoQueue function in it. Simply put, this is Last-in First-out method. LifoQueue, instead of using .pop() and .append() functions, uses .put() and .get() functions to put and remove data from the given stack:
>>> from collections import deque
>>> myStack = deque()
>>> myStack.append('a')
>>> myStack.append('b')
>>> myStack.append('c')
>>> myStack
deque(['a', 'b', 'c'])
>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'
>> myStack.pop()
Traceback (most recent call last):
File “<console>”, line 1, in <module>
IndexError: pop from an empty deque
With the Traceback error, the code resembles our previous code.
As compared to the deque, LifoQueue is completely thread-safe. All its functions can be safely used in a threaded programming environment. It also offers time-outs to its processes which are identified to be absolutely necessary features in threaded programs.
Total Thread Safety At The Expense Of Time
But as we know that any improvement in safety comes at a price, mostly with the time. To be thread-safe, LifoQueue has to do more computations, which means that it takes longer.
However, this increase in program execution speed won’t matter to your general program speed. If you discover that your stack operations are causing a bottleneck, you can move to deque though.
So What Implementation To Use For Python Stacks?
To get straight to the point, you should go for deque if your programming does not involve threading. However, if you are going to use threading, you should use LifoQueue, but not if you have done some performance measuring and discovered that boosting your push and pop operations will result in maintenance risks.
The list may provide the feature of familiarity, however, if it increases issues with memory reallocation, it should be avoided. And given that deque and List interfaces are similar, deque doesn’t suffer from these problems.
Given these conditions, it seems that the deque is perhaps the best choice for executing stack in Python in a non-threaded environment.
For those who are new to Python programming basics & solving stack in Python, here’s a video for beginners that introduces the concept.
Concluding Points
We are sure that by now you must be clear about what a stack is and how it works. In this discussion, we have compared three options used for implementing stacks and so far arrived at the conclusion that the deque method is better than LifoQueue and List (but only for non-threaded Python programs).
However, if you are using a threading environment while doing stack and queue in Python, it would be wise to go for LifoQueue.
With a substantial amount of experience and Python Programming course, one can also become a certified trainer in Python or an entrepreneur.
