blob: 9e9db1e73e72f9e41f9d16f709d48e1cb67cdc96 (
plain)
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
|
# 641. Design Circular Deque
"""
design your implementation of the circular double ended queue (deque).
implement the 'MyCircularDeque' class
"""
class MyCircularDeque(object):
def __init__(self, k):
"""
:type k: int
"""
self.size = 0
self.front = 0
self.rear = 0
self.capacity = k
self.data = [-1] * k
def insertFront(self, value):
"""
:type value: int
:rtype: bool
"""
if self.isFull():
return False
if self.isEmpty():
self.data[self.front] = value
else:
self.front = (self.front - 1) % self.capacity
self.data[self.front] = value
self.size += 1
return True
def insertLast(self, value):
"""
:type value: int
:rtype: bool
"""
if self.isFull():
return False
if self.isEmpty():
self.data[self.rear] = value
else:
self.rear = (self.rear + 1) % self.capacity
self.data[self.rear] = value
self.size += 1
return True
def deleteFront(self):
"""
:rtype: bool
"""
if self.isEmpty():
return False
self.data[self.front] = -1
self.front = (self.front + 1) % self.capacity
self.size -= 1
if self.isEmpty():
self.rear = self.front
return True
def deleteLast(self):
"""
:rtype: bool
"""
if self.isEmpty():
return False
self.data[self.rear] = -1
self.rear = (self.rear - 1) % self.capacity
self.size -= 1
if self.isEmpty():
self.front = self.rear
return True
def getFront(self):
"""
:rtype: int
"""
return self.data[self.front]
def getRear(self):
"""
:rtype: int
"""
return self.data[self.rear]
def isEmpty(self):
"""
:rtype: bool
"""
return self.size == 0
def isFull(self):
"""
:rtype: bool
"""
return self.size == self.capacity
if __name__ == "__main__":
obj = MyCircularDeque(3)
print(obj.insertLast(1))
print(obj.insertLast(2))
print(obj.insertFront(3))
print(obj.insertFront(4))
print(obj.getRear())
print(obj.isFull())
print(obj.deleteLast())
print(obj.insertFront(4))
print(obj.getFront())
|