Python data structures and Algorithms

Data Structures:

1. Stack: A stack is a linear data structure that follows the Last In First Out (LIFO) principle. You can imagine it like a stack of plates. The plate that is placed last is the first one to be removed. stack = []stack.append('a') # push 'a' to stackstack.append('b') # push 'b' to stackprint(stack) # Output: ['a', 'b']stack.pop() # remove 'b'print(stack) # Output: ['a']
2. Queue: A queue is a linear data structure that follows the First In First Out (FIFO) principle. It’s like a queue of people; the person who arrives first, leaves first.from collections import dequequeue = deque()queue.append('a') # enqueue 'a'queue.append('b') # enqueue 'b'print(queue) # Output: deque(['a', 'b'])queue.popleft() # dequeue 'a'print(queue) # Output: deque(['b'])
3. Linked List: A linked list is a linear data structure where each element is a separate object. Each element (node) of a list is comprising of two items - the data and a reference to the next node. class Node: def init(self, data=None): self.data = data self.next = Noneclass LinkedList: def init(self): self.head = Nonellist = LinkedList()llist.head = Node('a')second = Node('b')third = Node('c')llist.head.next = secondsecond.next = third

Algorithms:

1. Bubble Sort: Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j]arr = [64, 34, 25, 12, 22, 11, 90]bubble_sort(arr)print(arr) # Output: [11, 12, 22, 25, 34, 64, 90]
2. Binary Search: Binary search works on sorted arrays. The value is compared with the middle element of the array. If they’re not equal, the half in which the value cannot be is eliminated, and the search continues for the remaining half.def binary_search(arr, low, high, x): if high >= low: mid = (high + low) // 2 if arr[mid] == x: return mid elif arr[mid] > x: return binary_search(arr, low, mid - 1, x) else: return binary_search(arr, mid + 1, high, x) else: return -1arr = [2, 3, 4, 10, 40]x = 10result = binary_search(arr, 0, len(arr)-1, x)print(result) # Output: 3