A Stack is a data framework used to store Last-In / First-Out fashion items that are popularly referred to as LIFO. It is unlike the First-In / First-Out (FIFO) queue. The key to understanding stack is to think about it in any text editor like the undo app. You’re editing a Python script, for example. You’ve added a new feature. This means adding to the undo stack a new item.
There is an operation to insert a function in the stack. After adding the feature, you can delete a word from a post. Even the undo stack is added to this deletion. Each new command is placed at the top as these commands are stored in the undo stack. The inclusion of new items is referred to as Push when interacting with the stacks.
Download Detailed Brochure and Get Complimentary access to Live Online Demo Class with Industry Expert.
Now, all these changes you want to undo, so you give the undo button. It will take most of the element in the stack, in this case indenting the post, and delete it from the stack. The editor must undo the indent and the undo stack now contains just two objects.
This operation is the exact opposite of push and is named as Pop. When you give the undo command again, the next item on the stack will get popped off.
Once the stack is empty, giving the undo command will have no effect as the stack will be empty. Here is how you can implement a Python stack:
When you try to implement a Python stack, you have to consider a couple of options. Here we will be focusing on using the data structures provided by the Python library instead of using any third-party packages or writing your own.
List
When you are building a stack, the most frequently used data structure in the program is the built-in list. For adding new elements to the stack, you have to use .append() instead of .push(). For removing the elements in the order of LIFO, you have to use .pop().
The major operations that you can do on a stack through lists are:
1. Pushing an element
2. Popping an element
3. Getting the stack’s size
4. Printing all the items present in the stack
Take a look at the following example:
class Stack: #Constructor creates a list def __init__(self): self.stack = list() #Adding elements to stack def push(self,data): #Checking to avoid duplicate entries if data not in self.stack: self.stack.append(data) return True return False #Removing last element from the stack def pop(self): if len(self.stack)<=0: return ("Stack Empty!") return self.stack.pop()
#Getting the size of the stack def size(self): return len(self.stack) myStack = Stack() print(myStack.push(5)) #prints True print(myStack.push(6)) #prints True print(myStack.push(9)) #prints True print(myStack.push(5)) #prints False since 5 is there print(myStack.push(3)) #prints True print(myStack.size()) #prints 4 print(myStack.pop()) #prints 3 print(myStack.pop()) #prints 9 print(myStack.pop()) #prints 6 print(myStack.pop()) #prints 5 print(myStack.size()) #prints 0 print(myStack.pop()) #prints Stack Empty! Here is another example of Python’s implementation of stack using lists: >>> >>> 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 As you can see in the above code, an IndexError was raced after the final command was executed because the stack was empty and you can’t call a .pop() on an empty stack.
The best advantage of using list for implementing a stack in Python is that it is familiar. If you have any previous experience as a programmer, you must be familiar with lists and how they can be used in a program.
However, when compared to other data structures, there are a few shortcomings of using list as a data structure for implementing stack. The main issue is the issue of speed it faces as the list expands. The goal of storing items in a list is so that it can provide fast access to random elements. This means that at high level, all these items are stored adjacent to each other in memory.
When the stack gets bigger than the block of memory holding it currently, there are some memory allocations done by Python. This means that execution of .append() call will take much longer than usual. Another less serious problem is that adding an element in the stack at other than the last position takes a significantly longer amount of time. The issue of reallocation is fixed by the next data structure.
Collections.queue
Deque is present in the collections module and is used to create Python stacks. It stands for double ended queue. The same .append() and .pop() operations are used on the deque. Take a look at the following example:
>> >>> 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
This example must look similar to the example of list. This begs the questions as to why there was a need for two data structures that have the same implementation. There is a reason behind this.
As mentioned before, list is built on contiguous memory’s blocks. This means that all the items present in the list are stored next to each other. This adjacent storing of items works great for operations like list indexing.
For example, getting the third item on the list through myList[2] will not take much time as Python will know exactly where it has to search in memory to get the item. This layout of the memory also facilitates allowing of slices to work on lists.
The contiguous memory layout is also the reason why the .append() operation takes more time in lists. When the contiguous memory block gets full, a new block is needed which makes the .append() operation take even more time.
Dequeu is based on the doubly linked list. When it comes to the structure of the linked list, every item has its own memory block and a reference to the next item in the list. A doubly linked list also has the same features except one difference where each item has a reference to the next as well as previous item of the list.
So addition of a node to either end of the list is easier as compared to other types of data structures. When you add a new item to a linked list, the only thing you have to do is to set the reference of the new item to the top of the stack and then point the stack’s top to the new item.
However, this addition and removal of items from the stack has a trade-off. Now when you have to get the 4th item from the list, it will take a longer time than it took for a list. This is because now Python will have to walk through every item of the list to get to the fourth one.
Luckily, this random slicing and indexing is very rare on a stack. Push and Pop make up the majority of the stack operations. This also makes deque one of the best choices for implementation of Python stack.
Array
For the agnostic implementation of Stack, you have to use arrays. The only difference here is that unlike lists, arrays have a fixed size. Also, there is a top pointer that is used for keeping a tab on the stack’s status. Here is an algorithm that can be used for implementing Python stack using arrays:
1. The first step is declaring an integer with the name MaxSize that represents the stack’s maximum size and a list.
2. Set the top to 0.
3. This step is performing the Push operation. For this, you need to:
⇒ Check if the Stack’s MaxSize is more than the Top.
⇒ If no, print the message stating that stack is full.
⇒ If yes, then add the data to stack and increase the top by 1.
4. Next is implementing the pop operation. Follow these steps:
⇒ Check is top is more than 0 or not.
⇒ If no, print the message stating that stack is empty.
⇒ If yes, remove the last item from the list and decrease top by 1.
5. For getting the size of the stack, you just need to get the value of the top pointer.
Take a look at the following code:
class Stack:
#Constructor def __init__(self): self.stack = list() self.maxSize = 8 self.top = 0
#Adds element to the Stack def push(self,data): if self.top>=self.maxSize: return ("Stack Full!") self.stack.append(data) self.top += 1 return True
#Removes element from the stack def pop(self): if self.top<=0: return ("Stack Empty!") item = self.stack.pop() self.top -= 1 return item #Size of the stack def size(self): return self.top s = Stack() print(s.push(1))#prints True print(s.push(2))#prints True print(s.push(3))#prints True print(s.push(4))#prints True print(s.push(5))#prints True print(s.push(6))#prints True print(s.push(7))#prints True print(s.push(8))#prints True print(s.push(9))#prints Stack Full! print(s.size())#prints 8 print(s.pop())#prints 8 print(s.pop())#prints 7 print(s.pop())#prints 6 print(s.pop())#prints 5 print(s.pop())#prints 4 print(s.pop())#prints 3 print(s.pop())#prints 2 print(s.pop())#prints 1 print(s.pop())#prints Stack Empty!
Stacks and Threading
Python stacks have also found application in multi-threaded programs. If your program has threads, the lists and dequeue options will behave differently. For starters, for any data structure to which multiple threads have access, list shouldn’t be used.
Deque is a little more complicated. The .append() and .pop() operations involved in the deque are atomic in nature which means a different thread can’t interrupt them. So, you will be thread use if you use only the .append() and .pop() operations.
However, if there are other methods in the class, especially the ones that are not designed specifically to be atomic, then deque is not thread-safe. So, if you are using deque for creating a Python stack that is thread-safe, you are exposing yourself to cause race conditions and misuse it in the future.
So now that list and deque are out of the options for building Python stack for a threaded program, what can you do? The answer is queue.LifoQueue, present in the queue model.
Just like list and deque, LifoQueue uses .get() and .put() for adding and removing items from the stack:
>>> >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/Python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/Python3.7/queue.py", line 167, in get raise Empty _queue.Empty
LifeQueue is completely thread-safe meaning you can use all its methods for creating a safe threaded environment. There is also an option of adding timeouts to the operations which is a must-have feature for threaded programs. But, there is a cost to this full thread safety. To get this safety, each operation requires a little extra work meaning it takes longer time to execute. However, this will not slow down the speed of your entire program. You can carefully make a switch to deque if you have discovered that the stack operations are bottleneck and measured the performance of the program.
Which implementation should be used?
If you are not threading, you should go for the deque data structure. Use the LifQueue if you have to use threading unless you are willing to take the maintenance risks in exchange for a small increase in speed for popping and pushing items by measuring the performance of the program.
You might feel comfortable using lists for implementing stacks but it is usually avoided by developers due to the issues of memory reallocation. Both lists and deque have the same interface and deque doesn’t have the memory reallocation issues which makes it the best option for implementing non-threaded Python stack.
Now that you know what stack is and how you can implement it, you will be able to select the right implementation method for your problem.
Final Thoughts
With taking a Python course, you can become a Python coding language master that will not only enhance your resume value but will also ensure a better career.
