<jupyter_start><jupyter_text>Stack<jupyter_code># create stack
def create_stack():
    stack = []
    return stack

def push(stack,element):
    stack.append(element)
    return stack

def pop(stack):
    if len(stack) == 0:
        return "stack is empty"
    return stack.pop()
        
def peak(stack):
    if len(stack) == 0:
        return 'stack is empty'
    return stack[-1]
stk = create_stack()
push(stk,45)
push(stk,55)
pop(stk)
pop(stk)
peak(stk)<jupyter_output><empty_output><jupyter_text>Queue<jupyter_code>class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, element):
        self.queue.append(element)
        return self.queue

    def dequeue(self):
        if self.is_empty():
            return "queue is empty"
        return self.queue.pop(0)

    def show(self):
        return self.queue
    
    def is_empty(self):
        return len(self.queue) == 0
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)
q.dequeue()
q.is_empty()<jupyter_output><empty_output><jupyter_text>Circular Queue<jupyter_code>class CircularQueue:
    def __init__(self, length):
        self.cq = []
        self.length = length
        self.front = 0
        self.rear = 0
        
        
    def is_full(self):
        return len(self.cq) == self.length
            
    def is_empty(self):
        return len(self.cq) == 0
    
    def enqueue(self, element):
        if self.is_full():
            return "queue is full"
        
        if self.rear == self.length:
            if self.front > 0:
                self.rear = 0
                self.cq.insert(self.rear,element)
                if self.rear > self.front:
                    self.rear = self.rear + 1
                else:
                    "queue is full now"
                return self.cq
        
            else:
                "queue is full"
        if self.rear < self.length:
            self.cq.insert(self.rear,element)
            self.rear = self.rear + 1
            return self.cq
    
    def dequeue(self):
        if not self.is_empty():
            element = self.cq.pop(self.front)
            self.front = self.front +1
            return element
        else:
            return "queue is empty"

    def peek(self):
        if not self.is_empty():
            return queue[self.front]
        else:
            return "queue is empty"
        
    def show(self):
        print("queue = ",self.cq,"\nfront = ", self.front, "\nrear = ", self.rear)
circular_queue = CircularQueue(8)
circular_queue.show()
circular_queue.enqueue(11)
circular_queue.show()
circular_queue.enqueue(13)
circular_queue.enqueue(17)
circular_queue.show()
circular_queue.enqueue(19)
circular_queue.enqueue(23)
circular_queue.enqueue(29)
circular_queue.show()
circular_queue.enqueue(31)
circular_queue.show()
circular_queue.enqueue(37)
circular_queue.show()
circular_queue.enqueue(37)
circular_queue.dequeue()
circular_queue.enqueue(37)
circular_queue.show()<jupyter_output>queue =  [37, 13, 17, 19, 23, 29, 31, 37] 
front =  1 
rear =  0<jupyter_text>Double Ended Queue or Deque  1. Input Restricted dequeInsertion can happen from only one end but deletion can happen from both ends<jupyter_code>class InputRestrictedDeque:
    def __init__(self, length):
        self.length = length
        self.dq = []
        self.front = self.rear = 0
        
    def is_full(self):
        return len(self.dq) == self.length
        
    def is_empty(self):
        return len(self.dq) == 0
        
    def enqueue(self, element):
        if self.is_full():
            return "queue is full"
        
        elif self.rear < self.length:
            self.dq.insert(self.rear, element)
            self.rear = self.rear + 1
            return self.dq
        
        elif self.rear == self.length:
            return "queue is full"
            
    def dequeue(self, position):
        if self.is_empty():
            return "queue is empty"
        else:
            if position.lower() == 'front':
                self.rear = self.rear -1
                return self.dq.pop(self.front)
            elif position.lower() == 'rear':
                self.rear = self.rear - 1
                return self.dq.pop(self.rear)
    def show(self):
        print( 'deque = ',self.dq, '\nfront = ', self.front, '\nrear = ', self.rear)
deque = InputRestrictedDeque(8)
deque.show()
deque.enqueue(1)
deque.enqueue(2)
deque.enqueue(3)
deque.enqueue(4)
deque.enqueue(5)
deque.enqueue(6)
deque.enqueue(7)
deque.enqueue(8)
deque.dequeue('front')
deque.dequeue('rear')
deque.show()
deque.dequeue('rear')<jupyter_output><empty_output><jupyter_text>2. Output restricted DequeDeletion can happen from only one end<jupyter_code>class OutputRestrictedDeque:
    def __init__(self, length):
        self.length = length
        self.dq = []
        self.front = self.rear = 0
        
    def is_full(self):
        return len(self.dq) == self.length
        
    def is_empty(self):
        return len(self.dq) == 0
        
    def enqueue(self, element, position):
        if self.is_full():
            return "queue is full"
        elif position == 'front':
            self.dq.insert(self.front, element)
        elif position == 'rear':
            self.dq.insert(self.rear, element)
        
        self.rear = self.rear + 1
        return self.dq
        
            
    def dequeue(self):
        if self.is_empty():
            return "queue is empty"
        else:
            self.rear = self.rear -1
            return self.dq.pop(self.rear)
        
    def show(self):
        print( 'deque = ',self.dq, '\nfront = ', self.front, '\nrear = ', self.rear)
deque = OutputRestrictedDeque(8)
deque.enqueue(1, 'front')
deque.enqueue(2, 'front')
deque.enqueue(3, 'front')
deque.enqueue(98, 'rear')
deque.enqueue(99, 'rear')
deque.dequeue()<jupyter_output><empty_output><jupyter_text>Linked List<jupyter_code>class Node:
    def __init__(self, item):
        self.item = item
        self.next = None
    
    def show(self):
        print('\ndata =',self.item,'\nnext =',self.next)
class LinkedList:
    def __init__(self):
        self.head = None
ll = LinkedList()
ll.head = Node(1)
second = Node(2)
third = Node(3)
ll.head.next = second
second.next = third
while ll.head != None:
    print(ll.head.item)
    ll.head = ll.head.next<jupyter_output>1
2
3<jupyter_text>Insertion: 1. At Beginning2. Add to end3. Add in the middle  Deletion: 1. From Beginning2. From end3. From the middle<jupyter_code>class LinkedList:
    def __init__(self):
        self.ll = []
        
    def add_at_beginning(self, node):
        self.ll.insert(0, node)
        try: 
            if self.ll[1]:
                self.ll[0].next = self.ll[1]
        except:
            self.ll[0].next = None
        return self.ll
    
    def add_to_end(self, node):
        self.ll.insert(len(self.ll), node)
        self.ll[-2].next = self.ll[-1]
        return self.ll
    
    def add_in_the_mid(self, position, node):
        self.ll.insert(position, node)
        self.ll[position-1].next = self.ll[position]
        self.ll[position].next = self.ll[position+1]
        return self.ll
    
    def delete_from_beginning(self):
        self.ll.pop(0)
        return self.ll
    
    def delete_from_end(self):
        self.ll.pop(len(self.ll)-1)
        self.ll[-1].next = None
        return self.ll
    
    def delete_from_the_mid(self, position):
        self.ll[position-1].next = self.ll[position+1]
        self.ll.pop(position)
        return self.ll
ll = LinkedList()
ll.add_at_beginning(Node(1))
ll.ll[0].show()
ll.add_at_beginning(Node(2))
ll.add_at_beginning(Node(3))
ll.add_to_end(Node(99))
ll.add_in_the_mid(2, Node(50))
ll.delete_from_beginning()
ll.delete_from_end()
ll.delete_from_the_mid(1)
ll.ll[0].next.show()
ll.ll[0].show()<jupyter_output>data = 2 
next = <__main__.Node object at 0x7fd3c7766750><jupyter_text>Doubly Linked List<jupyter_code>class DoublyLinkedList:
    def __init__(self):
        self.head = None
class DoubleNode:
    def __init__(self, item):
        self.prev = None
        self.item = item
        self.next = None
DLL = DoublyLinkedList()
first = DoubleNode(10)
second = DoubleNode(20)
third = DoubleNode(30)<jupyter_output><empty_output><jupyter_text>Forward chaining<jupyter_code>DLL.head = first
first.next = second
second.next = third<jupyter_output><empty_output><jupyter_text>Backward Chaining<jupyter_code>third.prev = second
second.prev = first
first.prev = None<jupyter_output><empty_output><jupyter_text>Finished Building !  Now test it<jupyter_code>DLL.head
DLL.head.item
DLL.head.next.item
DLL.head.next.next.item
DLL.head.next.next.prev.item
DLL.head.next.next.prev.prev.item<jupyter_output><empty_output><jupyter_text>Hash Table<jupyter_code>def check_prime(n):
    for i in range(2,(n//2)+1):
        if n%i == 0:
            return 0
    if n not in [0,1]:
        return 1
    return 0
def get_prime(n):
    if n % 2 == 0:
        n = n + 1
    while not check_prime(n):
        n = n + 2
    return n
get_prime(10)
hashtable = [[]]*10
hashtable
def hashfunction(key):
    capacity = get_prime(10)
    return key%capacity
hashfunction(11)
def insertdata(key, data):
    index = hashfunction(key)
    hashtable[index] = [key, data]
def removedata(key):
    index = hashfunction(key)
    hashtable[index] = []
insertdata(12,12)
hashtable
removedata(12)
hashtable<jupyter_output><empty_output><jupyter_text>Non linear Data structures  Heap Data Structure<jupyter_code>a = [10,11,12,13,14,15,0]
def OK(array, i):
    if array[2*i + 1] < array[i]:
        if array[2*i + 2] < array[i]:
            return True
    else:
        return None
def satisfy_heap(array):
    result = []
    for i in range(int(len(array)/2 - 1),-1,-1):
        if OK(array,i):
            result.append(1)
        else:
            result.append(0)
    if 0 not in result:
        return True
def heapify(array):
    for i in range(int(len(array)/2 - 1),-1,-1):
        if not OK(array,i):
            if array[2*i + 1] > array[i]:
                array[2*i + 1], array[i] = array[i] , array[2*i + 1]
            if array[2*i + 2] > array[i]:
                array[2*i + 2], array[i] = array[i] , array[2*i + 2]
            else:
                continue
    if not satisfy_heap(array):
        heapify(array)
    return array
heapify(a)<jupyter_output><empty_output><jupyter_text>insertion<jupyter_code>a = [10,11,12,13,14,15,0]
a[-1] = 20
heapify(a)<jupyter_output><empty_output><jupyter_text>deletion<jupyter_code>a[2], a[-1] = a[-1], a[2]
a[-1] = 0
heapify(a)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup