-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQueue_Circular.py
More file actions
128 lines (104 loc) · 3.19 KB
/
Copy pathQueue_Circular.py
File metadata and controls
128 lines (104 loc) · 3.19 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
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
class Node(object):
def __init__(self, value=None, next=None, previous=None):
self.value, self.next, self.previous = value, next, previous
class CircularDoubleLinkedNode(object):
def __init__(self, maxsize=None):
self.maxsize = maxsize
self.root = Node()
self.root.next = self.root
self.root.previous = self.root
self.length = 0
def __len__(self):
return self.length
def headnode(self):
return self.root.next
def tailnode(self):
return self.root.previous
def append(self, value):
if self.maxsize is not None and self.value >= self.maxsize:
raise Exception('Full')
node = Node(value)
tailnode = self.tailnode()
tailnode.next = node
node.next = self.root
node.previous = tailnode
self.length += 1
self.root.previous = node
def appendleft(self, value):
if self.maxsize is not None and self.value >= self.maxsize:
raise Exception('Full')
node = Node(value)
headnode = self.headnode()
self.root.next = node
node.next = headnode
headnode.previous = node
node.previous = self.root
self.length += 1
def pop(self):
if self.root.next is self.root:
return
tailnode = self.tailnode()
prevnode = tailnode.previous
prevnode.next = self.root
self.root.previous = prevnode
value = tailnode.value
del tailnode
self.length -= 1
return value
def popleft(self):
if self.root.next is self.root:
return
headnode = self.headnode()
self.root.next = headnode.next
headnode.next.previous = self.root
value = headnode.value
del headnode
self.length -= 1
return value
def __iter__(self):
for node in self._iter_node():
yield node.value
def _iter_node(self):
curnode = self.root.next
while curnode is not self.root:
yield curnode
curnode = curnode.next
def remove(self, node):
if self.root.next is self.root:
raise Exception('remove empty CircularDoubleLinkedNode')
prevnode = node.previous
nextnode = node.next
prevnode.next = nextnode
nextnode.previous = prevnode
del node
self.length -= 1
def reverse_node(self):
curnode = self.root.previous
while curnode is not self.root:
yield curnode
curnode = curnode.previous
class Queue(object):
def __init__(self):
self._items = CircularDoubleLinkedNode()
def __len__(self):
return len(self._items)
def __iter__(self):
for item in self._items:
yield item
def push(self, value):
self._items.append(value)
def pop(self):
return self._items.popleft()
def is_empty(self):
return len(self._items) == 0
def test():
q = Queue()
for i in range(5):
q.push(i)
assert list(q) == [i for i in range(5)]
assert len(q) == 5
for i in range(5):
assert q.pop() == i
assert len(q) == 0
if __name__ == "__main__":
test()