使用双端队列模拟栈-白红宇

使用双端队列模拟栈

阅读量：436 次

发布时间：2019-03-06

本文共 2263 字，大约阅读时间需要 7 分钟。

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 pop(self):
        if len(self) == 0:
            raise EmptyError('None!')
        tailnode = self.tailnode()
        value = tailnode.value
        self.remove(tailnode)
        return value
    def popleft(self):
        if len(self) == 0:
            raise EmptyError('None!')
        headnode = self.headnode()
        value = headnode.value
        self.remove(headnode)
        return value
class stack(object):
    def __init__(self):
        self.deque = Deque()
    def push(self,value):
        return self.deque.append(value)
    
    def pop(self):
        return self.deque.pop()
    
    def __len__(self):
        return len(self.deque)
    