使用链表实现队列数据结构的Python程序

队列是一种特殊的线性数据结构，遵循先进先出（FIFO）的原则，即最先进入队列的元素最先出队。在Python中，可以使用列表(list)实现队列，但是列表实现队列的效率不高。因此，使用链表实现队列数据结构是更好的选择。

链表基础知识

链表是一种常见的数据结构，由一系列节点(node)组成。每个节点包含一个数据元素以及指向下一个节点的指针。链表基于指针实现，它s的节点可以随意添加、删除和移动，不需要提前开辟一段连续的内存空间。链表的基本操作包括：插入节点、删除节点、查找节点和遍历链表等。

下面是链表节点的定义：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

其中，val表示节点存储的数据元素，next指针指向下一个节点。如果没有后继节点，则next为None。

队列的实现

使用链表实现队列数据结构，需要注意以下几个方面：

队列的操作包括入队（enqueue）和出队（dequeue）操作；
队列的长度（size）随着元素的入队和出队不断变化；
队首（front）指向待出队的元素，队尾（rear）指向待入队的元素。

下面是链表实现队列的代码：

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

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

    def enqueue(self, x):
        node = ListNode(x)
        if self.is_empty():
            self.front = node
            self.rear = node
        else:
            self.rear.next = node
            self.rear = node
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("队列为空，不能进行出队操作！")
        else:
            node = self.front
            self.front = node.next
            self.size -= 1
            return node.val

    def get_size(self):
        return self.size

队列的测试

为了验证队列的正确性，可以编写以下测试代码：

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.get_size())  # 3
print(q.dequeue())   # 1
print(q.dequeue())   # 2
print(q.get_size())  # 1