6. Circular Queue using Circular Linked List

Circular Queue using Circular Linked List¶

In [1]:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    
    def __repr__(self):
        return "<Node: %s>" % self.data

class Node: def __init__(self, data): self.data = data self.next = None def __repr__(self): return "" % self.data

In [2]:

Node(10)

Node(10)

Out[2]:

<Node: 10>

In [3]:

class CircularQueue:
    def __init__(self, max_size):
        self.front = None
        self.rear = None
        self.capacity = max_size
        self.count = 0
    
    def __len__(self):
        return self.count
    
    def __repr__(self):
        nodes = []
        ptr = self.front
        cycle = 0
        first = True
        
        while ptr:
            if ptr == self.front:
                if cycle >= 1:
                    break
                if first:
                    cycle += 1
                first = False
                nodes.append("[Front: %s]" % ptr.data)
            elif ptr == self.rear:
                nodes.append("[Rear: %s]" % ptr.data)
            else:
                nodes.append("[%s]" % ptr.data)
            ptr = ptr.next
            
        return "<-".join(nodes)
    
    def __iter__(self):
        pass
    
    def is_full(self):
        return self.count == self.capacity
    
    def is_empty(self):
        return self.count == 0
    
    def enqueue(self, data):
        if self.is_full():
            print(f"cannot enqueue: {data}, queue has reached it's maximum initialized capacity")
            return
        
        node = Node(data)
        if self.front == self.rear == None:
            print("Inserting first item in the queue")
            print(f"Inserting: {data} in the queue")
            self.front = self.rear = node
            node.next = node
        else:
            print(f"Inserting: {data} in the queue")
            self.rear.next = node
            node.next = self.front
            self.rear = self.rear.next
        
        self.count += 1
        
    def dequeue(self):
        if self.is_empty():
            print("Queue is empty, no items to dequeue")
            return
        
        
        temp = self.front
        data = self.front.data
        print(f"Removing: {data} from the queue")
        
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.next
            self.rear.next = self.front
        
        self.count -= 1
        del temp

class CircularQueue: def __init__(self, max_size): self.front = None self.rear = None self.capacity = max_size self.count = 0 def __len__(self): return self.count def __repr__(self): nodes = [] ptr = self.front cycle = 0 first = True while ptr: if ptr == self.front: if cycle >= 1: break if first: cycle += 1 first = False nodes.append("[Front: %s]" % ptr.data) elif ptr == self.rear: nodes.append("[Rear: %s]" % ptr.data) else: nodes.append("[%s]" % ptr.data) ptr = ptr.next return "<-".join(nodes) def __iter__(self): pass def is_full(self): return self.count == self.capacity def is_empty(self): return self.count == 0 def enqueue(self, data): if self.is_full(): print(f"cannot enqueue: {data}, queue has reached it's maximum initialized capacity") return node = Node(data) if self.front == self.rear == None: print("Inserting first item in the queue") print(f"Inserting: {data} in the queue") self.front = self.rear = node node.next = node else: print(f"Inserting: {data} in the queue") self.rear.next = node node.next = self.front self.rear = self.rear.next self.count += 1 def dequeue(self): if self.is_empty(): print("Queue is empty, no items to dequeue") return temp = self.front data = self.front.data print(f"Removing: {data} from the queue") if self.front == self.rear: self.front = self.rear = None else: self.front = self.front.next self.rear.next = self.front self.count -= 1 del temp

In [4]:

queue = CircularQueue(5)

queue = CircularQueue(5)

In [5]:

for i in range(10, 100, 10):
    queue.enqueue(i)

for i in range(10, 100, 10): queue.enqueue(i)

Inserting first item in the queue
Inserting: 10 in the queue
Inserting: 20 in the queue
Inserting: 30 in the queue
Inserting: 40 in the queue
Inserting: 50 in the queue
cannot enqueue: 60, queue has reached it's maximum initialized capacity
cannot enqueue: 70, queue has reached it's maximum initialized capacity
cannot enqueue: 80, queue has reached it's maximum initialized capacity
cannot enqueue: 90, queue has reached it's maximum initialized capacity

In [6]:

queue

queue

Out[6]:

[Front: 10]<-[20]<-[30]<-[40]<-[Rear: 50]

In [7]:

queue.dequeue()

print(queue)

print(queue.count)

queue.dequeue() print(queue) print(queue.count)

Removing: 10 from the queue
[Front: 20]<-[30]<-[40]<-[Rear: 50]
4

In [8]:

queue.dequeue()

print(queue)

print(queue.count)

queue.dequeue() print(queue) print(queue.count)

Removing: 20 from the queue
[Front: 30]<-[40]<-[Rear: 50]
3

In [9]:

queue.dequeue()

print(queue)

print(queue.count)

queue.dequeue() print(queue) print(queue.count)

Removing: 30 from the queue
[Front: 40]<-[Rear: 50]
2

In [10]:

queue.dequeue()

print(queue)

print(queue.count)

queue.dequeue() print(queue) print(queue.count)

Removing: 40 from the queue
[Front: 50]
1

In [11]:

queue.dequeue()

print(queue)

print(queue.count)

queue.dequeue() print(queue) print(queue.count)

Removing: 50 from the queue

0

In [12]:

for _ in range(10):
    queue.dequeue()

for _ in range(10): queue.dequeue()

Queue is empty, no items to dequeue
Queue is empty, no items to dequeue
Queue is empty, no items to dequeue
Queue is empty, no items to dequeue
Queue is empty, no items to dequeue
Queue is empty, no items to dequeue
Queue is empty, no items to dequeue
Queue is empty, no items to dequeue
Queue is empty, no items to dequeue
Queue is empty, no items to dequeue

In [13]:

queue

queue

Out[13]:

In [14]:

queue.front

queue.front

In [15]:

queue.rear

queue.rear

In [16]:

for i in range(10, 100, 10):
    queue.enqueue(i)

for i in range(10, 100, 10): queue.enqueue(i)

Inserting first item in the queue
Inserting: 10 in the queue
Inserting: 20 in the queue
Inserting: 30 in the queue
Inserting: 40 in the queue
Inserting: 50 in the queue
cannot enqueue: 60, queue has reached it's maximum initialized capacity
cannot enqueue: 70, queue has reached it's maximum initialized capacity
cannot enqueue: 80, queue has reached it's maximum initialized capacity
cannot enqueue: 90, queue has reached it's maximum initialized capacity

In [17]:

queue

queue

Out[17]:

[Front: 10]<-[20]<-[30]<-[40]<-[Rear: 50]

In [18]:

queue.dequeue()

print(queue)

print(queue.count)

queue.dequeue() print(queue) print(queue.count)

Removing: 10 from the queue
[Front: 20]<-[30]<-[40]<-[Rear: 50]
4

In [19]:

queue.enqueue(100)

print(queue)

print(queue.count)

queue.enqueue(100) print(queue) print(queue.count)

Inserting: 100 in the queue
[Front: 20]<-[30]<-[40]<-[50]<-[Rear: 100]
5

In [20]:

queue.enqueue(-1)

print(queue)

print(queue.count)

queue.enqueue(-1) print(queue) print(queue.count)

cannot enqueue: -1, queue has reached it's maximum initialized capacity
[Front: 20]<-[30]<-[40]<-[50]<-[Rear: 100]
5

In [21]:

queue.dequeue()

print(queue)

print(queue.count)

queue.dequeue() print(queue) print(queue.count)

Removing: 20 from the queue
[Front: 30]<-[40]<-[50]<-[Rear: 100]
4

In [22]:

queue.enqueue(200)

print(queue)

print(queue.count)

queue.enqueue(200) print(queue) print(queue.count)

Inserting: 200 in the queue
[Front: 30]<-[40]<-[50]<-[100]<-[Rear: 200]
5

In [ ]: