数据结构（python）-------栈和队列2
目录
二、队列
（一）、定义
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
（二）、队列与一般线性表的区别
一般线性表
队列
（三）、分类
1、顺序队列：队列的顺序表示（用一维数组）
1.1队列的顺序表示－－用一维数组base[M]
存在问题
2、循环队列
2.1 循环队列初始化
2.2判断对空
2.3、循环队列入队----环状位移要取余
2.4、获取队首元素
3.链式队列：用单链表表示
3.1判断队空
3.2、链式入队
3.3、链式队列出队
3.4、获取队首元素
二、队列
（一）、定义
1. 定义
只能在表的一端（队尾）进行插入，在另一端（队首或队头）进行删除运算的线性表
2. 逻辑结构
与线性表相同，仍为一对一关系
3. 存储结构
用顺序队列或链式队列存储均可
4. 运算规则
先进先出（FIFO）
5. 实现方式
关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同
（二）、队列与一般线性表的区别
队列是一种特殊（操作受限）的线性表
区别：仅在于运算规则不同
一般线性表
逻辑结构：一对一
存储结构：顺序表、链表
运算规则：随机、顺序存取
队列
逻辑结构：一对一
存储结构：顺序队列、链式队列
运算规则：先进先出
（三）、分类
1、顺序队列：队列的顺序表示（用一维数组）
利用一组连续的存储单元(一维数组) 依次存放从队首到队尾的各个元素，称为顺序队列。
顺序队列定义如下：
class SeqQueue:
def __init__(self, max):
self.max = max # 队列最大容量
# 存储队列元素的数组
self.data = [None for i in range(self.max)]
self.front = 0 # 队首指针
self.rear = 0 # 队尾指针1.1队列的顺序表示－－用一维数组base[M]
入队和出队
存在问题
真假溢出
解决办法-----循环队列
2、循环队列
2.1 循环队列初始化
class CircleQueue(object):
def __init__(self,max):
# 队列最大容量
self.max = max
# 存储队列元素的数组
self.data = [None for i in range(self.max)]
# 队首指针
self.front = 0
# 队尾指针
self.rear = 0
2.2判断对空
class CircleQueue(object):
def __init__(self,max):
# 队列最大容量
self.max = max
# 存储队列元素的数组
self.data = [None for i in range(self.max)]
# 队首指针
self.front = 0
# 队尾指针
self.rear = 0
2.3、循环队列入队----环状位移要取余
def push(self,val):
'''
:Desc 入队 :param val:待入队关键字
'''
# 如果队列满了，抛出异常
if (self.rear + 1) % self.max == self.front:
raise IndexError("队列为满")
# 在队尾插入新的关键字
self.data[self.rear] = val
# 修改队尾指针
self.rear = (self.rear + 1) % self.max2.4循环队列出队
def pop(self):
'''
:Desc 将队首元素出队
'''
# 如果队列为空，抛出异常
if self.empty():
raise IndexError("队列为空")
# 队列不为空，获取队首元素
cur = self.data[self.front]
# 修改队首指针，指向下一个位置
self.front = (self.front + 1) % self.max
# 返回原队首元素
return cur2.4、获取队首元素
def pop(self):
'''
:Desc 将队首元素出队
'''
# 如果队列为空，抛出异常
if self.empty():
raise IndexError("队列为空")
# 队列不为空，获取队首元素
cur = self.data[self.front]
# 修改队首指针，指向下一个位置
self.front = (self.front + 1) % self.max
# 返回原队首元素
return cur3.链式队列：用单链表表示
设立一个队首指针front ，指向队首元素。
初始化：front=None。
入队：判断队列是否为空。如果队列为空，将队首指针指向待插入的新节点。若队列不为空，则遍历到队尾元素，将新节点插入到队尾。
出队：首先判断队列是否为空，若是队列为空，则抛出异常；否则，删除队首节点。
队列为空：front is None。
class Node(object):
def __init__(self,data):
'''
:Desc
队列节点存储结构
'''
# 数据域
self.data = data
# 指针域
self.next = None
class LinkedQueue(object):
def __init__(self):
'''
:Desc 队列初始化
'''
# 队首指针指向空
self.front = None3.1判断队空
class LinkedQueue(object):
def __init__(self):
'''
:Desc 队列初始化
'''
# 队首指针指向空
self.front = None3.2、链式入队
入队：判断队列是否为空。如果队列为空，将队首指针指向待插入的新节点。若队列不为空，则遍历到队尾元素，将新节点插入到队尾。
def push(self,val):
'''
:Desc 将关键字入队 :param val: 关键字
'''
# 新节点
new = Node(val)
# 如果队列为空
if self.front == None:
# 将队首指针指向新节点
self.front = new
# 如果队列不为空
else:
# 声明cur指针
cur = self.front
# 通过cur指针遍历队列
while cur.next != None:
cur = cur.next
# 在队尾插入元素
cur.next = new
3.3、链式队列出队
出队：首先判断队列是否为空，若是队列为空，则抛出异常；否则，删除队首节点
def pop(self):
'''
:Desc 将队首元素出队
'''
# 如果队列为空，抛出异常
if self.empty():
raise IndexError("队列为空")
# 如果队列不为空
else:
cur = self.front
# 将队首指针指向队首节点的后继节点
self.front = self.front.next
# 返回原本队首节点
return cur
3.4、获取队首元素
peek(self):
'''
:Desc 获取队首元素 :return: 返回队首元素
'''
# 如果队列为空，抛出异常
if self.empty():
raise IndexError("队列为空")
# 如果队列不为空
else:
# 返回队首元素
return self.front