Python数据结构与算法

Python数据结构与算法—队列

队列

1.定义：队列是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为“队尾”，允许进行删除操作的一端称为“队头”。

2.特点：

队列只能在队头和队尾进行数据操作
栈模型具有先进先出或者叫做后进后出的规律

3.队列的代码实现

队列的操作有入队，出队，判断队列的空满等操作。

 1 """
 2 squeue.py  队列的顺序存储
 3 重点代码
 4 
 5 思路分析：
 6 1. 基于列表完成存储结构
 7 2. 通过封装规定队头和队尾操作
 8 """
 9 
10 # 　自定义队列异常
11 class QueueError(Exception):
12   pass
13 
14 
15 # 队列操作类
16 class SQueue:
17   def __init__(self):
18     self._elems = []
19 
20   # 判断队列空
21   def is_empty(self):
22     return self._elems == []
23 
24   # 入队 从列表尾部
25   def enqueue(self, elem):
26     self._elems.append(elem)
27 
28   # 出队　从列表开头
29   def dequeue(self):
30     if not self._elems:
31       raise QueueError("Queue is empty")
32     return self._elems.pop(0)
33 
34 
35 if __name__ == "__main__":
36   sq = SQueue()
37   sq.enqueue(10)
38   sq.enqueue(20)
39   sq.enqueue(30)
40   while not sq.is_empty():
41     print(sq.dequeue())

队列的顺序存储代码

 1 """
 2 lqueue.py 链式队列
 3 重点代码
 4 
 5 思路分析：
 6 1. 基于链表模型完成链式栈
 7 2. 链表开端作为队头，尾端作为队尾
 8 3. 头尾指向同一个节点时作为空队列
 9 """
10 
11 # 　自定义队列异常
12 class QueueError(Exception):
13   pass
14 
15 #节点类
16 class Node:
17   def __init__(self, data, next=None):
18     self.data = data
19     self.next = next
20 
21 # 链式队列类
22 class LQueue:
23   def __init__(self):
24     # 初始头尾指向一个没有实际意义的节点
25     self.front = self.rear = Node(None)
26 
27   def is_empty(self):
28     return self.front == self.rear
29 
30   #　入队　尾动
31   def enqueue(self,elem):
32     self.rear.next = Node(elem)
33     self.rear = self.rear.next
34 
35   #　出对　头动
36   def dequeue(self):
37     if self.front == self.rear:
38       raise QueueError("Queue is empty")
39     self.front = self.front.next
40     return self.front.data
41 
42 if __name__ == "__main__":
43   lq = LQueue()
44   lq.enqueue(10)
45   lq.enqueue(20)
46   lq.enqueue(30)
47   print(lq.dequeue())

队列的链式存储代码