Stack Operations

A stack is an abstract data type that holds an ordered, linear sequence of items. In contrast
to a queue, a stack is a last in, first out (LIFO) structure.
Key characteristics of Stack Operations

• Push: Inserting an item into a stack.

• Pop: Deleting an item from the stack.
• Peek or Top: Displaying the contents of the stack.
# Implementation of Stack Operations
class Stack:
def __init__(self):
# Initialize an empty list to represent the stack
self.stack = []

def push(self, item):

# Add an item to the top of the stack
self.stack.append(item)
print(f"'{item}' has been pushed to the stack.")

def pop(self):
# Remove and return the item from the top of the stack
if len(self.stack) == 0:
print("Error: Stack is empty!")
return None
return self.stack.pop()

def peek(self):
# Return the item at the top of the stack without removing it
if len(self.stack) == 0:
print("Error: Stack is empty!")
return None
return self.stack[-1]

def display(self):
# Display the current state of the stack
if len(self.stack) == 0:
print("Stack is empty.")
else:
print("Stack contents:", self.stack)

def main():
stack = Stack()
 while True:
# Display options for the user
print("\nStack Operations Menu:")
print("1. Push item to stack")
print("2. Pop item from stack")
print("3. Peek top item of stack")
print("4. Display stack contents")
print("5. Exit")

# Get user input

choice = input("Choose an operation (1-5): ").strip()

if choice == '1':
item = input("Enter an item to push to the stack: ").strip()
stack.push(item)
elif choice == '2':
popped_item = stack.pop()
if popped_item:
print(f"'{popped_item}' has been popped from the stack.")
elif choice == '3':
top_item = stack.peek()
if top_item:
print(f"The top item of the stack is '{top_item}'.")
elif choice == '4':
stack.display()
elif choice == '5':
print("Exiting the program. Goodbye!")
break
else:
print("Invalid choice! Please choose a valid operation (1-5).")

if __name__ == "__main__":
main()

Output:
Stack Operations:
1. Push
2. Pop
3. Peek
4. Display Stack
5. Check if Stack is Empty
6. Exit
Enter your choice: 1
Enter the item to push: 10
Item 10 pushed to stack.

Stack Operations:
1. Push
2. Pop
3. Peek
4. Display Stack
5. Check if Stack is Empty
6. Exit
Enter your choice: 4
Stack contents: ['10']
 Queue Operation

Queue - Is a linear data structure that follows the First In, First Out (FIFO) principle.
This means that the element that is added first to the queue will be the first one to
be removed. Think of it like a line at a checkout counter, where the first person to
stand in line is the first one to be served.
In a queue:
• Enqueue: refers to adding an item to the end (or rear) of the queue.
• Dequeue: refers to removing an item from the front of the queue.
• Peek/Front: refers to accessing the item at the front of the queue without removing
it.

#Implemention of queue
class Queue:
def __init__(self):
self.queue = []

def enqueue(self, item):

self.queue.append(item)
print(f"'{item}' has been added to the queue.")

def dequeue(self):
if not self.is_empty():
removed_item = self.queue.pop(0)
print(f"'{removed_item}' has been removed from the queue.")
else:
print("Error: Queue is empty!")

def is_empty(self):
return len(self.queue) == 0

def display(self):
 if self.is_empty():
print("Queue is empty.")
else:
print("Queue contents:", self.queue)

def main():
q = Queue()

while True:
print("\nQueue Operations Menu:")
print("1. Enqueue item")
print("2. Dequeue item")
print("3. Display queue")
print("4. Exit")

choice = input("Choose an operation (1-4): ").strip()

if choice == '1':
item = input("Enter an item to enqueue: ").strip()
q.enqueue(item)
elif choice == '2':
q.dequeue()
elif choice == '3':
q.display()
elif choice == '4':
print("Exiting the program. Goodbye!")
break
else:
print("Invalid choice! Please choose a valid option (1-4).")
if __name__ == "__main__":
main()
Output:
Queue Operations:
1. Enqueue
2. Dequeue
3. View Queue
4. Exit
Enter your choice (1-4): 1
Enter item to enqueue: Apple
Enqueued: Apple
 Bubble sort
Bubble Sort is a simple sorting algorithm that compares adjacent elements, and swaps them
if they are in the wrong order. The process is repeated until the list is sorted.
Key Characteristics of Bubble Sort
1. Comparison-based: It works by comparing adjacent elements.
2. Iterative: Requires multiple passes through the list.
3. Time Complexity:
o Best Case (already sorted): O(n)
o Worst and Average Case: O(n2)
# Implementation of Bubble Sort
def bubble_Sort(arr):
n = len(arr)
# Traverse through all array elements in the list
for i in range(n):
swapped = False
for j in range(0, n-i-1):
# Traverse the array from 0 to n-i-1
# Swap the element if the comparing element(arr[j]) is greater than the next element
(arr[j+1])
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
# Driver code
if __name__ == "__main__":
arr = list(map(int, input("Enter the elements of the array separated by spaces: ").split()))
bubble_Sort(arr)
print("Sorted array:")
 for i in range(len(arr)):
print("%d" % arr[i], end=" ")

Output:
Enter the elements of the array separated by spaces: 20 2 65 1 10
Sorted array:
1 2 10 20 65
 Insertion sort
Insertion sort: It is a simple sorting algorithm that builds a sorted list one element at a time
by repeatedly taking the next element from the unsorted part of the list and inserting it into
its correct position in the sorted part.
Key Characteristics:
• Simple and easy to implement.
• Efficient for small or nearly sorted lists.
• Time complexity is O(n2)O(n^2)O(n2) in the worst case, but it can be O(n)O(n)O(n)
for nearly sorted lists.
#Implementation of Insertion sort
def insertion_sort(arr):
# Traverse from the second element to the end
for i in range(1, len(arr)):
key = arr[i]
j=i-1

# Shift elements of arr[0..i-1] that are greater than key to one position ahead
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1

# Insert the key after shifting elements

arr[j + 1] = key

# Get user input for the list

user_input = input("Enter numbers separated by spaces: ")
arr = list(map(int, user_input.split()))

# Sort the array using insertion sort

insertion_sort(arr)
# Output the sorted list
print("Sorted array:", arr)
Output:
Enter numbers separated by spaces: 5 2 9 1 5 6
Sorted array: [1, 2, 5, 5, 6, 9]
 Binary search
Binary Search : It is a fast search algorithm used to find the position of a target
value within a sorted array or list.
Key characteristics of Binary search
Requires Sorted Data: Binary search only works on sorted arrays or lists.
Divide and Conquer: It repeatedly divides the search range in half, making it very efficient
for large datasets.
Time Complexity: The time complexity is O(log⁡n)O(\log n)O(logn), where nnn is the
number of elements, making it faster than linear search (O(n)O(n)O(n)).

#Implementation of Binary search

def binary_search(arr, target):
low = 0
high = len(arr) - 1

while low <= high:

mid = (low + high) // 2
if arr[mid] == target:
return mid # Target found
elif arr[mid] < target:
low = mid + 1 # Search in the right half
else:
high = mid - 1 # Search in the left half

return -1 # Target not found

# Get user input for the list

user_input = input("Enter numbers separated by spaces (sorted in ascending order): ")
arr = list(map(int, user_input.split()))
# Get the target number to search for
target = int(input("Enter the number to search for: "))

# Perform binary search

result = binary_search(arr, target)

# Output the result

if result != -1:
print(f"Element {target} found at index {result}.")
else:
print(f"Element {target} not found.")
Output:
Enter numbers separated by spaces (sorted in ascending order): 1 3 5 7 9 11 13
Enter the number to search for: 5
Element 5 found at index 2.
 Combine 1 sorting and 1 searching techniques
# Insertion Sort function
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j=i-1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

# Binary Search function

def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Target found
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # Target not found

# Main program
def main():
# Get user input for the list
user_input = input("Enter numbers separated by spaces: ")
 arr = list(map(int, user_input.split()))

# Sort the list using Insertion Sort

insertion_sort(arr)
print("Sorted array:", arr)

# Get the target number to search for

target = int(input("Enter the number to search for: "))

# Perform Binary Search

result = binary_search(arr, target)

# Output the result

if result != -1:
print(f"Element {target} found at index {result}.")
else:
print(f"Element {target} not found.")

# Run the main function

if __name__ == "__main__":
main()
Output:
Enter numbers separated by spaces: 5 2 9 1 3
Sorted array: [1, 2, 3, 5, 9]
Enter the number to search for: 3
Element 3 found at index 2.
 Matrix Multiplication
Matrix multiplication: Matrix multiplication in Python can be implemented using nested
loops or by leveraging libraries like NumPy. Below is a simple implementation using both
methods
key characteristics of Matrix Multiplication:
1. Requires Compatibility:
o The number of columns in the first matrix must equal the number of rows in
the second matrix for multiplication to be possible.
2. Non-Commutative:
o Matrix multiplication is not commutative; that is, A×B≠B×AA \times B \neq B
\times AA×B =B×A in most cases.
3. Associative:
o Matrix multiplication is associative, meaning (A×B)×C=A×(B×C)(A \times B)
\times C = A \times (B \times C)(A×B)×C=A×(B×C).
#Implementation of Matrix Multiplication
import numpy as np
def multiply_matrices(matrix1, matrix2):
"""
Multiplies two matrices using NumPy.
Args:
matrix1: The first matrix as a NumPy array.
matrix2: The second matrix as a NumPy array.
Returns:
The product of the two matrices as a NumPy array,
or None if the matrices cannot be multiplied.
"""
try:
result = np.dot(matrix1, matrix2)
return result
except ValueError:
print("Matrices cannot be multiplied.")
return None
# Example usage
matrix1 = np.array([[1, 2, 3], [4, 5, 6]])
matrix2 = np.array([[7, 8], [9, 10], [11, 12]])
result = multiply_matrices(matrix1, matrix2)
if result is not None:
print("Resultant Matrix:")
print(result)
output:
[[ 58 64]
[139 154]]
 String Matching
String matching: It is the process of finding a substring (or pattern) within a larger string (or
text). It involves searching for occurrences of a specific sequence of characters within
another string.
Key Points:
1. Pattern Matching: Finding a given "pattern" (substring) in a larger "text" (string).
2. Methods: Several algorithms exist for string matching, such as:
o Naive Search: Compare the pattern with every substring of the text.
o Knuth-Morris-Pratt (KMP): Optimized approach that preprocesses the
pattern to skip unnecessary comparisons.
o Rabin-Karp: Uses hashing to search for multiple patterns efficiently.
3. Applications: Used in text editors, search engines, DNA sequence analysis, and more.
#Implementation of String Matching
def string_matching():
# Get input from the user
main_string = input("Enter the main string: ")
pattern = input("Enter the pattern to search for: ")

# Check if the pattern is in the main string

if pattern in main_string:
print(f"The pattern '{pattern}' is found in the main string.")
else:
print(f"The pattern '{pattern}' is not found in the main string.")
Enter the main string: Hello, world!
Enter the pattern to search for: world
The pattern 'world' is found in the main string.# Call the function
string_matching()
Output:
Enter the main string: Hello, world!
Enter the pattern to search for: world
The pattern 'world' is found in the main string.