Deque类插入和删除前后不可互换工作[python]

Question

在我的作业中，我要做一个deque类，让人们从前面和后面插入，也可以从前面和后面删除，这是deque类中4个独立的函数。在

如果我使用insert_front，那么我可以使用remove_front移除队列中的所有内容，但是如果我使用insert_front并尝试使用remove_rear，那么我的程序在执行remove_rear一次之后中断，它将删除后面的部分，但是如果我尝试删除下一个后端，程序会因为不知道下一个后端节点是什么而中断，我已经知道了不知道如何能够跟踪前后，所以我可以互换使用这些功能。反之亦然，插入“后”和“拆下”前。在

我的Deque类代码如下：

def insert_front( self, value ):


    if self._rear==None and len(self)==1:

        node = _DequeNode(value, self._front,self._rear)
        self._front = node
        self._rear=node
    else:
        node = _DequeNode(value, self._front,self._rear)
        self._front = node


    self._size += 1
    return

def insert_rear( self, value ):
    node = _DequeNode(value, self._front,self._rear)
    self._rear = node
    if self._front==None and len(self)==2:
        self._front=node


    self._size += 1
    return

def remove_front( self ):

    if self.is_empty():
        value = None
    else:
        current = self._front
        value = current._value
        self._front = current._next
        self._size -= 1

    return value

def remove_rear( self ):

    if self.is_empty():
        value = None
    else:
        current = self._rear
        value = current._value
        self._rear = current._prev
        self._size -= 1

    return value

这是我的演讲：

^{pr2}$

我在修改代码的时候肯定做错了什么，因为这本来是一个链表，你只能从前面删除和插入，老师让我们把它做成一个前后都有的Deque，我根据我认为应该发生的事情来编辑代码。。在

有人能帮我吗？我一整天都在想办法解决这个问题！ 提前谢谢！！在

Answer 1

这是我写得很快的一个工作版本。在

我还添加了一个__repr__方法，这样您就可以看到发生了什么（这实际上不是{}的一个好实践，除非您还修改了__init__使其能够将输出作为参数。在

您可能还想看看https://github.com/python-mirror/python/blob/master/Modules/_collectionsmodule.c-它包含pythondeque实现。在

class DQ: 
    def __init__(self): 
        self._front = self._rear = None
        self._size = 0

    def insert_front( self, value ):
        self._front = DequeNode(value, prev=self.front)
        if self.size > 0:
            self.front.prev._next = self._front
        else: 
            self._rear = self._front
        self._size += 1

    def insert_rear( self, value ):
        self._rear = DequeNode(value, next=self.rear)
        if self.size > 0:
            self.rear.next._prev = self._rear
        else:
            self._front = self._rear
        self._size += 1

    def pop_front( self ):
        if self.empty:
            raise IndexError("deque is empty")
        else:
            ret = self._front
            self._size -= 1
            self._front = self._front.prev
            if self.front:
                self.front._next = None
            if self.size == 0: 
                self._front = None
            return ret

    def pop_rear( self ):
        if self.empty:
            raise IndexError("deque is empty")
        else:
            ret = self._rear
            self._size -= 1
            self._rear = self._rear.next
            if self.rear: 
                self.rear._prev = None
            if self.size == 0: 
                self._front = None
            return ret

    @property
    def empty(self): 
        return self._size == 0 
    @property
    def size(self): 
        return self._size
    @property
    def front(self): 
        return self._front
    @property
    def rear(self):
        return self._rear

    def __str__(self): 
        cur = self.rear
        l = []
        for i in range(self.size): 
            l.append(cur)
            cur = cur.next
        return str(l)

    def __repr__(self): 
        return self.__str__()



class DequeNode: 
    def __init__(self, value=None, next=None, prev=None):
        self._value = value
        self._next =next
        self._prev = prev

    @property
    def prev(self):
        return self._prev
    @property
    def next(self):
        return self._next

    def __str__(self): 
        return str(self._value)

    def __repr__(self): 
        return str("DequeNode( %s )" %self._value)