aboutsummaryrefslogtreecommitdiff
path: root/design_circular_queue.py
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())