首页 > 其他 > 详细

双端队列(继承有问题需要改)

时间:2020-07-01 13:22:38      阅读:46      评论:0      收藏:0      [点我收藏+]
class Node(object):
    def __init__(self,value=None,prev=None,next=None):
        self.value,self.prev,self.next = value,prev,next

class DoubleLinkedList(object):
    def __init__(self,maxsieze=None):
        self.maxsieze=maxsieze
        node = Node()
        node.next,node.prev = node,node
        self.root = node
        self.length = 0
    
    def __len__(self):
        return self.length

    def headnode(self):
        return self.root.next
    
    def tailnode(self):
        return self.root.prev
    
    def append(self,value):
        if self.maxsieze is not None and len(self) > self.maxsieze:
            raise Exception("List is Full")
        node = Node(value=value)
        tailnode = self.tailnode()

        tailnode.next = node
        node.prev = tailnode
        node.next = self.root
        self.root.prev = node  #互指

        self.length += 1

    def appendleft(self,value):
        if self.maxsieze is not None and len(self) > self.maxsieze:
            raise Exception("List is Full")
        node = Node(value=value)

        if self.root.next is self.root:             #如果链表为空
            node.next = self.root
            node.prev = self.root
            self.root.next = node
            self.root.prev = node
        else:
            node.prev = self.root
            headnode = self.root.next
            node.next = headnode
            headnode.prev = node
            self.root.next = node

        self.length += 1
    
    def remove(self,node):                          #删除为O(1) 所以删除节点而不是值
        if node is self.root:
            return
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
        self.length -= 1
        return node

    def iter_node(self):
        if self.root.next is self.root:
            return
        curnode = self.root.next
        while curnode.next is not self.root:
            yield curnode
            curnode = curnode.next
        yield curnode

    def __iter__(self):
        for node in self.iter_node():
            yield node.value

    def iter_node_reverse(self):
        if self.root.prev is self.root:
            return
        curnode = self.root.prev
        while curnode.prev is not self.root:
            yield curnode
            curnode = curnode.prev
        yield curnode

class FullError(Exception):
    pass
class EmptyError(Exception):
    pass

class Deque(DoubleLinkedList):
    def __init__(self,maxsieze=None):
       self.maxsieze = maxsieze

    def pop(self,node):
        tailnode = self.tailnode()
        self.remove(tailnode)

    def popleft(self,node):
        headnode = self.headnode()
        self.remove(headnode)
        
def testdeque():
    dq = Deque()
    dq.append(0)
    dq.append(1)
    dq.append(2)
    dq.append(3)
    dq.append(4)
    dq.append(5)

    assert list(dq) == [0,1,2,3,4,5]

双端队列(继承有问题需要改)

原文:https://www.cnblogs.com/mylearnpark/p/13218660.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!