Knowing stack operations in Python are like knowing the basics of programming and computer science. Python stack that includes the LIFO function is used to implement data management and algorithmic design processes. This article by teacher at a python training institute in Delhi discusses the necessary principles, techniques, and major considerations for using stack in Python which is indispensable to developers of all levels including beginner students.
What is a Stack in Data Structures?
Data structure is the core of any computer storage building blocks the accessing and modifying of data to be efficient. Unlike lines, stacks in computer memory are arrangements of data items. It is a combination of memory and the CPU architecture as well. Similarly, like plates on a shelf of a restaurant, elements on a stack are also from in a “last in, first out” order.
Modern stack data structures are an ordered list or array of function calls and parameters that allow adding or removing objects dynamically either from the top or from the end of the stack. Random access is not possible due to the fact that objects are arranged in a stack.
The stack has two types of operations:
- Push – for putting data into the stack.
- POP – To pop data out of the stack.
Stacks are learnable and easy to use. They can be added to the software to perform different operations. They can be implemented via an Array or Linked List.
When and Why Do We Use Stacks?
The stacks are not complicated data structures in Python, rather they are meant to store and retrieve the data in a sequence.
There are several applications of stacks in the real world, and knowing their functions will help you with smooth data storage.
Example of Stack operation in an Microsoft Office application
Let’s say you’re a developer whose job is to build a brand-new word processor. Therefore you have to develop an “undo” tool. The user should keep going back till the beginning of the session. The stack is perfect for this case. You can record every single user action by pushing them to the stack. Users can easily undo the action by popping the corresponding element from the stack.
What is the difference between Deque Vs. List in Python?
| Deque Vs. List | Deque | List |
| Module Requirement | You do not need to import the collections module for using deque in Python. | You do not need to import any external module for using a list in Python. It’s an inbuilt data structure. |
| Time Complexity | The time complexity of deque for append() and pop() functions is O(1). | The time complexity of lists for append() and pop() functions is O(n). |
| Structure | They are double-ended, which means elements can be inserted into and removed from either of the ends. | This is a single-ended structure that allows append() to insert the element at the end of the list. The pop() is to remove the last element from the list. |
| Usage | Deques can be used to implement stacks with bigger sizes easily and efficiently | The list is suitable for fixed-length operations. The stack implementation through lists becomes difficult when its size starts growing bigger. |
How to implement a Stack in Python?
In Python, we can implement stacks by
- Through the integrated List data structure: Python already provides the built-in List data type with methods to stimulate both operations.
- With the help of the deque library which has a single object to perform operations of both stack and queue.
PUSH Operation
Push — This function pushes an element on top of the stack.
POP Operation
POP — This function removes an element from the top of the stack.
Here’s a program illustrating a Stack in Python:
class MyStack:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, data):
self.items.append(data)
def pop(self):
if not self.is_empty():
return self.items.pop()
else:
print("Stack is empty")
stack = MyStack()
while True:
print("push <value>")
print("pop")
print("quit")
do = input("What you want to do? ").split()
operation = do[0].strip().lower()
if operation == 'push':
stack.push(int(do[1]))
elif operation == 'pop':
popped = stack.pop()
if popped is not None:
print("Popped value:", popped)
elif operation == 'quit':
BreakHow to use stack in Python?
Stacks are used for many purposes in algorithms, for eg, in syntax analysis and in the implementation of real-time memory management (“call stack”). A simple and concise algorithm yet efficient by a stack is a depth-first search (DFS) on a tree or graph data structure. Python deals with stacks by implementing different stack operations each of them characteristically different.
The list Built-in
This stability in operations might not match the consistency provided by the default inserts and deletes of a linked list-oriented implementation. But, lists give the possibility of fast-time random access to other elements on the stack.
Doing this gives the amortized performance in terms of insertion and deletion, whereby new is added to the end of the list using append() and is removed from the start of the list using pop() function. The stacks based on Python lists extend to the right and then shrink to the left.
Example of Python list as a stack (LIFO):
stack = []
stack.append('apple')
stack.append('banana')
stack.append('orange')
print(stack) # Output: ['apple', 'banana', 'orange']
print(stack.pop()) # Output: 'orange'
print(stack.pop()) # Output: 'banana'
print(stack.pop()) # Output: 'apple'
try:
print(stack.pop())
except IndexError as e:
print("IndexError:", e)The collections.deque Class
Since deques provide the function of adding or removing elements equally from both ends, they can serve as either queues or stacks.
Thus, if you are looking for a stack in the Python standard library, but want to have it with the runtime complexity of a linked list implementation, collections.deque would be the best option.
Example of collections.deque as a stack (LIFO):
stack = deque()
# Push elements onto the stack
stack.append('apple')
stack.append('banana')
stack.append('cherry')
print(stack) # Output: deque(['apple', 'banana', 'cherry'])
print(stack.pop()) # Output: 'cherry'
print(stack.pop()) # Output: 'banana'
print(stack.pop()) # Output: 'apple'
try:
print(stack.pop())
except IndexError as e:
print("Error:", e) # Output: Error: pop from an empty deque
The queue.LifoQueue
The Python library also has this stack implementation which is synchronization and provides lock semantics. It support multiple concurrent producers and consumers.
The queue module has many such classes for the sake of parallel computing to implement multi-producers as well as multi-consumer queues.
Depending on your use case, the locking semantics might be required or just a redundancy. In this particular case, you would be better off using a list or deque as a suitable stack.
Example of the queue.LifoQueue as a stack:
class Stack:
def __init__(self):
self.stack = deque()
def push(self, item):
self.stack.append(item)
def pop(self):
if self.is_empty():
return "Stack is empty"
return self.stack.pop()
def is_empty(self):
return len(self.stack) == 0
stack = Stack()
stack.push('study')
stack.push('work')
stack.push('relax')
print(stack.pop()) # Output: relax
print(stack.pop()) # Output: work
print(stack.pop()) # Output: study
print(stack.pop()) # Output: Stack is empty
Which Stack Implementation Should You Consider?
In the case of a non-threaded program, you must use deque. When you need your program to have a safe thread environment, you should use LifoQueue unless your program performance and maintenance are severely impacted by stack operations speed.
Now, the list is a little dangerous because it might start some memory reallocation problems. Moreover, Python lists are not thread-safe for multi-threaded environments. The list and deque interfaces are the same, except there are some problems in the list. Therefore, a Python deque may be considered the best substitute for stack implementation.
Check the basics of linked list in Python
Become a professional Python Developer with Python online course in Hindi
Learning data structures for python may not be easy for students from tier2 and tier3 cities in India but it is must to become an efficient programmer, hence it is always advisable to learn from an expert. You should check the course that comes with proper syllabus and practice modules and practicals. You can check our latest and top python course online in Hindi