-
Notifications
You must be signed in to change notification settings - Fork 0
/
622-design-circular-queue.py
91 lines (69 loc) · 2.1 KB
/
622-design-circular-queue.py
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
"""
Init(): h,r = -1, [None, None, None]
h,r
1. Enqueue(1): [1, None, None]
h r
2. Enqueue(2): [1, 2, None]
h r
3. Enqueue(3): [1, 2, 3]
4. Enqueue(4): -> full
h r
5. Dequeue(): [None, 2, 3]
r h
6. Enqueue(4): [4, 2, 3]
7. Enqueue(5): -> full
==> check full: (tail + 1) % size = head
r h
8. Dnqueue(): [4, None, 3]
h,r
9. Dnqueue(): [4, None, None]
10. Dequeue(): h,r = -1, [None, None, None]
==> check empty: head = -1 or head == tail. let head = -1, tail = -1
"""
class MyCircularQueue:
def __init__(self, k: int):
self.size = k
self.queue = [None] * k
self.head = -1
self.tail = -1
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
if self.isEmpty():
self.head = 0
self.tail = (self.tail + 1) % self.size
self.queue[self.tail] = value
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
if self.head == self.tail:
self.queue[self.head] = None
self.head = -1
self.tail = -1
return True
self.queue[self.head] = None
self.head = (self.head + 1) % self.size
return True
def Front(self) -> int:
if self.isEmpty():
return -1
else:
return self.queue[self.head]
def Rear(self) -> int:
if self.isEmpty():
return -1
else:
return self.queue[self.tail]
def isEmpty(self) -> bool:
return self.head == -1
def isFull(self) -> bool:
return ((self.tail + 1) % self.size) == self.head
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()