1+ # Queue with capacity / maximum size (Circular Queue) implementation using Py List
2+ # Enqueue and Dequeue TC is O(n), rest is O(1) as well as SC of all
3+ # Circular Queue happens to prevent unused memory allocation
4+ # All TC and SC is O(1) - constant
5+
6+
7+ class Queue :
8+ def __init__ (self , max_size ):
9+ # init empty list with None values
10+ self .list = max_size * [None ]
11+ self .max_size = max_size
12+ self .start = - 1
13+ self .top = - 1
14+
15+ def __str__ (self ):
16+ values = [str (x ) for x in self .list ]
17+ return ' ' .join (values )
18+
19+
20+ def isFull (self ):
21+ # top circles and reaches to start
22+ if self .top + 1 == self .start :
23+ return True
24+ elif self .start == 0 and self .top + 1 == self .max_size :
25+ return True
26+ else :
27+ return False
28+
29+
30+ def isEmpty (self ):
31+ # top has no value
32+ if self .top == - 1 :
33+ return True
34+ else :
35+ return False
36+
37+
38+ # insert/push
39+ def enqueue (self , value ):
40+ if self .isFull ():
41+ return "Queue is full"
42+ else :
43+ if self .top + 1 == self .max_size :
44+ self .top = 0
45+ else :
46+ self .top += 1
47+ if self .start == - 1 :
48+ self .start = 0
49+ self .list [self .top ] = value
50+ return "Element inserted"
51+
52+
53+ # remove/pop
54+ def dequeue (self ):
55+ if self .isEmpty ():
56+ return "Queue is empty"
57+ else :
58+ first_element = self .list [self .start ]
59+ start = self .start
60+ # if only element in queue
61+ if self .start == self .top :
62+ self .start = - 1
63+ self .top = - 1
64+ # if last element
65+ elif self .start + 1 == self .max_size :
66+ self .start = 0
67+ else :
68+ self .start += 1
69+ # set its place to none
70+ self .list [start ] = None
71+ return first_element
72+
73+
74+ def peek (self ):
75+ if self .isEmpty ():
76+ return "Queue is empty"
77+ else :
78+ return self .list [self .start ]
79+
80+
81+ def delete (self ):
82+ self .list = self .max_size * [None ]
83+ self .top = - 1
84+ self .start = - 1
0 commit comments