Python/data_structures/queue/priority_queue_using_list.py at master · imanghotbi-python/Python · 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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
"""
Pure Python implementations of a Fixed Priority Queue and an Element Priority Queue
using Python lists.
"""


classOverFlowError(Exception):
pass


classUnderFlowError(Exception):
pass


classFixedPriorityQueue:
"""
 Tasks can be added to a Priority Queue at any time and in any order but when Tasks
 are removed then the Task with the highest priority is removed in FIFO order. In
 code we will use three levels of priority with priority zero Tasks being the most
 urgent (high priority) and priority 2 tasks being the least urgent.

 Examples
 >>> fpq = FixedPriorityQueue()
 >>> fpq.enqueue(0, 10)
 >>> fpq.enqueue(1, 70)
 >>> fpq.enqueue(0, 100)
 >>> fpq.enqueue(2, 1)
 >>> fpq.enqueue(2, 5)
 >>> fpq.enqueue(1, 7)
 >>> fpq.enqueue(2, 4)
 >>> fpq.enqueue(1, 64)
 >>> fpq.enqueue(0, 128)
 >>> print(fpq)
 Priority 0: [10, 100, 128]
 Priority 1: [70, 7, 64]
 Priority 2: [1, 5, 4]
 >>> fpq.dequeue()
 10
 >>> fpq.dequeue()
 100
 >>> fpq.dequeue()
 128
 >>> fpq.dequeue()
 70
 >>> fpq.dequeue()
 7
 >>> print(fpq)
 Priority 0: []
 Priority 1: [64]
 Priority 2: [1, 5, 4]
 >>> fpq.dequeue()
 64
 >>> fpq.dequeue()
 1
 >>> fpq.dequeue()
 5
 >>> fpq.dequeue()
 4
 >>> fpq.dequeue()
 Traceback (most recent call last):
 ...
 data_structures.queue.priority_queue_using_list.UnderFlowError: All queues are empty
 >>> print(fpq)
 Priority 0: []
 Priority 1: []
 Priority 2: []
 """

def__init__(self):
self.queues= [
 [],
 [],
 [],
 ]

defenqueue(self, priority: int, data: int) ->None:
"""
 Add an element to a queue based on its priority.
 If the priority is invalid ValueError is raised.
 If the queue is full an OverFlowError is raised.
 """
try:
iflen(self.queues[priority]) >=100:
raiseOverflowError("Maximum queue size is 100")
self.queues[priority].append(data)
exceptIndexError:
raiseValueError("Valid priorities are 0, 1, and 2")

defdequeue(self) ->int:
"""
 Return the highest priority element in FIFO order.
 If the queue is empty then an under flow exception is raised.
 """
forqueueinself.queues:
ifqueue:
returnqueue.pop(0)
raiseUnderFlowError("All queues are empty")

def__str__(self) ->str:
return"\n".join(f"Priority {i}: {q}"fori, qinenumerate(self.queues))


classElementPriorityQueue:
"""
 Element Priority Queue is the same as Fixed Priority Queue except that the value of
 the element itself is the priority. The rules for priorities are the same the as
 Fixed Priority Queue.

 >>> epq = ElementPriorityQueue()
 >>> epq.enqueue(10)
 >>> epq.enqueue(70)
 >>> epq.enqueue(4)
 >>> epq.enqueue(1)
 >>> epq.enqueue(5)
 >>> epq.enqueue(7)
 >>> epq.enqueue(4)
 >>> epq.enqueue(64)
 >>> epq.enqueue(128)
 >>> print(epq)
 [10, 70, 4, 1, 5, 7, 4, 64, 128]
 >>> epq.dequeue()
 1
 >>> epq.dequeue()
 4
 >>> epq.dequeue()
 4
 >>> epq.dequeue()
 5
 >>> epq.dequeue()
 7
 >>> epq.dequeue()
 10
 >>> print(epq)
 [70, 64, 128]
 >>> epq.dequeue()
 64
 >>> epq.dequeue()
 70
 >>> epq.dequeue()
 128
 >>> epq.dequeue()
 Traceback (most recent call last):
 ...
 data_structures.queue.priority_queue_using_list.UnderFlowError: The queue is empty
 >>> print(epq)
 []
 """

def__init__(self):
self.queue= []

defenqueue(self, data: int) ->None:
"""
 This function enters the element into the queue
 If the queue is full an Exception is raised saying Over Flow!
 """
iflen(self.queue) ==100:
raiseOverFlowError("Maximum queue size is 100")
self.queue.append(data)

defdequeue(self) ->int:
"""
 Return the highest priority element in FIFO order.
 If the queue is empty then an under flow exception is raised.
 """
ifnotself.queue:
raiseUnderFlowError("The queue is empty")
else:
data=min(self.queue)
self.queue.remove(data)
returndata

def__str__(self) ->str:
"""
 Prints all the elements within the Element Priority Queue
 """
returnstr(self.queue)


deffixed_priority_queue():
fpq=FixedPriorityQueue()
fpq.enqueue(0, 10)
fpq.enqueue(1, 70)
fpq.enqueue(0, 100)
fpq.enqueue(2, 1)
fpq.enqueue(2, 5)
fpq.enqueue(1, 7)
fpq.enqueue(2, 4)
fpq.enqueue(1, 64)
fpq.enqueue(0, 128)
print(fpq)
print(fpq.dequeue())
print(fpq.dequeue())
print(fpq.dequeue())
print(fpq.dequeue())
print(fpq.dequeue())
print(fpq)
print(fpq.dequeue())
print(fpq.dequeue())
print(fpq.dequeue())
print(fpq.dequeue())
print(fpq.dequeue())


defelement_priority_queue():
epq=ElementPriorityQueue()
epq.enqueue(10)
epq.enqueue(70)
epq.enqueue(100)
epq.enqueue(1)
epq.enqueue(5)
epq.enqueue(7)
epq.enqueue(4)
epq.enqueue(64)
epq.enqueue(128)
print(epq)
print(epq.dequeue())
print(epq.dequeue())
print(epq.dequeue())
print(epq.dequeue())
print(epq.dequeue())
print(epq)
print(epq.dequeue())
print(epq.dequeue())
print(epq.dequeue())
print(epq.dequeue())
print(epq.dequeue())


if__name__=="__main__":
fixed_priority_queue()
element_priority_queue()