队列的链表实现(python语言)

队列的链表实现(python语言)

#定义链表中的结点类
class Node:
    def __init__(self):
        self.data = None
        self.next = None


#定义队列类
class YouQueue:
	#初始化头结点，front和rear两个指针指向这个头结点
    def __init__(self):
        head = Node()
        self.front = head
        self.rear = head

    #判断队列是否为空，只需要判断头结点指向的下一个结点是否为空即可
    def isEmpty(self):
        return self.front.next == None

    #获取队列中元素个数
    def size(self):
        if self.front.next:
            n = 0
            cur = self.front.next
            while cur != None:
                n += 1
                cur = cur.next
            return n
        else:
            print("队列为空")

    #入队列，将元素插入到队列的队尾(也即链表的尾部)
    def enQueue(self,e):
        node = Node()
        node.data = e
        if self.front.next != None:
            self.rear.next = node
            self.rear = node
        else:
            self.front.next = node
            self.rear = node

    #出队列，删除队列首元素(也即删除对应链表的首结点)
    def deQueue(self):
        if self.front.next != None:
            cur = self.front.next
            self.front.next = cur.next
        else:
            print("出队列失败，因为队列为空")

    #获取队列首元素
    def getFront(self):
        if self.front.next != None:
            return self.front.next.data
        else:
            print("获取队列首元素失败，因为队列为空")

    #获取队列尾元素
    def getRear(self):
        if self.rear.data != None:
            return self.rear.data
        else:
            print("获取队列尾元素失败，因为队列为空")


if __name__ == "__main__":
    queue = YouQueue()
    queue.enQueue(1)
    queue.enQueue(2)
    print("队列头元素为:{}".format(queue.getFront()))
    print("队列尾元素为:{}".format(queue.getRear()))
    print("队列大小为:{}".format(queue.size()))
    queue.deQueue()
    print("队列头元素为:{}".format(queue.getFront()))
    print("队列尾元素为:{}".format(queue.getRear()))
    print("队列大小为:{}".format(queue.size()))