04 Data Structures

Data Structures

Stack

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.isEmpty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.isEmpty():
            return self.items[-1]
        return None

Linear Queue

class Queue:
    def __init__(self, size):
        self.queue = [None] * size
        self.front = 0
        self.rear = -1
        self.size = size

    def isEmpty(self):
        return self.front > self.rear

    def isFull(self):
        return self.rear == self.size - 1

    def enqueue(self, item):
        if not self.isFull():
            self.rear += 1
            self.queue[self.rear] = item

    def dequeue(self):
        if not self.isEmpty():
            item = self.queue[self.front]
            self.front += 1
            return item
        return None

Circular Queue

class CircularQueue:
    def __init__(self, size):
        self.queue = [None] * size
        self.front = 0
        self.rear = 0
        self.count = 0
        self.size = size

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.size

    def enqueue(self, item):
        if not self.isFull():
            self.queue[self.rear] = item
            self.rear = (self.rear + 1) % self.size
            self.count += 1

    def dequeue(self):
        if not self.isEmpty():
            item = self.queue[self.front]
            self.front = (self.front + 1) % self.size
            self.count -= 1
            return item
        return None

Linear Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insertFront(self, item):
        newNode = Node(item)
        newNode.next = self.head
        self.head = newNode

    def insertEnd(self, item):
        newNode = Node(item)

        if self.head is None:
            self.head = newNode
            return

        current = self.head
        while current.next is not None:
            current = current.next

        current.next = newNode

    def search(self, key):
        current = self.head

        while current is not None:
            if current.data == key:
                return current
            current = current.next

        return None

    def delete(self, key):
        current = self.head
        previous = None

        while current is not None and current.data != key:
            previous = current
            current = current.next

        if current is None:
            return

        if previous is None:
            self.head = current.next
        else:
            previous.next = current.next

    def display(self):
        current = self.head

        while current is not None:
            print(current.data)
            current = current.next