"""

    链式存储-队列

    linkqueue.py

    代码实现

    思路：

    1.入队，

    2.出队，

    3.判断空满

"""

# 异常类

class QueueError(Exception):

    pass

# 节点生成类

class Node:

    """

    思路：将自定义的类视为节点的生成类，

            实例对象中包含数据的部分和下一个节点的next

    """

    def __init__(self,val,next = None):

        self.val =  val # 有用数据

        self.next = next # 循环下一个节点的关系

# 链式存储队列类-队头删除，队尾加入，判断空满等

class LinkQueue01:

    """

    头尾选择一端做队头，另一端队尾，队头删除，队尾插入，总有一端需要遍历

    改进思路：标记头部和尾部，不需要遍历

    """

    def __init__(self):

        # 标记头部位置

        self._first = Node(None)

    # 队头删除

    def dequeue(self):

        p = self._first

        if p.next is None:

            raise QueueError("queue is empty")

        else:

            p.next = p.next.next

    # 队尾插入

    def enqueue(self, val):

        p = self._first

        if p.next is None:

            p.next = Node(val)

        else:

            while p.next is not None:

                p = p.next

            p.next = Node(val)

    # 判断队列为空

    def is_empty(self):

        if self._first.next is None:

            return True

        else:

            return False

    # 遍历队列

    def show(self):

        # 队列为空时，报异常

        if self._first.next is None:

            raise QueueError("queue is empty")

        else:

            p = self._first.next # 第一个有限节点

            while p is not None:

                print(p.val)

                p = p.next # p 向后移动

# print("-"*30)

# if __name__ == "__main__":

#     lq = LinkQueue()

#     print(lq.is_empty())

#     #lq.delete_node()

#     # lq.show()

#     lq.enqueue(1)

#     lq.show()

#     print("***")

#     # lq.insert_end(2)

#     #print(lq.is_empty())

#     lq.enqueue(2)

#     lq.enqueue(3)

#     lq.show()

#     print("***")

#     lq.enqueue(4)

#     lq.show()

#     #print(lq.is_empty())

#     #lq.dequeue()

#     #lq.show()

#-------------------------------------------------

"""

链式队列的另一种实现

重点代码

思路分析：

1.基于链表构建队列模型

2.链表的开端作为队头，结尾位置作为队尾

3.单独定义队尾进行标记，每次插入数据不需要遍历

4.当队头和队尾重叠时，认为队列为空

"""

class LinkQueue:

    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

    # 出队，front动,指向谁，谁出队

    def dequeue(self):

        if self.front == self.rear:

            raise  QueueError("queue is empty")

        self.front = self.front.next

        return self.front.val  # 指向他，但实际出队

if __name__ == "__main__":

    print("-"*30)

    lq = LinkQueue()

    lq.enqueue(1)

    lq.enqueue(2)

    lq.enqueue(3)

    lq.enqueue(4)

    print(lq.dequeue()) # 1