Stack in Python: How, why and where?

Hey there, you might have landed here searching for Stack in Python, well, we have got it sorted for you. In this blog, we will be conducting an in-depth analysis of HOW, WHY and WHERE to use Stack in Python. 

The blog consists of the following topics:

• What is Stack in Data Structures?
• Why and When do we use stacks?
• How can we implement a stack in Python?
• A simple program to illustrate Stack in Python.
• More about the usage of Stacks in Python and related programs
• The list Built-in
• The collections.deque Class
• The queue.LifoQueue Class

What is Stack in Data Structures?

Data structures are the key to organize storage in computers so that we can efficiently access and edit data. Stacks is one of the earliest data structures defined in computer science. In simple words, Stack is a linear collection of items. It is a collection of objects that supports fast last-in, first-out (LIFO) semantics for insertion and deletion. It is an array or list structure of function calls and parameters used in modern computer programming and CPU architecture. Similar to a stack of plates at a restaurant, elements in a stack are added or removed from the top of the stack, in a “last in, first out” order. Unlike lists or arrays, random access is not allowed for the objects contained in the stack.

There are two types of operations in Stack-

• Push– To add data into the stack.
• Pop– To remove data from the stack.

Stacks are simple to learn and easy to implement, they are extensively incorporated in many software for carrying out various tasks. They can be implemented with an Array or Linked List. We’ll be relying on the List data structure here.

Why and When do we use Stack?

Stacks are simple data structures that allow us to store and retrieve data sequentially.

Talking about performance, a proper stack implementation is expected to take O(1) time for insert and delete operations.

To understand Stack at the ground level, think about a pile of books. You add a book at the top of the stack, so the first one to be picked up will be the last one that was added to the stack.

There are many real-world use cases for stacks, understanding them allows us to solve many data storage problems in an easy and effective way.

Imagine you’re a developer and you are working on a brand new word processor. You need to create an undo feature – allowing users to backtrack their actions until the beginning of the session. A stack is an ideal fit for this scenario. We can record every action of the user by pushing it to the stack. When the user wants to undo an action they can pop accordingly from the stack.

How can we implement a stack in Python?

In Python, we can implement python stacks by:

1. Using the built-in List data structure. Python’s built-in List data structure comes with methods to simulate both stack and queue operations.
2. Using the deque library which efficiently provides stack and queue operations in one object. 
3. Using the queue.LifoQueue Class.

As mentioned earlier, we can add items to a stack using the “PUSH” operation and remove items using the “POP” operation. 

PUSH Operation

Push – adds an element at the top of the stack. Refer the below image for more understanding:

POP Operation

Pop – removes an element from the top of the stack. 

Here is a simple program to illustrating Stack in Python- 

class Stack
def_init_(self):
self.items=[]
def is_empty(self):
		return self.items==[]
	def push(self, data):
		self.items.append(data)
	def pop(self):
		return self.items.pop()
s= Stack()
while True:
	print(‘push<value>’)
	print(‘pop’)
	print(‘quit’)
do= input(‘What would you like to do?’).split()
operation= do[0].strip().lower()
if operation== ‘push’:
s.push(int(do[1]))
elif operation== ‘pop’:
	if s.is_empty():
		print(‘Stack is empty’)
	else:
		print(‘Popped value:’, s.pop())
elif operation==’quit’:
break

More about Usage of Stacks in Python and related programs

Stacks provide a wide range of uses in algorithms, for eg, in language parsing and run-time memory management (“call stack”). A short and useful algorithm using a stack is a depth-first search (DFS) on a tree or graph data structure. Python plays with several stack implementations and each has slightly different characteristics. Let’s take a brief look at them:

 The list Built-in

Python’s built-in list type makes a decent stack data structure as it supports push and pop operations in amortized O(1) time.

Python’s lists are implemented as dynamic arrays internally which means they occasionally need to resize the storage space for elements stored in them whenever they are added or removed. The storage space is allocated more than required, so that not every push or pop requires resizing and you get an amortized O(1) time complexity for these operations.

Although this makes their performance less consistent than the stable O(1) inserts and deletes provided by a linked list-based implementation. On the other hand, lists provide fast O(1) time random access to elements on the stack which can be an added benefit.

Here’s an important performance caveat while using lists as stacks:

To get the amortized O(1) performance for insertion and deletion, new is added to the end of the list with the append() method and are removed from the end using pop(). Stacks based on Python lists extend to the right and shrink to the left.

Adding and removing from the front takes much more time  (O(n) time), as the existing elements have to be shifted around to make room for the new element to be added.

# Using a Python list as a stack (LIFO):

s = []
 
s.append('eat')
s.append('sleep')
s.append('code')
 
>>> s
['eat', 'sleep', 'code']
 
>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'
 
>>> s.pop()
IndexError: "pop from empty list"

The collections.deque Class

The deque class implements a double-ended queue which supports addition and removal of elements from either end in O(1) time (non-amortized).

Because deques support adding and removing elements from both ends equally well, they can serve both as queues and as stacks.

Python’s deque objects are implemented as doubly-linked lists which gives them proper and consistent performance insertion and deletion of elements, but poor O(n) performance as they randomly access elements in the middle of the stack.

collections.deque is a favourable choice if you’re looking for a stack data structure in Python’s standard library with the performance characteristics of a linked-list implementation.

# Using collections.deque as a stack (LIFO):

from collections import deque
q = deque()
 
q.append('eat')
q.append('sleep')
q.append('code')
 
>>> q
deque(['eat', 'sleep', 'code'])
 
>>> q.pop()
'code'
>>> q.pop()
'sleep'
>>> q.pop()
'eat'
 
>>> q.pop()
IndexError: "pop from an empty deque"

The queue.LifoQueue Class

This stack implementation in the Python standard library is synchronized and provides locking semantics to support multiple concurrent producers and consumers.

The queue module contains several other classes implementing multi-producer, multi-consumer queues that are useful for parallel computing.

Depending on your use case the locking semantics might be helpful, or just incur unneeded overhead. In this case you’d be better off with using a list or a deque as a general purpose stack.

# Using  queue.LifoQueue as a stack:

from queue import LifoQueue
s = LifoQueue()
 
s.put('eat')
s.put('sleep')
s.put('code')
 
>>> s
<queue.LifoQueue object at 0x108298dd8>
 
>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'
 
>>> s.get_nowait()
queue.Empty
 
>>> s.get()
# Blocks / waits forever...

If you have continued this far, you must now be in a position to use stacks in Python, I hope this blog helped you go through the different implementation methods of a stack in Python. 

So this concludes our “stack in python” article. I hope you enjoyed reading this blog and found it informative. By now, you must have acquired a sound understanding of what a python stack is and how it is used. Now go ahead and practice all the examples.

To get in-depth knowledge on Python Programming language along with its various applications, you can enroll now for live Python course training with 24/7 support and lifetime access.

Got a question for us? Please mention it in the comments section of “Stack in Python” blog and we will get back to you at the earliest.