【python】数据结构与算法—双端队列(二)

小半 • 2023年1月12日下午2:57 • 技术随笔 • 阅读 248

一、双端队列的特点：

可以对两端进行操作：队尾入队，队首出队；队尾出队，队首入队；

二、双端队列要实现的操作：

三、代码块（链表实现）

class Node():
    def __init__(self,data,_next=None):
        self.data=data  #数据域
        self.next=_next  #指针域

class Deque():
    def __init__(self):
        self.head=None #对头
        self.rear=None  #队尾
        self._length=0  #队列的长度

    def is_empty(self):
        return self._length==0

    def length(self):
        return self._length
    def items(self):
        cur=self.head
        while cur:
            print(cur.data)
            cur=cur.next
        print()

    def push(self,item):
        #队尾添加一个元素item
        #队列为空
        node=Node(item)
        if self.is_empty():
            self.head=node
            self.rear=node
        # 队列不为空
        else:
            self.rear.next=node
            self.rear=node
        self._length+=1

    def push_left(self,item):
        #再队首添加一个节点
        node=Node(item)
        if self.is_empty():
            self.head=node
            self.rear=node
        else:
            node.next=self.head
            self.head=node
        self._length+=1

    def pop(self):
        #弹出队首元素
        if self.is_empty():
            raise ValueError('双端队列为空')
        value=self.head.data
        self.head=self.head.next
        self._length-=1
        if self._length==0:
            self.rear=None
        return value

    def pop_right(self):
        #弹出队尾元素
        if self.is_empty():
            raise ValueError('双端队列为空')
        if self.length()==1:
            return self.pop()
        cur=self.head
        value=self.rear.data
        while cur.next!=self.rear:
            cur=cur.next
        self.rear=cur
        cur.next=None
        self._length-=1
        return value
    def peek(self):
        if self.is_empty():
            raise ValueError('双端队列为空')
        return self.head.data


if __name__ == '__main__':
    deque = Deque()
    deque.push(1)  # 1
    deque.push(2)  # 1,2
    deque.push_left(3)  # 3,1,2
    deque.push_left(4)  # 4,3,1,2
    deque.items()
    deque.pop()  # 3,1,2
    deque.pop_right()  # 3,1
    deque.items()