Scribd
Upload
3 views11 pages

Creating A Stack Using Class in Python

The document provides Python implementations for various data structures and algorithms, including a stack, queue, singly linked list operations (traversal, deletion, insertion), quick sort, merge sort, shell sort, and binary tree creation and traversal methods. Each section includes class definitions and example usage, demonstrating how to manipulate these data structures effectively. Overall, it serves as a comprehensive guide for implementing fundamental data structures and sorting algorithms in Python.

Uploaded by

pkalpanas1974
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views11 pages

Creating A Stack Using Class in Python

The document provides Python implementations for various data structures and algorithms, including a stack, queue, singly linked list operations (traversal, deletion, insertion), quick sort, merge sort, shell sort, and binary tree creation and traversal methods. Each section includes class definitions and example usage, demonstrating how to manipulate these data structures effectively. Overall, it serves as a comprehensive guide for implementing fundamental data structures and sorting algorithms in Python.

Uploaded by

pkalpanas1974
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Creating a stack using class in Python

class Stack:
def __init__(self):
[Link] = []

def push(self, element):


[Link](element)

def pop(self):
if [Link]():
return "Stack is empty"
return [Link]()

def peek(self):
if [Link]():
return "Stack is empty"
return [Link][-1]

def isEmpty(self):
return len([Link]) == 0

def size(self):
return len([Link])

# Create a stack
myStack = Stack()

[Link]('A')
[Link]('B')
[Link]('C')

print("Stack: ", [Link])


print("Pop: ", [Link]())
print("Stack after Pop: ", [Link])
print("Peek: ", [Link]())
print("isEmpty: ", [Link]())
print("Size: ", [Link]())

Using a Python class as a queue:

1
class Queue:
def __init__(self):
[Link] = []

def enqueue(self, element):


[Link](element)

def dequeue(self):
if [Link]():
return "Queue is empty"
return [Link](0)

def peek(self):
if [Link]():
return "Queue is empty"
return [Link][0]

def isEmpty(self):
return len([Link]) == 0

def size(self):
return len([Link])

# Create a queue
myQueue = Queue()

[Link]('A')
[Link]('B')
[Link]('C')

print("Queue: ", [Link])


print("Peek: ", [Link]())
print("Dequeue: ", [Link]())
print("Queue after Dequeue: ", [Link])
print("isEmpty: ", [Link]())
print("Size: ", [Link]())

2
Traversal of a singly linked list in Python:

class Node:
def __init__(self, data):
[Link] = data
[Link] = None

def traverseAndPrint(head):
currentNode = head
while currentNode:
print([Link], end=" -> ")
currentNode = [Link]
print("null")

node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)

[Link] = node2
[Link] = node3
[Link] = node4
[Link] = node5

traverseAndPrint(node1)

DELETING IN THE SIGNLY LINKED LIST


class Node:
def __init__(self, data):
[Link] = data
[Link] = None

def traverseAndPrint(head):
currentNode = head
while currentNode:
print([Link], end=" -> ")
currentNode = [Link]
print("null")

def deleteSpecificNode(head, nodeToDelete):


if head == nodeToDelete:
return [Link]

currentNode = head
while [Link] and [Link] != nodeToDelete:
currentNode = [Link]

3
if [Link] is None:
return head

[Link] = [Link]

return head

node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)

[Link] = node2
[Link] = node3
[Link] = node4
[Link] = node5

print("Before deletion:")
traverseAndPrint(node1)

# Delete node4
node1 = deleteSpecificNode(node1, node4)

print("\nAfter deletion:")
traverseAndPrint(node1)

Inserting a node in a singly linked list in Python:

class Node:
def __init__(self, data):
[Link] = data
[Link] = None

def traverseAndPrint(head):
currentNode = head
while currentNode:
print([Link], end=" -> ")
currentNode = [Link]
print("null")

def insertNodeAtPosition(head, newNode, position):


if position == 1:
[Link] = head
return newNode

currentNode = head
for _ in range(position - 2):
if [Link] is None:
break

4
currentNode = [Link]

[Link] = [Link]
[Link] = newNode
return head

node1 = Node(7)
node2 = Node(3)
node3 = Node(2)
node4 = Node(9)

[Link] = node2
[Link] = node3
[Link] = node4

print("Original list:")
traverseAndPrint(node1)

# Insert a new node with value 97 at position 2


newNode = Node(97)
node1 = insertNodeAtPosition(node1, newNode, 2)

print("\nAfter insertion:")
traverseAndPrint(node1)

Implement Quick Sort Method


def partition(array, low, high):
pivot = array[high]
i = low - 1

for j in range(low, high):


if array[j] <= pivot:
i += 1
array[i], array[j] = array[j], array[i]

array[i+1], array[high] = array[high], array[i+1]


return i+1

def quicksort(array, low=0, high=None):


if high is None:
high = len(array) - 1

if low < high:


pivot_index = partition(array, low, high)
quicksort(array, low, pivot_index-1)
quicksort(array, pivot_index+1, high)

mylist = [64, 34, 25, 5, 22, 11, 90, 12]


quicksort(mylist)
print(mylist) Output: [5, 11, 12, 22, 25, 34, 64, 90]

5
Implementing the Merge Sort algorithm in Python:

def mergeSort(arr):
if len(arr) <= 1:
return arr

mid = len(arr) // 2
leftHalf = arr[:mid]
rightHalf = arr[mid:]

sortedLeft = mergeSort(leftHalf)
sortedRight = mergeSort(rightHalf)

return merge(sortedLeft, sortedRight)

def merge(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

mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]


mysortedlist = mergeSort(mylist)
print("Sorted array:", mysortedlist)

6
defshell_sort(arr):
n = len(arr)
interval = n // 2

while interval > 0:


fori in range(interval, n):
temp = arr[i]
j=i

# Compare elements separated by interval


while j >= interval and arr[j - interval] > temp:
arr[j] = arr[j - interval]
j -= interval

arr[j] = temp

# Reduce interval by half


interval //= 2

# Test the shell sort algorithm


numbers = [45, 31, 62, 12, 89, 5, 9, 8]
print("Original array:")
print(numbers)

shell_sort(numbers)

print("\nArray after Shell Sort:")


print(numbers)

7
CREATE BINARY TREE IN PYTHON
class TreeNode:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')

[Link] = nodeA
[Link] = nodeB

[Link] = nodeC
[Link] = nodeD

[Link] = nodeE
[Link] = nodeF

[Link] = nodeG

# Test
print("[Link]:", [Link])
OUTPUT: [Link]: E

8
classTreeNode:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

defpreOrderTraversal(node):
if node is None:
return
print([Link], end=", ")
preOrderTraversal([Link])
preOrderTraversal([Link])

root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')

[Link] = nodeA
[Link] = nodeB

[Link] = nodeC
[Link] = nodeD

[Link] = nodeE
[Link] = nodeF

[Link] = nodeG

# Traverse
preOrderTraversal(root)

OUTPUT:R, A, C, D, B, E, F, G,

9
classTreeNode:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

definOrderTraversal(node):
if node is None:
return
inOrderTraversal([Link])
print([Link], end=", ")
inOrderTraversal([Link])

root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')

[Link] = nodeA
[Link] = nodeB

[Link] = nodeC
[Link] = nodeD

[Link] = nodeE
[Link] = nodeF

[Link] = nodeG

# Traverse
inOrderTraversal(root)

OUTPUT: C, A, D, R, E, B, G, F,

10
11

You might also like