committed from zkp

pythonkd · pythonkd · commit f9d166bd6d33 · 2019-01-22T17:05:33.000+08:00
diff --git a/Introduction to algorithms/Queue_Circular.py b/Introduction to algorithms/Queue_Circular.py
@@ -0,0 +1,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()
