【7】数据结构的队列篇章

队列的定义

• 定义：队列（Queue）是一种常见的数据结构，它遵循“先进先出”（First In First Out，FIFO）的原则。类似于排队买票的情况，排在前面的先离开队列，后面来的排在队尾。
• 特点：
  • 队列只允许在一端删除，在另一端插入的线性表
  • 允许删除的一端称为队首，允许插入的一端称为队尾
  • 向队列中插入元素称入队，从队列中删除元素称为出队
• 队列示意图

顺序队列的实现

初始化

class SeqQueue:"""顺序队列的定义"""def __init__(self, max):"""顺序队列的初始化:param max: 队列大小"""self.max = max# 存储队列元素self.data = [None for i in range(self.max)]# 队首指针self.front = 0# 队尾指针self.rear = 0

入队

• 核心思想
  • 检查队列是否已满
  • 在队尾插入元素值
  • 队尾指针加1
• 入队示意图

• 代码实现

    def enter(self, data):"""入队:param data: 入队元素:return:"""# 队满情况if self.rear == self.max:raise IndexError('队列已满')# 在队尾插入新的关键字self.data[self.rear] = data# 队尾指针加1self.rear += 1

出队

• 核心思想
  • 检查队列是否为空
  • 获取队首元素
  • 队首指针front向后移动一格
• 出队示意图

• 代码实现

    def delete(self):"""出队:return: 出队元素"""# 队空if self.front == self.rear:raise IndexError('队空')# 获取出队元素data = self.data[self.front]# 队首指向下一个元素位置self.front += 1return data

顺序队列总代码与调试

# 10.顺序队列
class SeqQueue:"""顺序队列的定义"""def __init__(self, max):"""顺序队列的初始化:param max: 队列大小"""self.max = max# 存储队列元素self.data = [None for i in range(self.max)]# 队首指针self.front = 0# 队尾指针self.rear = 0def enter(self, data):"""入队:param data: 入队元素:return:"""# 队满情况if self.rear == self.max:raise IndexError('队列已满')# 在队尾插入新的关键字self.data[self.rear] = data# 队尾指针加1self.rear += 1def delete(self):"""出队:return: 出队元素"""# 队空if self.front == self.rear:raise IndexError('队空')# 获取出队元素data = self.data[self.front]# 队首指向下一个元素位置self.front += 1return dataif __name__ == '__main__':print('PyCharm')# 10.队列seqQueue = SeqQueue(8)# 10.1入队seqQueue.enter(10)seqQueue.enter(20)seqQueue.enter(30)# 10.2出队data = seqQueue.delete()print('当前出队元素：', data)data = seqQueue.delete()print('当前出队元素：', data)# 入队seqQueue.enter(40)seqQueue.enter(50)seqQueue.enter(60)# 出队data = seqQueue.delete()print('当前出队元素：', data)data = seqQueue.delete()print('当前出队元素：', data)data = seqQueue.delete()print('当前出队元素：', data)

循环队列的实现

• 顺序队列易出现队列溢出的情况，针对这种情况的解决思路，设计了循环队列的线性表。
• 顺序队列中存在的假溢出现象

• 循环队列的出入队解决情况

• 设定
  • 队首取下一个位置为：(front + 1) % max
  • 队尾取下一个位置为：(rear + 1) % max
  • 队空：front == rear
  • 队满：(rear + 1) % max == front

初始化

• 初始化

class CSeqQueue:"""顺序队列的定义"""def __init__(self, max):"""顺序队列的初始化:param max: 队列大小"""self.max = max# 存储队列元素self.data = [None for i in range(self.max)]# 队首指针self.front = 0# 队尾指针self.rear = 0

• 是否为空

    def isEmpty(self):"""循环队列是否为空:return: true or false"""return self.front ==self.rear

入队

• 核心思想
  • 检查队列是否已满
  • 在队尾插入元素值
  • 取队尾的下一个位置
• 代码实现

    def enter(self, data):"""入队:param data: 入队元素:return:"""# 队列满的情况if(self.rear + 1)% self.max == self.front:raise IndexError('队列已满')# 在队尾插入dataself.data[self.rear] = data# 修改队尾指针self.rear = (self.rear + 1) % self.max

出队

• 核心思想
  • 检查队列是否为空
  • 获取队首元素
  • 取队首的下一个位置
• 代码实现

    def delete(self):"""出队:return: 返回队首元素"""# 队空if self.isEmpty():raise IndexError('队列为空')# 获队首元素data = self.data[self.front]# 修改队首指针self.front = (self.front + 1) % self.max#返回return data

获取队首元素

    def peak(self):"""获取队首元素:return: 队首元素"""# 队空if self.isEmpty():raise IndexError('队列为空')# 返回队首元素return self.data[self.front]

循环队列总代码与调试

# 11.循环队列
class CSeqQueue:"""顺序队列的定义"""def __init__(self, max):"""顺序队列的初始化:param max: 队列大小"""self.max = max# 存储队列元素self.data = [None for i in range(self.max)]# 队首指针self.front = 0# 队尾指针self.rear = 0def isEmpty(self):"""循环队列是否为空:return: true or false"""return self.front ==self.reardef enter(self, data):"""入队:param data: 入队元素:return:"""# 队列满的情况if(self.rear + 1)% self.max == self.front:raise IndexError('队列已满')# 在队尾插入dataself.data[self.rear] = data# 修改队尾指针self.rear = (self.rear + 1) % self.maxdef delete(self):"""出队:return: 返回队首元素"""# 队空if self.isEmpty():raise IndexError('队列为空')# 获队首元素data = self.data[self.front]# 修改队首指针self.front = (self.front + 1) % self.max#返回return datadef peak(self):"""获取队首元素:return: 队首元素"""# 队空if self.isEmpty():raise IndexError('队列为空')# 返回队首元素return self.data[self.front]if __name__ == '__main__':print('PyCharm')# 11.循环队列cseqQueue = CSeqQueue(5)# 入队cseqQueue.enter(10)cseqQueue.enter(20)cseqQueue.enter(30)print('输出队首元素：', cseqQueue.peak())# 出队10data = cseqQueue.delete()print('出队的元素：', data)print('队首元素：', cseqQueue.peak())# 出队20data = cseqQueue.delete()print('出队的元素：', data)print('队首元素：', cseqQueue.peak())# 入队cseqQueue.enter(40)cseqQueue.enter(50)cseqQueue.enter(60)print('队首元素：', cseqQueue.peak())

链式队列的实现

• 结点设置：与单链表一致，包括数据域data与指针域next。
• 链式队列示意图
  
• 代码实现

class Node:"""定义链式队列结点"""def __init__(self, data):# 数据域self.data = data# 指针域self.next = None

链式队列的初始化

• 初始化

    def __init__(self):"""链式队列初始化"""# 队首结点指向Noneself.front = Node(None)# 队尾指针指向队首self.rear = self.front

• 是否为空

    def isEmpty(self):"""判断是否为空:return: true or false"""return self.front == self.rear

入队

• 核心思想
  • 队尾的next指针指向新结点
  • 队尾指针指向新结点
• 入队示意图
  
• 代码实现

    def enter(self, data):"""入队:param data: 入队元素值"""# 创建新结点newNode = Node(data)self.rear.next = newNodeself.rear = newNode

出队

• 核心思想
  • 检查队列是否为空
  • 保留队首结点
  • 将队首结点的next指针指向队首结点的后继结点，实现删除
• 出队示意图
  
• 代码实现

    def delete(self):"""出队:return: 出队值"""# 队列为空if self.isEmpty():raise IndexError('队列为空')else:node = self.front.next# 队首结点的next指向队首结点的后继结点self.front.next = node.next# 返回出队结点return node

获取队首元素

    def peak(self):"""获取队首元素:return: 队首元素"""# 队列为空if self.isEmpty():raise IndexError('队列为空')else:# 返回队首元素return self.front.next.data

链式队列总代码与调试

# 链式队列
class Node:"""定义链式队列结点"""def __init__(self, data):# 数据域self.data = data# 指针域self.next = Noneclass LinkedQueue:"""链式队列定义"""def __init__(self):"""链式队列初始化"""# 队首结点指向Noneself.front = Node(None)# 队尾指针指向队首self.rear = self.frontdef isEmpty(self):"""判断是否为空:return: true or false"""return self.front == self.reardef enter(self, data):"""入队:param data: 入队元素值"""# 创建新结点newNode = Node(data)self.rear.next = newNodeself.rear = newNodedef delete(self):"""出队:return: 出队值"""# 队列为空if self.isEmpty():raise IndexError('队列为空')else:node = self.front.next# 队首结点的next指向队首结点的后继结点self.front.next = node.next# 返回出队结点return nodedef peak(self):"""获取队首元素:return: 队首元素"""# 队列为空if self.isEmpty():raise IndexError('队列为空')else:# 返回队首元素return self.front.next.dataif __name__ == '__main__':print('PyCharm')# 12.链式队列linkedQueue = LinkedQueue()# 入队linkedQueue.enter('A')linkedQueue.enter('B')linkedQueue.enter('C')print('输出队首元素：', linkedQueue.peak())# 出队node = linkedQueue.delete()print('出队元素：', node.data)node = linkedQueue.delete()print('出队元素：', node.data)print('输出队首元素：', linkedQueue.peak())