INDEX
1 Stack Implementation 2
2 Queue Implementation 3
3 Array Implementation 4
4 Linked List Implementation 5-6
5 Bubble Sort Using Class 7
6 Selection Sort 8
7 Insertion Sort 9
8 Merge Sort 10-11
9 Quick Sort 12-13
10 Linear search 14
11 Binary Search 15
12 DFS 16
13 BFS 17-18
14 N QUEEN Problem 19-20
15 8 Puzzle Problem 21-22
Page 1 of 22
# Stack Implementation
stack = []
while True:
print("\nStack Operations:")
print("1. Push")
print("2. Pop")
print("3. Display")
print("4. Exit")
choice = int(input("Enter your choice: "))
if choice == 1:
element = input("Enter element to push: ")
[Link](element)
print(f"Element '{element}' pushed to stack.")
elif choice == 2:
if len(stack) == 0:
print("Stack is empty. Cannot pop.")
else:
popped_element = [Link]()
print(f"Element '{popped_element}' popped from stack.")
elif choice == 3:
print("Stack:", stack)
elif choice == 4:
print("Exiting...")
break
else:
print("Invalid choice. Please try again.")
Page 2 of 22
# Queue Implementation
queue = []
while True:
print("\nQueue Operations:")
print("1. Enqueue")
print("2. Dequeue")
print("3. Display")
print("4. Exit")
choice = int(input("Enter your choice: "))
if choice == 1:
element = input("Enter element to enqueue: ")
[Link](element)
print(f"Element '{element}' enqueued to queue.")
elif choice == 2:
if len(queue) == 0:
print("Queue is empty. Cannot dequeue.")
else:
dequeued_element = [Link](0)
print(f"Element '{dequeued_element}' dequeued from queue.")
elif choice == 3:
print("Queue:", queue)
elif choice == 4:
print("Exiting...")
break
else:
print("Invalid choice. Please try again.")
Page 3 of 22
# Array Implementation
array = []
while True:
print("\nArray Operations:")
print("1. Insert")
print("2. Delete")
print("3. Display")
print("4. Exit")
choice = int(input("Enter your choice: "))
if choice == 1:
element = input("Enter element to insert: ")
[Link](element)
print(f"Element '{element}' inserted into array.")
elif choice == 2:
if len(array) == 0:
print("Array is empty. Cannot delete.")
else:
element = input("Enter element to delete: ")
if element in array:
[Link](element)
print(f"Element '{element}' deleted from array.")
else:
print(f"Element '{element}' not found in array.")
elif choice == 3:
print("Array:", array)
elif choice == 4:
print("Exiting...")
break
else:
print("Invalid choice. Please try again.")
Page 4 of 22
# Linked List Implementation
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
def append(self, data):
new_node = Node(data)
if not [Link]:
[Link] = new_node
else:
current = [Link]
while [Link]:
current = [Link]
[Link] = new_node
def delete(self, data):
if not [Link]:
print("Linked List is empty.")
return
if [Link] == data:
[Link] = [Link]
return
current = [Link]
while [Link]:
if [Link] == data:
[Link] = [Link]
return
current = [Link]
print(f"Element '{data}' not found in Linked List.")
Page 5 of 22
def display(self):
elements = []
current = [Link]
while current:
[Link]([Link])
current = [Link]
print("Linked List:", elements)
linked_list = LinkedList()
while True:
print("\nLinked List Operations:")
print("1. Append")
print("2. Delete")
print("3. Display")
print("4. Exit")
choice = int(input("Enter your choice: "))
if choice == 1:
element = input("Enter element to append: ")
linked_list.append(element)
print(f"Element '{element}' appended to Linked List.")
elif choice == 2:
element = input("Enter element to delete: ")
linked_list.delete(element)
elif choice == 3:
linked_list.display()
elif choice == 4:
print("Exiting...")
break
else:
print("Invalid choice. Please try again.")
Page 6 of 22
class BubbleSort:
def __init__(self):
[Link] = []
def get_input(self):
n = int(input("Enter the number of elements: "))
print("Enter the elements:")
[Link] = [int(input()) for _ in range(n)]
def sort(self):
n = len([Link])
for i in range(n):
for j in range(0, n - i - 1):
if [Link][j] > [Link][j + 1]:
# Swap if elements are in the wrong order
[Link][j], [Link][j + 1] = [Link][j + 1], [Link][j]
print(f"Step {i + 1}: {[Link]}")
def display(self):
print("Sorted array:", [Link])
# Main Execution
if __name__ == "__main__":
bubble = BubbleSort()
bubble.get_input()
print("Sorting using Bubble Sort...")
[Link]()
[Link]()
Page 7 of 22
class SelectionSort:
def __init__(self):
[Link] = []
def get_input(self):
n = int(input("Enter the number of elements: "))
print("Enter the elements:")
[Link] = [int(input()) for _ in range(n)]
def sort(self):
n = len([Link])
for i in range(n):
min_index = i
for j in range(i + 1, n):
if [Link][j] < [Link][min_index]:
min_index = j
# Swap the found minimum element with the first element
[Link][i], [Link][min_index] = [Link][min_index], [Link][i]
print(f"Step {i + 1}: {[Link]}")
def display(self):
print("Sorted array:", [Link])
# Main Execution
if __name__ == "__main__":
selection = SelectionSort()
selection.get_input()
print("Sorting using Selection Sort...")
[Link]()
[Link]()
Page 8 of 22
class InsertionSort:
def __init__(self):
[Link] = []
def get_input(self):
n = int(input("Enter the number of elements: "))
print("Enter the elements:")
[Link] = [int(input()) for _ in range(n)]
def sort(self):
n = len([Link])
for i in range(1, n):
key = [Link][i]
j=i-1
# Move elements of data[0..i-1] that are greater than key
while j >= 0 and [Link][j] > key:
[Link][j + 1] = [Link][j]
j -= 1
[Link][j + 1] = key
print(f"Step {i}: {[Link]}")
def display(self):
print("Sorted array:", [Link])
# Main Execution
if __name__ == "__main__":
insertion = InsertionSort()
insertion.get_input()
print("Sorting using Insertion Sort...")
[Link]()
[Link]()
Page 9 of 22
class MergeSort:
def __init__(self):
[Link] = []
def get_input(self):
n = int(input("Enter the number of elements: "))
print("Enter the elements:")
[Link] = [int(input()) for _ in range(n)]
def merge(self, left, right):
result = []
i=j=0
while i < len(left) and j < len(right):
if left[i] < right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1
[Link](left[i:])
[Link](right[j:])
return result
def sort(self, arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = [Link](arr[:mid])
right = [Link](arr[mid:])
return [Link](left, right)
def display(self):
print("Original array:", [Link])
[Link] = [Link]([Link])
Page 10 of 22
print("Sorted array:", [Link])
# Main Execution
if __name__ == "__main__":
merge = MergeSort()
merge.get_input()
print("Sorting using Merge Sort...")
[Link]()
Page 11 of 22
class QuickSort:
def __init__(self):
[Link] = []
def get_input(self):
n = int(input("Enter the number of elements: "))
print("Enter the elements:")
[Link] = [int(input()) for _ in range(n)]
def partition(self, low, high):
pivot = [Link][high]
i = low - 1
for j in range(low, high):
if [Link][j] < pivot:
i += 1
[Link][i], [Link][j] = [Link][j], [Link][i]
[Link][i + 1], [Link][high] = [Link][high], [Link][i + 1]
return i + 1
def quick_sort(self, low, high):
if low < high:
pi = [Link](low, high)
print(f"Pivot step: {[Link]}")
self.quick_sort(low, pi - 1)
self.quick_sort(pi + 1, high)
def display(self):
print("Sorted array:", [Link])
# Main Execution
if __name__ == "__main__":
quick = QuickSort()
quick.get_input()
Page 12 of 22
print("Sorting using Quick Sort...")
quick.quick_sort(0, len([Link]) - 1)
[Link]()
Page 13 of 22
class LinearSearch:
def __init__(self):
[Link] = []
def get_input(self):
n = int(input("Enter the number of elements: "))
print("Enter the elements:")
[Link] = [int(input()) for _ in range(n)]
def search(self, target):
for i, value in enumerate([Link]):
if value == target:
return i # Return index if found
return -1 # Return -1 if not found
# Main Execution
if __name__ == "__main__":
ls = LinearSearch()
ls.get_input()
target = int(input("Enter the element to search: "))
result = [Link](target)
if result != -1:
print(f"Element {target} found at index {result}.")
else:
print(f"Element {target} not found.")
Page 14 of 22
class BinarySearch:
def __init__(self):
[Link] = []
def get_input(self):
n = int(input("Enter the number of elements: "))
print("Enter the elements in sorted order:")
[Link] = [int(input()) for _ in range(n)]
def search(self, target):
left, right = 0, len([Link]) - 1
while left <= right:
mid = (left + right) // 2
if [Link][mid] == target:
return mid # Return index if found
elif [Link][mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # Return -1 if not found
# Main Execution
if __name__ == "__main__":
bs = BinarySearch()
bs.get_input()
target = int(input("Enter the element to search: "))
result = [Link](target)
if result != -1:
print(f"Element {target} found at index {result}.")
else:
print(f"Element {target} not found.")
Page 15 of 22
class Graph:
def __init__(self):
[Link] = {}
def add_edge(self, u, v):
if u not in [Link]:
[Link][u] = []
[Link][u].append(v)
def dfs_util(self, v, visited):
[Link](v)
print(v, end=" ")
for neighbor in [Link](v, []):
if neighbor not in visited:
self.dfs_util(neighbor, visited)
def dfs(self, start):
visited = set()
self.dfs_util(start, visited)
# Taking user input for graph
if __name__ == "__main__":
g = Graph()
n = int(input("Enter the number of edges: "))
print("Enter edges in the format 'u v':")
for _ in range(n):
u, v = map(int, input().split())
g.add_edge(u, v)
start_node = int(input("Enter the starting node for DFS: "))
print("DFS Traversal:")
[Link](start_node)
Page 16 of 22
from collections import deque
class Graph:
def __init__(self):
[Link] = {}
def add_edge(self, u, v):
if u not in [Link]:
[Link][u] = []
[Link][u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
[Link](start)
while queue:
v = [Link]()
print(v, end=" ")
for neighbor in [Link](v, []):
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)
# Taking user input for graph
if __name__ == "__main__":
g = Graph()
n = int(input("Enter the number of edges: "))
print("Enter edges in the format 'u v':")
for _ in range(n):
u, v = map(int, input().split())
g.add_edge(u, v)
Page 17 of 22
start_node = int(input("Enter the starting node for BFS: "))
print("BFS Traversal:")
[Link](start_node)
Page 18 of 22
class NQueens:
def __init__(self, size):
[Link] = size
[Link] = []
def is_safe(self, board, row, col):
# Check column
for i in range(row):
if board[i][col] == 1:
return False
# Check upper-left diagonal
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check upper-right diagonal
for i, j in zip(range(row, -1, -1), range(col, [Link])):
if board[i][j] == 1:
return False
return True
def solve_queens(self, board, row):
if row == [Link]:
[Link]([row[:] for row in board])
return True
for col in range([Link]):
if self.is_safe(board, row, col):
board[row][col] = 1
self.solve_queens(board, row + 1)
board[row][col] = 0 # Backtrack
Page 19 of 22
return False
def solve(self):
board = [[0] * [Link] for _ in range([Link])]
self.solve_queens(board, 0)
def print_solutions(self):
print(f"Total solutions: {len([Link])}")
for idx, solution in enumerate([Link]):
print(f"Solution {idx + 1}:")
for row in solution:
print(" ".join("Q" if cell == 1 else "." for cell in row))
print()
# Taking user input
if __name__ == "__main__":
n=4
queen = NQueens(n)
[Link]()
queen.print_solutions()
Page 20 of 22
from collections import deque
class Puzzle:
def __init__(self, initial, goal):
[Link] = initial
[Link] = goal
def find_blank(self, state):
for i in range(3):
for j in range(3):
if state[i][j] == 0:
return i, j
def generate_moves(self, state):
moves = []
x, y = self.find_blank(state)
# Possible moves: up, down, left, right
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < 3 and 0 <= new_y < 3:
new_state = [row[:] for row in state]
new_state[x][y], new_state[new_x][new_y] = new_state[new_x][new_y], new_state[x][y]
[Link](new_state)
return moves
def bfs(self):
queue = deque([([Link], [])])
visited = set()
while queue:
state, path = [Link]()
if state == [Link]:
return path
Page 21 of 22
state_tuple = tuple(tuple(row) for row in state)
if state_tuple in visited:
continue
[Link](state_tuple)
for move in self.generate_moves(state):
[Link]((move, path + [move]))
return None
# Taking user input
if __name__ == "__main__":
print("Enter the initial state (3x3 matrix, use 0 for blank):")
initial = [list(map(int, input().split())) for _ in range(3)]
print("Enter the goal state (3x3 matrix, use 0 for blank):")
goal = [list(map(int, input().split())) for _ in range(3)]
puzzle = Puzzle(initial, goal)
solution = [Link]()
if solution:
print("Solution found!")
for step in solution:
print("\n".join(" ".join(map(str, row)) for row in step))
print()
else:
print("No solution exists.")
Page 22 of 22