301 队列的实现1 #

1. 队列节点的数据构造
2. 队列的数据构造
3. 队列进站的实现

队列节点的构造 #

这里使用链表实现队列，与栈一样，它是由一个个数据节点构成，每个数据节点除了数据外，还具有指向下一个节点的指针，队列节点的构造如下：

class Node:
    def __init__(self,data):
        self.data=data #用于存储数据
        self.next=None #用于指向下一数据

队列的数据结构 #

一个队列具有头节点和尾节点

class Queue:
    def __init__(self):
        self.front=None #头部指针
        self.rear=None #尾部指针

数据进队列的实现 #

对于一个队列来说，加入新节点需要在尾部加入节点，然后更新尾部指针，定义offer函数实现进队功能

class Node:
    def __init__(self, data):
        self.data = data  # 用于存储数据
        self.next = None  # 用于指向下一数据

class Queue:
    def __init__(self):
        self.front = None  # 头部指针
        self.rear = None  # 尾部指针

    def offer(self, data):
        new_node = Node(data)  # 构造一个节点数据
        if(self.rear == None):
            self.front = new_node
        else:
            self.rear.next = new_node
        self.rear = new_node
        new_node.next = None

    def __str__(self):  # 重载__str__()函数用于,用于print()打印
        if((self.front == None) & (self.rear == None)):
            return("This is a queue structure\n" +
                   "the queue is empty now!!!")
        else:
            return("This is a queue structure\n" +
                   "the rear data is "+str(self.rear.data))

myqueue1 = Queue()  # 实例化一个队列结构
print(myqueue1)
myqueue1.offer(3)  # 进队列
print(myqueue1)
myqueue1.offer(4)  # 进队列
print(myqueue1)

小结 #

• 掌握队列数据节点的构造
• 掌握队列结构的构造，并能实现入队的功能

习题 #

1. 对于一个队列来说为什么需要同时需要头指针和尾指针？
2. 本节课中队列结构中的offer()函数中添加节点前为什么要判断rear是否为None？