python链式队列

2022年 11月 9日
"""
链式队列
思路分析：
        基于链表构建队列模型
        链表的开端作为对头，结尾位置作为队尾
        单独定义队尾标记，避免每次插入数据遍历
        队头和队尾重叠认为队列为空
"""


# 自定义队列异常
class QueueError(Exception):
    pass


# 节点类
class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


# 队列操作
class LQueue:
    def __init__(self):
        # 定义队头和队尾的变量
        self.front = self.rear = Node(None)

    # 判断是否为空
    def is_empty(self):
        return self.front == self.rear

    # 入队 rear动
    def enqueue(self, val):
        self.rear.next = Node(val)
        self.rear = self.rear.next

    # 出队
    def dequeue(self):
        if self.front == self.rear:
            raise QueueError("Queue is empty")
        # 认为front指向的节点已经出队
        self.front = self.front.next
        return self.front.val