338Lab5/ex5.py at main · shivanshiv/338Lab5 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class CircularQueueArray:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1

    def enqueue(self, value):
        if (self.rear + 1) % self.size == self.front:
            print("enqueue None")  # Queue is full
            return
        if self.front == -1:
            self.front = self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = value
        print(f"enqueue {value}")

    def dequeue(self):
        if self.front == -1:
            print("dequeue None")
            return None
        value = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.size
        print(f"dequeue {value}")
        return value

    def peek(self):
        if self.front == -1:
            print("peek None")
            return None
        print(f"peek {self.queue[self.front]}")
        return self.queue[self.front]

class CircularQueueNode:
    def __init__(self, value):
        self.value = value
        self.next = None

class CircularQueueLinkedList:
    def __init__(self, size):
        self.size = size
        self.count = 0
        self.front = self.rear = None

    def enqueue(self, value):
        if self.count == self.size:
            print("enqueue None")
            return
        new_node = CircularQueueNode(value)
        if not self.front:
            self.front = self.rear = new_node
            self.rear.next = self.front  # Circular link
        else:
            self.rear.next = new_node
            self.rear = new_node
            self.rear.next = self.front
        self.count += 1
        print(f"enqueue {value}")

    def dequeue(self):
        if self.count == 0:
            print("dequeue None")
            return None
        value = self.front.value
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.next
            self.rear.next = self.front
        self.count -= 1
        print(f"dequeue {value}")
        return value

    def peek(self):
        if self.count == 0:
            print("peek None")
            return None
        print(f"peek {self.front.value}")
        return self.front.value

def test_circular_queues():
    cq = CircularQueueArray(5)
    cq.enqueue(1)
    cq.enqueue(2)
    cq.enqueue(3)
    cq.enqueue(4)
    cq.enqueue(5)
    cq.enqueue(6)  # Full queue
    cq.peek()
    cq.dequeue()
    cq.dequeue()
    cq.enqueue(6)
    cq.enqueue(7)  # Wraps around
    cq.dequeue()
    cq.dequeue()
    cq.dequeue()
    cq.dequeue()
    cq.dequeue()
    cq.dequeue()  # Empty queue

test_circular_queues()