Stack Implementation in Python.

In Python, the stack data structure represents a fundamental and versatile form of collection, adhering to the Last In, First Out (LIFO) principle. It organizes elements in a manner where the last element added is the first one to be removed, resembling a stack of items. Python facilitates stack implementation through its built-in data structures like lists or by utilizing modules from the collections or queue libraries.

Note: Here we will cover stack implementation in Python programming. If you are not familiar with stack data structure then you can check our post "Introduction to Stack Data Structure" in which we have explained the stack in complete detail with code.

Basic Stack Operations.

push(element): Add/Insert an element onto the stack.
pop(): Remove the element from the top of the stack.
peek(): View the top element without removing it.
empty(): Check if the stack is empty. Return true if the stack is empty.
size(): Find the number of elements present in the stack.

Implementation of Stack in Python.

There are various methods to implement stack in Python and here we are going to learn three different methods:

Using List.
Using collection.deque.
Using queue.LifoQueue.

Stack Implementation Using List.

The stack implementation in Python using a list mirrors the behavior of a traditional stack data structure by utilizing Python's built-in list functions. Elements are added to the top of the stack, resembling a push operation via the append() method. Similarly, the pop() function removes and returns the top element, replicating the stack's pop operation.

To view the top element without removing it (peek operation), referencing the last element (self.stack[-1]) of the list is employed, providing a glimpse into the topmost element of the stack. The size of the stack is determined by obtaining the length of the underlying list (len(self.stack)), indicating the number of elements present.

However, the implementation has drawbacks. Python lists utilize dynamic arrays, resulting in automatic resizing to accommodate elements. While append() and pop() operations typically offer O(1) time complexity, the occasional resizing might lead to O(n) complexity in specific cases, impacting performance.

Python Code:

class StackUsingList:
    # Initializing an empty list as a stack
    def __init__(self):
        self.stack = []  
    
    # Adding an element to the top of the stack
    def push(self, element):
        self.stack.append(element)  

    # Removing and returning the top element from the stack
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()  
        else:
            return "Stack is empty"
    
    # Returning the top element without removing it
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]  
        else:
            return "Stack is empty"
    
    # Checking if the stack is empty
    def is_empty(self):
        return len(self.stack) == 0  
    
    # Determining the size of the stack
    def size(self):
        return len(self.stack)  

# Example usage:
stack = StackUsingList()
stack.push(10)
stack.push(20)
stack.push(30)

print("Size of stack:", stack.size())  

print("Top element:", stack.peek()) 

print("Popped element:", stack.pop()) 

print("Is stack empty?", stack.is_empty())

Output:

Size of stack: 3
Top element: 30
Popped element: 30
Is stack empty? False

Stack Implementation Using collection.deque.

The stack implementation using collection.deque in Python provides an efficient alternative to mimic stack behavior while addressing some of the drawbacks of using lists.

Implementation:

To Initialize an empty dequeue from the collections module to serve as the stack: stack = dequeu().
To add elements to the stack (push) we use the append() function of deque. This adds elements to the right side of the deque, emulating the stack's push operation.
To remove or retrieve the top element (pop) from the stack we use pop() function of the deque. This removes and returns the rightmost element, simulating the stack's pop operation.
To access the top element without removing it (peek) by referencing the rightmost element (stack[-1]) of the deque, providing a view into the top element.
To verify if the stack is empty we check the length of the deque and if the length is 0 (len(stack) == 0) it means the stack is empty.
To determine the size of the stack by retrieving the length of the deque (len(stack)), indicating the count of elements in the stack.

Python Code:

from collections import deque

class StackUsingDeque:
    # Initializing an empty deque as a stack
    def __init__(self):
        self.stack = deque()  

    # Adding an element to the top of the stack
    def push(self, element):
        self.stack.append(element)  

    # Removing and returning the top element from the stack
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()  
        else:
            return "Stack is empty"

    # Returning the top element without removing it
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]  
        else:
            return "Stack is empty"
    
    # Checking if the stack is empty
    def is_empty(self):
        return len(self.stack) == 0  
    
    # Determining the size of the stack
    def size(self):
        return len(self.stack)  

# Example usage:
stack = StackUsingDeque()
stack.push(10)
stack.push(20)
stack.push(30)

print("Size of stack:", stack.size())  

print("Top element:", stack.peek())

print("Popped element:", stack.pop())

print("Is stack empty?", stack.is_empty())

Output:

Size of stack: 3
Top element: 30
Popped element: 30
Is stack empty? False

Stack Implementation using queue.LifoQueue.

The implementation of a stack queue.LifoQueue in Python provides a direct and thread-safe approach to creating a stack data structure adhering to the Last-In, First Out (LIFO) principle. This implementation is part of the queue module, offering synchronization and efficient LIFO-based operations for managing in a stack-like manner.

The functionality of Stack Implementation using the queue.LifoQueue:

Initialize an empty stack using LifoQueue: stack = LifoQueue(). This creates a stack structure optimized for LIFO operations.
Add elements onto the stack (push) using the put() method of LifoQueue. Elements are inserted into the stack, following the LIFO order, ensuring the last element added becomes the top of the stack.
Remove and retrieve elements from the top of the stack(pop) using the get() method of LifoQueue. This retrieves elements in the reverse order of their insertion, effectively mimicking the behavior of a stack.
Accessing the top element of the stack without removing it (peek) by using not_empty() attribute allows viewing the top element without altering the stack contents.
Obtain the size of the stack using the qsize() method of LifoQueue, which retrieves the count of elements present in the stack.

Python Code:

from queue import LifoQueue

# Initializing a LifoQueue as a stack
class StackUsingLifoQueue:
    def __init__(self):
        self.stack = LifoQueue()

    # Adding an element to the top of the stack
    def push(self, element):
        self.stack.put(element)

    # Removing and returning the top element from the stack
    def pop(self):
        if not self.is_empty():
            return self.stack.get()  
        else:
            return "Stack is empty"

    def peek(self):
        if not self.is_empty():
            top_element = self.stack.get()
            # Restoring the element after peeking
            self.stack.put(top_element)
            # Returning the top element without removing it  
            return top_element  
        else:
            return "Stack is empty"

    # Checking if the stack is empty
    def is_empty(self):
        return self.stack.empty()  
     
    # Determining the size of the stack
    def size(self):
        return self.stack.qsize()

# Example usage:
stack = StackUsingLifoQueue()
stack.push(10)
stack.push(20)
stack.push(30)

stack.push(40)

print("Size of stack:", stack.size()) 

print("Top element:", stack.peek())  

print("Popped element:", stack.pop())  

print("Is stack empty?", stack.is_empty())

Output:

Size of stack: 4
Top element: 40
Popped element: 40
Is stack empty? False

I hope now you understand three different ways to implement stack data structure in Python. Stack is a very useful data structure and have many applications in numerous domains, from handling function calls to algorithmic problem-solving, making it an essential component in Python programming.

Stack Implementation in Python.

Basic Stack Operations.

Implementation of Stack in Python.

Stack Implementation Using List.

Stack Implementation Using collection.deque.

Stack Implementation using queue.LifoQueue.

No comments:

Post a Comment