"""
链式存储-队列
linkqueue.py
代码实现
思路：
1.入队，
2.出队，
3.判断空满
""" # 异常类
class QueueError(Exception):
pass # 节点生成类
class Node:
"""
思路：将自定义的类视为节点的生成类，
实例对象中包含数据的部分和下一个节点的next
"""
def __init__(self,val,next = None):
self.val = val # 有用数据
self.next = next # 循环下一个节点的关系 # 链式存储队列类-队头删除，队尾加入，判断空满等
class LinkQueue01:
"""
头尾选择一端做队头，另一端队尾，队头删除，队尾插入，总有一端需要遍历
改进思路：标记头部和尾部，不需要遍历
"""
def __init__(self):
# 标记头部位置
self._first = Node(None) # 队头删除
def dequeue(self):
p = self._first
if p.next is None:
raise QueueError("queue is empty")
else:
p.next = p.next.next # 队尾插入
def enqueue(self, val):
p = self._first
if p.next is None:
p.next = Node(val)
else:
while p.next is not None:
p = p.next
p.next = Node(val) # 判断队列为空
def is_empty(self):
if self._first.next is None:
return True
else:
return False # 遍历队列
def show(self):
# 队列为空时，报异常
if self._first.next is None:
raise QueueError("queue is empty")
else:
p = self._first.next # 第一个有限节点
while p is not None:
print(p.val)
p = p.next # p 向后移动 # print("-"*30)
# if __name__ == "__main__":
# lq = LinkQueue()
# print(lq.is_empty())
# #lq.delete_node()
# # lq.show()
# lq.enqueue(1)
# lq.show()
# print("***")
# # lq.insert_end(2)
# #print(lq.is_empty())
# lq.enqueue(2)
# lq.enqueue(3)
# lq.show()
# print("***")
# lq.enqueue(4)
# lq.show()
# #print(lq.is_empty())
# #lq.dequeue()
# #lq.show()
#-------------------------------------------------
"""
链式队列的另一种实现
重点代码
思路分析：
1.基于链表构建队列模型
2.链表的开端作为队头，结尾位置作为队尾
3.单独定义队尾进行标记，每次插入数据不需要遍历
4.当队头和队尾重叠时，认为队列为空
""" class LinkQueue:
def __init__(self):
# 定义队头队尾属性变量,牺牲节点，
self.front = self.rear = Node(None) # 判断队列空
def is_empty(self):
return self.front == self.rear # 入队操作,rear动
def enqueue(self,val):
self.rear.next = Node(val)
self.rear = self.rear.next # 出队，front动,指向谁，谁出队
def dequeue(self):
if self.front == self.rear:
raise QueueError("queue is empty")
self.front = self.front.next
return self.front.val # 指向他，但实际出队 if __name__ == "__main__":
print("-"*30)
lq = LinkQueue()
lq.enqueue(1)
lq.enqueue(2)
lq.enqueue(3)
lq.enqueue(4)
print(lq.dequeue()) # 1