Stack in Python: How To Implement Python Stack?

Stack is a linear type of data structure that enables efficient data storage and access. As the literal meaning of stack indicates, this data structure is based on the logic of storing elements one on top of another. There are plenty of real-world examples of the stack from our daily lives, such as a Stack of plates, a stack of notes, a stack of clothes, etc. Like any other efficient programming language, Python also allows a smooth stack implementation and various other data structures. Today, in this article, we will learn about the Python stack and how to implement it. 

• What is Stack in Python? 
• Methods of Stack
• Functions associated with Python Stack
• Implementation of Stack
• Deque Vs. List
• Python Stacks and Threading
• Which Implementation of Stack should one consider?
• Conclusion
• FAQs

What is Stack in Python? 

Stack is a linear data structure that works on the principle of ‘Last In First Out (LIFO). This means that the element that goes in the stack first comes out last. The term that we use for sending the elements to a stack is known as ‘Push’, whereas the term for deleting the elements from a stack is known as ‘Pop’. Hence, we can say that since a stack has only one open end, pushing and popping can’t take place simultaneously. A pictorial representation of the PUSH and POP operation in the stack has been shown below:

The inbuilt datatype of Python that we use to implement Python is the Python list. Further, for exercising PUSH and POP operations on a stack, we use the append() and pop() function of the Python list.

Get your hands on the Python Stack course and learn more about it.

Methods of Stack

The most basic methods associated with a Stack in python are as follows:

• push(n)– This is a user-defined stack method used for inserting an element into the stack. The element to be pushed is passed in its argument.
• pop()– We need this method to remove the topmost element from the stack. 
• isempty()– We need this method to check whether the stack is empty or not. 
• size()– We need this method to get the size of the stack. 
• top()– This stacking method will be used for returning the reference to the topmost element or, lastly pushed element in a stack.

Functions associated with Python Stack

There are a bunch of useful functions in Python that help us deal with a stack efficiently. Let’s take a brief look at these functions –  

• len()– This stack method is used for returning the size of the stack. This function can also be used in the definition of isempty() method in a Python stack.
• append(n)– This Python function is used for inserting an element into the stack. The element to be pushed is passed in its argument.
• pop()– This method, associated with the Python lists, is used for deleting the topmost element from the stack. 

Implementation of Stack

There are four ways in which we can carry out the implementation of a stack in Python-

• list
• collections.deque
• queue.LifoQueue
• Singly-linked list  

Out of these three, the easiest and the most popular way for implementing a stack in Python is list. Let’s see the implementation of a stack in Python using lists.

Implementation Using List

# Stack Creation
def create_stack():
    stack = list()            #declaring an empty list
    return stack


# Checking for empty stack
def Isempty(stack):
    return len(stack) == 0


# Inserting items into the stack
def push(stack, n):
    stack.append(n)
    print("pushed item: " + n)


# Removal of an element from the stack
def pop(stack):
    if (Isempty(stack)):
        return "stack is empty"
    else:
        return stack.pop()

# Displaying the stack elements
def show(stack):
    print("The stack elements are:")
    for i in stack:
        print(i)
        
stack = create_stack()
push(stack, str(10))
push(stack, str(20))
push(stack, str(30))
push(stack, str(40))
print("popped item: " + pop(stack))
show(stack)

However, the speed issue becomes a major limitation here when dealing with a growing stack. The items in a list are stored one after the other inside the memory. Hence, if the stack grows bigger than the block of memory allocated to the list, Python needs to do some new memory allocations, resulting in some append() taking much longer than the rest while calling.

Implementation using collections.deque

We can also use the deque class of the Python collections module to implement a stack. Since a deque or double ended queue allow us to insert and delete element from both front and rear sides, it might be more suitable at times when we require faster append() and pop() operations. 

from collections import deque  

def create_stack():  
    stack = deque()    #Creating empty deque
    return stack 
  
# PUSH operation using append()
def push(stack, item):
    stack.append(item)

  
#POP operation
def pop(stack):
    if(stack):
        print('Element popped from stack:')
        print(stack.pop())
    else:
        print('Stack is empty')
    

#Displaying Stack
def show(stack):
    print('Stack elements are:')
    print(stack)
    
new_stack=create_stack()
push(new_stack,25)
push(new_stack,56)
push(new_stack,32)
show(new_stack)

pop(new_stack)
show(new_stack)

Implementation using queue.LifoQueue

The queue module of Python consists of a LIFO queue. A LIFO queue is nothing but a stack. Hence, we can easily and effectively implement a stack in Python using the queue module. For a LifoQueue, we have certain functions that are useful in stack implementation, such as qsize(), full(), empty(), put(n), get() as seen in the following piece of code. The max size parameter of LifoQueue defines the limit of items that the stack can hold.

from queue import LifoQueue
  
# Initializing a stack
def new():
    stack = LifoQueue(maxsize=3)   #Fixing the stack size
    return stack

#PUSH using put(n) 
def push(stack, item):
    if(stack.full()):                      #Checking if the stack is full
        print("The stack is already full")
    else:
        stack.put(item)
        print("Size: ", stack.qsize())     #Determining the stack size

#POP using get()
def pop(stack):
    if(stack.empty()):              #Checking if the stack is empty
        print("Stack is empty")
    else:
        print('Element popped from the stack is ', stack.get())         #Removing the last element from stack
        print("Size: ", stack.qsize())

stack=new()
pop(stack)
push(stack,32)
push(stack,56)
push(stack,27)
pop(stack)

Implementation using a singly linked list

Singly-linked lists are the most efficient and effective way of implementing dynamic stacks. We use the class and object approach of Python OOP to create linked lists in Python. We have certain functions at our disposal in Python that are useful in stack implementation, such as getSize(), isEmpty(), push(n), and pop(). Let’s take a look at how each of these functions helps in implementing a stack.

#Node creation
class Node:
	def __init__(self, value):
		self.value = value
		self.next = None

#Stack creation
class Stack:
    #Stack with dummy node
	def __init__(self):
		self.head = Node("head")
		self.size = 0

	#  For string representation of the stack
	def __str__(self):
		val = self.head.next
		show = ""
		while val:
			show += str(val.value) + " , "
			val = val.next
		return show[:-3]

	# Retrieve the size of the stack
	def getSize(self):
		return self.size

	# Check if the stack is empty
	def isEmpty(self):
		return self.size == 0

	# Retrieve the top item of the stack
	def peek(self):
		# Check for empty stack.
		if self.isEmpty():
			raise Exception("This is an empty stack")
		return self.head.next.value

	# Push operation
	def push(self, value):
		node = Node(value)
		node.next = self.head.next
		self.head.next = node
		self.size += 1

	# Pop Operation
	def pop(self):
		if self.isEmpty():
			raise Exception("Stack is empty")
		remove = self.head.next
		self.head.next = self.head.next.next
		self.size -= 1
		return remove.value


#Driver Code
if __name__ == "__main__":
	stack = Stack()
	n=20
	for i in range(1, 11):
		stack.push(n)
		n+=5
	print(f"Stack:{stack}")

	for i  in range(1, 6):
		remove = stack.pop()
		print(f"Pop: {remove}")
	print(f"Stack: {stack}")

Deque Vs. List

Python Stacks and Threading

Python is a multi-threaded language, i.e. it allows programming that involves running multiple parts of a process in parallel. We use threading in Python for running multiple threads like function calls, and tasks simultaneously. Python lists and deques both work differently for a program with threads. You would not want to use lists for data structures that ought to be accessed by multiple threads since they are not thread-safe. 

Your thread program is safe with deques as long as you are strictly using append() and pop() only. Besides, even if you succeed at creating a thread-safe deque program, it might expose your program to chances of being misused and give rise to race conditions at some later point in time. So, neither list nor a deque is very good to call when dealing with a threaded program. The best way to make a stack in a thread-safe environment is queue.LifoQueue. We are free to use its methods in a threaded environment. Nevertheless, your stack operations in queue.LifoQueue may take a little longer owing to making thread-safe calls. 

Note: Threading in Python does not mean that different threads are executed on different processors. If 100% of the CPU time is already being consumed, Python threads will no longer be helpful in making your program faster. You can switch to parallel programming in such cases.

Which Implementation of Stack should one consider?

When dealing with a non-threading program, you should go for a deque. When your program requires a thread-safe environment, you better opt for LifoQueue unless your program performance and maintenance are highly affected by the speed of the stack operations. 

Now, the list is a bit risky since it might raise memory reallocation issues. Besides, Python lists are not safe for multithreading environments. The list and deque interfaces are the same, except for such issues as in the list. Hence, a Python deque can be seen as the best alternative for stack implementation.

Conclusion 

Now that, you have come to the end of this article, you must have got a hang of stack in Python. The foremost essential part is to recognize the situations where you need to implement a stack. You have learned about various ways of implementing stack in Python, so you know it is significant to know the requirements of your program to be able to choose the best stack implementation option. 

You should be clear if you are writing a multi-threaded program or not. Python lists are not thread-safe, and thus you would prefer going for deques in case of a multi-threading environment. The drawback of slow stack operations can be overlooked as long as your program performance does not decline because of these factors. 

Frequently Asked Questions