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.

Python Program to Subtract two Matrices.

Matrix subtraction is a fundamental operation in linear algebra and is often required in various scientific and computational applications. In this article, we'll explore how to subtract two matrices using Python programming.

In matrix subtraction, elements of one matrix are subtracted from their corresponding elements in another matrix of the same dimensions. The result is a new matrix with dimensions identical to the original matrices being subtracted. 

Quick Tip: Ensure matrices have the same dimensions for subtraction (m x n).

Matrix Subtraction Program in Python.

Step-by-step Algorithm:

• Define two matrices A and B, each represented as nested lists in Python.

• Create a new matrix to store the result of the subtraction.

• Subtract corresponding elements of matrices A and B to obtain the elements of the resultant matrix.

• Use nested loops to iterate through each element in the matrices and perform subtraction.

Python Code:

# Python code for matrix subtraction
def subtract_matrices(matrix_A, matrix_B):
    result_matrix = []
    for i in range(len(matrix_A)):
        row = []
        for j in range(len(matrix_A[0])):
            row.append(matrix_A[i][j] - matrix_B[i][j])
        result_matrix.append(row)
    return result_matrix

# Example usage
matrix_A = [[1, 2, 3],
            [4, 5, 6],
            [7, 8, 9]]

matrix_B = [[9, 8, 7],
            [6, 5, 4],
            [3, 2, 1]]

result = subtract_matrices(matrix_A, matrix_B)
print("Resultant Matrix after subtraction:")
for row in result:
    print(row)

Output:

Resultant Matrix after subtraction:
[-8, -6, -4]
[-2, 0, 2]
[4, 6, 8]

• Time Complexity: O(m x n) where m is the number of rows and n is the number of columns.
• Space Complexity: O(m x n) because we need extra space to store the resultant matrix.

Python Program to Add Two Matrices.

In Python programming, performing matrix operations holds importance in various computational tasks. Adding two matrices is a fundamental operation, often encountered in scientific computing, data analysis, and machine learning. Let's understand the efficient way to perform this operation in Python.

Matrix Addition in Python.

Matrix addition is possible only when the matrices meet specific conditions related to their dimensions. For two matrices A and B to be added together (A + B = C), they must satisfy the following conditions:

• Both matrices must have the same number of rows and columns.
• If matrix A has dimensions m x n (m rows and n columns), matrix B must also have dimensions m x n.

Python Code for Adding Two Matrices.

# Python Code for Matrix Addition
def add_matrices(matrix1, matrix2):
    # Check if matrices have the same dimensions
    if len(matrix1) != len(matrix2) or len(matrix1[0]) != len(matrix2[0]):
        return "Matrices should have the same dimensions for addition"

    result = []
    for i in range(len(matrix1)):
        row = []
        for j in range(len(matrix1[0])):
            row.append(matrix1[i][j] + matrix2[i][j])
        result.append(row)
    return result

# Example matrices for addition
matrix_A = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

matrix_B = [
    [9, 8, 7],
    [6, 5, 4],
    [3, 2, 1]
]

# Calling the function to add matrices
resultant_matrix = add_matrices(matrix_A, matrix_B)
print("Resultant Matrix after Addition:")
for row in resultant_matrix:
    print(row)

Output:

Resultant Matrix after Addition:
[10, 10, 10]
[10, 10, 10]
[10, 10, 10]

Explanation: The add_matrices() function takes two matrices as input parameters and checks if they have the same dimensions. If the matrices have the same dimensions, it iterates through corresponding elements of the matrices, performs element-wise addition, and constructs the resultant matrix.

• Time Complexity: O(m x n)
• Space Complexity: O(m x n)

Python Program to Print 2D Matrix.

Printing a 2D matrix in Python is a fundamental operation, often encountered in various data manipulation and algorithmic tasks. A 2D matrix, also known as a 2D array, represents data in a grid format consisting of rows and columns. Python offers several methods to effectively display and print a 2D matrix.

Let's explore different methods to print a 2D matrix in Python:

Method 1: Using Nested Loops.

One of the simplest ways to print a 2D matrix is by utilizing nested loops to iterate through rows and columns.

Python Code:

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Using nested loops to print the matrix
for row in matrix:
    for element in row:
        print(element, end=" ")  
    print()  # Move to the next line after printing a row

Output:

1 2 3
4 5 6 
7 8 9 

Method 2: Using List Comprehension.

Python's list comprehension offers a concise way to print a 2D matrix.

Python Code:

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Using list comprehension to print the matrix
[print(*row) for row in matrix]

Output:

1 2 3
4 5 6 
7 8 9 

Method 3: Using NumPy Library.

The NumPy library provides powerful functionalities for handling multi-dimensional arrays, including 2D matrices.

Python Code:

import numpy as np

matrix = np.array([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
])

# Printing the NumPy matrix
print(matrix)

Output:

1 2 3
4 5 6 
7 8 9 

Heap Sort Algorithm in Python.

Heap Sort is a comparison-based sorting algorithm that uses a Binary Heap data structure to sort elements in an array. In this article, we will discuss the algorithm in detail with Python code implementation.

Heap Sort Algorithm Explanation.

Heap Sort is a sorting algorithm that utilizes the principles of a Binary Heap data structure to sort elements within an array. The process begins by constructing a Max Heap or Min Heap from the unsorted array, ensuring that the root node holds the maximum (or minimum) value compared to its children in the Max Heap (or vice versa in a Min Heap). 

In the next step, the algorithm performs heapify operations, involving reorganization of the heap after each element removal to maintain heap property. During the sorting phase, elements are sequentially removed from the heap, starting from the root node. After each removal, the remaining elements undergo heapify operations to preserve the heap structure. The removed elements are stored in the array, ultimately resulting in a sorted arrangement.

Heap Sort Algorithm Steps:

• Convert the unsorted array into a Max Heap or Min Heap.
• Perform heapify operations to maintain the heap property after each element removal.
• Sequentially remove elements from the heap, starting from the root node. After each removal, reorganize the heap to maintain the heap property.
• Store the removed elements in an array to obtain the sorted order. 

Python Program for Heap Sort Algorithm.

Below is the code implementation of the Heap Sort Algorithm using Python language.

Python Code:

# Python Code implementatin for Heap Sort Algorithm
def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2  # Right child

    # Check if left child exists and is greater than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Check if right child exists and is greater than root
    if right < n and arr[right] > arr[largest]:
        largest = right

    # Change root if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # Build a max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap root with last element
        heapify(arr, i, 0)  # Heapify root element

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:", arr) 

Output:

Sorted array: [5, 6, 7, 11, 12, 13]

Time Complexity: The time complexity of Heap Sort in all cases is O(n log n). Building the heap takes O(n) time, and for each element, heapify takes O(log n) time. As there are n elements, the total time complexity is O(n log n).

Space Complexity: Heap Sort has a space complexity of O(1) as it performs sorting in place, utilizing the input array without requiring additional space.

Heap Sort Using Python Built-in Function.

In Python, the heapq module provides a heap sort functionality through the heapify() and heappop() functions. These functions enable Heap Sort by creating a min-heap and extracting elements one by one, resulting in a sorted list.

Main functions of heapq module:

• heapify(iterable): Converts a given iterable (such as a list) into a heap in place. The function rearranges the elements so that they satisfy the heap property.

• heappush(heap, item): Adds an element item to the heap while maintaining the heap property.

• heappop(heap): Removes and returns the smallest element (root) from the heap while maintaining the heap property.

Python Code:

# Heap Sort Algorithm using heapq module
import heapq

def heap_sort(arr):
    # Convert the input list into a min-heap
    heapq.heapify(arr)  

    sorted_list = []
    while arr:
    # Extract elements one by one 
       sorted_list.append(heapq.heappop(arr))  
    return sorted_list

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
sorted_array = heap_sort(arr)
print("Sorted array:", sorted_array)

Output:

Sorted array: [5, 6, 7, 11, 12, 13]

Time Complexity: O(n log n)

Space Complexity: O(1)

Merge Sort Algorithm in Python.

MergeSort is a popular sorting algorithm known for its efficiency and stability. It operates by dividing the unsorted list into smaller sub-lists and then merging them back together to produce a sorted list. It is very similar to the Quick Sort Algorithm. In this article, we are going to understand the Merge Sort algorithm in detail with Python code implementation.

Merge Sort Algorithm Explanation.

The merge sort algorithm is based on the divide and conquer approach in which we continuously divide the given list into smaller units to create sorted sub-lists and then merge them back to create a final sorted list.  

 

Algorithm Steps:

• Start with an unsorted list/array.
• Divide the list into smaller sub-lists recursively until each sub-list contains only one element. This process is achieved recursively.
• Combine the smaller sorted sub-lists back together by comparing and merging adjacent pairs of sub-lists.
• Merge these pairs in a sorted manner to create larger sorted sub-lists. 

Python Program for Merge Sort Algorithm.

Below is the code implementation of Merge Sort Algorithm in Python:

# Python code implementation of Merge Sort
def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle of the list
        mid = len(arr) // 2 
 
        # Divide the list into two halves
        left_half = arr[:mid]  
        right_half = arr[mid:]

        # Recursive call to sort the left half
        merge_sort(left_half)  
        
        # Recursive call to sort the right half
        merge_sort(right_half)  

        # Merge the sorted halves
        i = j = k = 0  # Initialize indices for merging
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Check for remaining elements in left and right halves

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example usage:
arr = [64, 34, 25, 12, 20, 10, 90]
merge_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [10, 12, 20, 25, 34, 64, 90]

Time Complexity: Merge Sort demonstrates a time complexity of O(n log n) across all cases. This efficiency makes Marge Sort highly desirable for sorting larger datasets. 

Space Complexity: O(n). Merge Sort's space complexity primarily involves auxiliary space for temporary arrays during the merging phase.

Quick Sort Algorithm in Python.

Quick Sort is a highly efficient sorting algorithm that arranges elements in ascending or descending order. It operates based on the divide and conquer strategy, dividing the array into smaller segments, and then sorting those segments recursively to achieve the final sorted array. It is very much similar to the Merge Sort Algorithm.

Quick Sort Algorithm Explanation.

In Quick Sort, we have to choose a pivot element, a chosen value from the array around which partitioning occurs. This pivotal choice significantly influences the algorithm's efficiency. Our goal is to select a pivot that helps create balanced partitions, ensuring the array gets divided into approximately equal halves during each recursive call.

Select the First and Last Element as Pivot:

• Selecting the first and last element as the pivot is simple and efficient in implementation. However, this approach might lead to unbalanced partitions if the array is already sorted or nearly sorted.

Select the Last Element as Pivot:

• Choosing the middle element of the array as the pivot. This method often provides a better pivot choice, especially for larger datasets.

Quick Sort Algorithm Steps:

• Step 1: Select an element from the array as the pivot (commonly the last element).

• Step 2: Rearrange the elements in the array so that elements smaller than the pivot are placed before it, while elements larger than the pivot are placed after it. 

• Step 3: After Step 2,  the pivot assumes its correct position in the sorted array.

• Step 4: Apply Quick Sort recursively to the subarrays formed by partitioning until the entire array is sorted.

Python Program for Quick Sort Algorithm.

Below is the code implementation of the Quick Sort Algorithm using Python programming.

# Python code implementation of Quick Sort Algorithm
def partition(arr, low, high):
    # Choose the last element as the pivot    
    pivot = arr[high]  
    i = low - 1  # Index of smaller element
    
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        # Partitioning index
        pi = partition(arr, low, high)

        # Recursively sort elements before and after partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Time Complexity: In the best and average cases, where the pivot consistently divides the array into roughly equal halves, Quick Sort achieves a time complexity of O(n log n). However, in the worst-case scenario, where the pivot selection leads to highly unbalanced partitions, Quick Sort's time complexity degrades to O(n^2).

Space Complexity: In the average case, the maximum space required for the recursive call stack is O(log n), as the array gets divided into smaller segments. 

Selection Sort Algorithm in Python.

Sorting algorithms offer a unique approach to arranging data efficiently in ascending or descending order. Among these techniques stands Selection Sort, a straightforward yet essential algorithm that systematically organizes elements by repeatedly selecting the minimum value and placing it at the beginning. In this article, we will explore the Selection Sort Algorithm in detail with Python implementation, and understand its strengths and limitations in sorting data.

Python Program for Selection Sort Algorithm.

Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. It divides the array into two parts: the sorted part and the unsorted part. The algorithm finds the smallest element from the unsorted part and swaps it with the first unsorted element, incrementing the sorted part’s size by one.

Algorithm Steps:

• Start from the beginning of the list.
• Find the minimum element in the unsorted part.
• Swap it with the first unsorted element.
• Increment the sorted part’s size by one.
• Repeat steps 2-4 until the entire list is sorted.

Python Code Implementation for Selection Sort.

Here is an example of Selection Sort in Python:

# Python code for Selection Sort Algorithm
def selection_sort(arr):
    n = len(arr)
    for i in range(n):

        min_idx = i

        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Time and Space Complexity.

• Time Complexity: O(n^2) as it involves nested loops iterating through the array, making it inefficient for larger datasets.

• Space Complexity: O(1) as Selection Sort operates in place, requiring only a constant amount of extra space for variables.