-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathqueue.py
More file actions
executable file
·99 lines (74 loc) · 2.98 KB
/
Copy pathqueue.py
File metadata and controls
executable file
·99 lines (74 loc) · 2.98 KB
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
class Queue_custom:
def __init__(self, initial_size=10):
self.arr = [0 for _ in range(initial_size)]
self.next_index = 0
self.front_index = -1
self.queue_size = 0
def enqueue(self, value):
# if queue is already full --> increase capacity
if self.queue_size == len(self.arr):
print('Queue is full, increase capacity')
self._handle_queue_capacity_full()
# enqueue new element
self.arr[self.next_index] = value
self.queue_size += 1
self.next_index = (self.next_index + 1) % len(self.arr)
if self.front_index == -1:
self.front_index = 0
def dequeue(self):
# check if queue is empty
if self.is_empty():
self.front_index = -1 # resetting pointers
self.next_index = 0
return None
# dequeue front element
value = self.arr[self.front_index]
self.arr[self.front_index]=0
self.front_index = (self.front_index + 1) % len(self.arr)
self.queue_size -= 1
return value
def size(self):
return self.queue_size
def is_empty(self):
return self.size() == 0
def front(self):
# check if queue is empty
if self.is_empty():
return None
return self.arr[self.front_index]
def _handle_queue_capacity_full(self):
old_arr = self.arr
self.arr = [0 for _ in range(2 * len(old_arr))]
index = 0
# copy all elements from front of queue (front-index) until end
for i in range(self.front_index, len(old_arr)):
self.arr[index] = old_arr[i]
index += 1
# case: when front-index is ahead of next index
for i in range(0, self.front_index):
self.arr[index] = old_arr[i]
index += 1
# reset pointers
self.front_index = 0
self.next_index = index
queue = Queue_custom(4)
queue.enqueue(1)
print('1.', queue.front_index, queue.next_index, queue.queue_size, queue.arr)
queue.enqueue(2)
print('2.', queue.front_index, queue.next_index, queue.queue_size, queue.arr)
queue.enqueue(3)
print('3.', queue.front_index, queue.next_index, queue.queue_size,queue.arr)
queue.enqueue(4)
print('4.', queue.front_index, queue.next_index, queue.queue_size,queue.arr)
print(queue.dequeue())
print('5.', queue.front_index, queue.next_index, queue.queue_size,queue.arr)
queue.enqueue(5)
print('6.', queue.front_index, queue.next_index, queue.queue_size,queue.arr)
print(queue.dequeue())
print('7.', queue.front_index, queue.next_index, queue.queue_size,queue.arr)
print(queue.dequeue())
print('7.', queue.front_index, queue.next_index, queue.queue_size,queue.arr)
print(queue.dequeue())
print('7.', queue.front_index, queue.next_index, queue.queue_size,queue.arr)
print(queue.dequeue())
print('7.', queue.front_index, queue.next_index, queue.queue_size,queue.arr)