5. Circular Queue using Python List

Circular Queue using list¶

• This I think can be one idea for implementing circular queue where we reset the queue as soon we see there are no more elements left in the queue

• hint for more generic implementation: https://www.techiedelight.com/queue-implementation-python/ but this one is incorrect as it keeps on overwriting on the existing items in the queue

In [1]:

class CircularQueue:
    def __init__(self, max_size):
        self.items = [None]*max_size
        self.capacity = max_size
        self.front = -1
        self.rear = -1
        self.count = 0
        
    def __len__(self):
        return self.count
    
    def __repr__(self):
        nodes = []
        counter = 0
        ptr = self.front
        hit_rear = True
        while counter <= self.count:
            if ptr == self.front and hit_rear:
                nodes.append("[Front: %s]" % self.items[ptr])
                hit_rear = False
            elif ptr == self.rear:
                nodes.append("[Rear: %s]" % self.items[ptr])
            else:
                nodes.append("[%s]" % self.items[ptr])
            ptr = (ptr+1) % self.capacity
            counter += 1
            
        return "<-".join(nodes)
    
    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("Queue is full, dequeue some elements")
            return
        if self.front == self.rear == -1:
            print("first element")
            print(f"Inserting: {data} into the queue")
            self.front = self.rear = 0
            self.items[self.rear] = data
            self.rear += 1
            self.count += 1
        else:
            print(f"Inserting: {data} into the queue")
            self.items[self.rear] = data
            self.rear = (self.rear+1) % self.capacity
            self.count += 1
    
    def dequeue(self):
        if not self.is_empty():
            data = self.items[self.front]
            # additional step, though not required
            self.items[self.front] = None
            print(f"Removing: {data} from the front of the queue")
            self.front = (self.front+1) % self.capacity
            self.count -= 1
        # It is fine even if we do not reset the queue
        elif self.count == 0:
            print("resetting queue to -1")
            self.front = self.rear = -1
        else:
            print("empty queue, cannot dequeue")

class CircularQueue: def __init__(self, max_size): self.items = [None]*max_size self.capacity = max_size self.front = -1 self.rear = -1 self.count = 0 def __len__(self): return self.count def __repr__(self): nodes = [] counter = 0 ptr = self.front hit_rear = True while counter <= self.count: if ptr == self.front and hit_rear: nodes.append("[Front: %s]" % self.items[ptr]) hit_rear = False elif ptr == self.rear: nodes.append("[Rear: %s]" % self.items[ptr]) else: nodes.append("[%s]" % self.items[ptr]) ptr = (ptr+1) % self.capacity counter += 1 return "<-".join(nodes) 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("Queue is full, dequeue some elements") return if self.front == self.rear == -1: print("first element") print(f"Inserting: {data} into the queue") self.front = self.rear = 0 self.items[self.rear] = data self.rear += 1 self.count += 1 else: print(f"Inserting: {data} into the queue") self.items[self.rear] = data self.rear = (self.rear+1) % self.capacity self.count += 1 def dequeue(self): if not self.is_empty(): data = self.items[self.front] # additional step, though not required self.items[self.front] = None print(f"Removing: {data} from the front of the queue") self.front = (self.front+1) % self.capacity self.count -= 1 # It is fine even if we do not reset the queue elif self.count == 0: print("resetting queue to -1") self.front = self.rear = -1 else: print("empty queue, cannot dequeue")

In [2]:

queue = CircularQueue(5)

queue = CircularQueue(5)

In [3]:

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

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

first element
Inserting: 10 into the queue
Inserting: 20 into the queue
Inserting: 30 into the queue
Inserting: 40 into the queue
Inserting: 50 into the queue

In [4]:

queue

queue

Out[4]:

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

In [5]:

queue.dequeue()
queue.dequeue()
queue.dequeue()

queue.dequeue() queue.dequeue() queue.dequeue()

Removing: 10 from the front of the queue
Removing: 20 from the front of the queue
Removing: 30 from the front of the queue

In [6]:

queue

queue

Out[6]:

[Front: 40]<-[50]<-[Rear: None]

In [7]:

queue.front

queue.front

Out[7]:

3

In [8]:

queue.rear

queue.rear

Out[8]:

0

In [9]:

queue.items

queue.items

Out[9]:

[None, None, None, 40, 50]

In [10]:

queue.count

queue.count

Out[10]:

2

In [11]:

queue.front

queue.front

Out[11]:

3

In [12]:

queue.rear

queue.rear

Out[12]:

0

In [13]:

queue.enqueue(10)

queue.enqueue(10)

Inserting: 10 into the queue

In [14]:

queue.items

queue.items

Out[14]:

[10, None, None, 40, 50]

In [15]:

queue.enqueue(20)

queue.enqueue(20)

Inserting: 20 into the queue

In [16]:

queue.items

queue.items

Out[16]:

[10, 20, None, 40, 50]

In [17]:

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

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

Removing: 40 from the front of the queue
Removing: 50 from the front of the queue
Removing: 10 from the front of the queue
Removing: 20 from the front of the queue
resetting queue to -1
resetting queue to -1
resetting queue to -1
resetting queue to -1
resetting queue to -1
resetting queue to -1

In [18]:

queue.items

queue.items

Out[18]:

[None, None, None, None, None]

In [19]:

queue.count

queue.count

Out[19]:

0

In [20]:

queue.front

queue.front

Out[20]:

-1

In [21]:

queue.rear

queue.rear

Out[21]:

-1

In [22]:

queue.items

queue.items

Out[22]:

[None, None, None, None, None]

In [23]:

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

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

first element
Inserting: 0 into the queue
Inserting: 1 into the queue
Inserting: 2 into the queue
Inserting: 3 into the queue
Inserting: 4 into the queue
Queue is full, dequeue some elements
Queue is full, dequeue some elements
Queue is full, dequeue some elements
Queue is full, dequeue some elements
Queue is full, dequeue some elements

In [24]:

queue.items

queue.items

Out[24]:

[0, 1, 2, 3, 4]

In [25]:

queue.dequeue()

queue.dequeue()

Removing: 0 from the front of the queue

In [26]:

queue.dequeue()

queue.dequeue()

Removing: 1 from the front of the queue

In [27]:

queue.items

queue.items

Out[27]:

[None, None, 2, 3, 4]

In [28]:

queue.front

queue.front

Out[28]:

2

In [29]:

queue.rear

queue.rear

Out[29]:

0

In [30]:

queue.enqueue(10)

queue.enqueue(10)

Inserting: 10 into the queue

In [31]:

queue.enqueue(20)

queue.enqueue(20)

Inserting: 20 into the queue

In [32]:

queue.enqueue(30)

queue.enqueue(30)

Queue is full, dequeue some elements

In [33]:

queue.items

queue.items

Out[33]:

[10, 20, 2, 3, 4]

In [34]:

queue

queue

Out[34]:

[Front: 2]<-[3]<-[4]<-[10]<-[20]<-[Rear: 2]

In [35]:

queue.front

queue.front

Out[35]:

2

In [36]:

queue.rear

queue.rear

Out[36]:

2

In [ ]: