""" Circular Queue
1. Below is a class implementation
2. Essential features:
- [Enqueue] puts items into the list via (tail)
- [Dequeue] removes items from the list via (head)
- Wraparound using modulus sign to keep the index...
...within the range of the queue
3. This is an implementation that doesnt require head and tail to...
...have -1 as the default value for an empty list
This is my attempt at shortening the CircularQueue class
Check out the source for more info!
"""
class CircularQueue:
def __init__(self, max_size, start=0):
self._queue = [None]*max_size
self._max_size = max_size
self._size = 0
self._head = self._tail = start
def empty(self):
return self._size == 0
def full(self):
return self._size == self._max_size
def update_tail(self):
self._tail = (self._tail + 1) % self._max_size
def update_head(self):
self._head = (self._head + 1) % self._max_size
def enqueue(self, data): # enqueue
if self.full():
return "Full"
# Put item into queue
self._queue[self._tail] = data
self._size += 1
self.update_tail()
# To check
return data
def dequeue(self): # dequeue
if self.empty():
return "Empty"
# Remove item from queue
data = self._queue[self._head]
self._queue[self._head] = None
self._size -= 1
self.update_head()
# To check
return data
def head_at(self):
return self._head
def tail_at(self):
return self._tail
def max_size_of(self):
return self._max_size
def size_of(self):
return self._size
def display(self):
return self._queue
# Test
from random import randrange
def CQ_Test(CQ):
# Create random list
lst = [randrange(10, 100) for _ in range(10)]
print(f"List: {lst}",
sep = " | ", end = "\n\n")
# Create Empty CQ with length less than lst
len_CQ = len(lst) - 1
CQ = CQ(len_CQ)
print(f"Enq: ",
f"used: {CQ.usedslots()}",
f"H,T: {CQ.head_at()}, {CQ.tail_at()}",
f"CQ: {CQ.display()}",
sep = " | ") ## Display Empty CQ
# Fill CQ completely
for item in lst:
print(f"Enq: {CQ.enq(item)}",
f"used: {CQ.usedslots()}",
f"H,T: {CQ.head_at()}, {CQ.tail_at()}",
f"CQ: {CQ.display()}",
sep = " | ")
print()
# Remove half of CQ
mid = len_CQ // 2
for i in range(mid):
print(f"Deq: {CQ.deq()}",
f"used: {CQ.usedslots()}",
f"H,T: {CQ.head_at()}, {CQ.tail_at()}",
f"CQ: {CQ.display()}",
sep = " | ")
print()
# Fill CQ back to full
for i in range(mid, len_CQ - 1):
print(f"Enq: {CQ.enq(lst[i])}",
f"used: {CQ.usedslots()}",
f"H,T: {CQ.head_at()}, {CQ.tail_at()}",
f"CQ: {CQ.display()}",
sep = " | ")
print()
# Remove all in CQ
for i in range(len_CQ + 1):
print(f"Deq: {CQ.deq()}",
f"used: {CQ.usedslots()}",
f"H,T: {CQ.head_at()}, {CQ.tail_at()}",
f"CQ: {CQ.display()}",
sep = " | ")
CQ_Test(CQ)
"""Latest Edits
1. Removed:
def usedslots(self):
return sum(_ is None for _ in self.q)
- The reason I removed the method size() is that it was not time efficient.
- Instead, updating self.used at enq() and deq() is better.
- It could have just been self.q.count(None) instead lol
"""
"""Linear Queue
Queue is a First In - First Out (FIFO) data structure much like a real queue
- The below is a simple implementation of a Linear Queue
Check out the source for more info!
"""
class LQ:
def __init__(self):
self.q = []
def enq(self, data): # enqueue
self.q.append(data)
def deq(self): #dequeue
if self.q:
return self.q.pop(0)
return "Empty!"
def peek(self):
if self.q:
return self.q[0]
return "Empty!"
def size(self):
return len(self.q)
def display(self):
return self.q
# Test
from random import randrange
def LQ_Test(LQ):
# Create random list
lst = [randrange(10, 100) for _ in range(10)]
print(f"List: {lst}")
# Create Empty LQ
LQ = LQ()
print(f"LQ: {LQ.display()}",
f"Size: {LQ.size()}",
f"Front: {LQ.peek()}",
sep = " | ", end = "\n\n")
# Put items into LQ
for item in lst:
LQ.enq(item)
print(f"Front: {LQ.peek()}",
f"LQ: {LQ.display()}",
sep = " | ", end = "\n\n")
# Remove items from LQ
for _ in range(len(lst)):
print(f"Deq: {LQ.deq()}",
f"Front: {LQ.peek()}",
f"Size: {LQ.size()}",
f"LQ: {LQ.display()}",
sep = " | ")
LQ_tester(LQ)