一、队列的定义
队列（Queue）：简称为队，一种线性表数据结构，是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。
我们把队列中允许插入的一端称为 「队尾（rear）」；把允许删除的另一端称为 「队头（front）」。当表中没有任何数据元素时，称之为 「空队」。
二、队列的实现
2.1 队列的顺序存储
class Queue:
# 初始化空队列
def __init__(self, size = 100):
self.size = size
self.queue = [None for _ in range(size)]
self.front = -1 # 队列的头指针
self.rear = -1 # 队列的尾指针
# 判断队列是否为空
def is_empty(self):
return self.front == self.rear
# 判断队列是否满了
def is_full(self):
return self.rear + 1 == self.size
# 元素入队
def enqueue(self, value):
if self.is_full():
raise Exception('Queue is full')
else:
self.rear += 1
self.queue[self.rear] = value
# 元素出队
def dequeue(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
self.front += 1
return self.queue[self.front]
# 获取队头元素
def front_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
return self.queue[self.front + 1]
# 获取队尾元素
def rear_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
return self.queue[self.rear]
2.2 循环队列的顺序存储实现
class Queue:
# 初始化空队列
def __init__(self, size = 100):
self.size = size + 1
self.queue = [None for _ in range(size + 1)]
self.front = 0
self.rear = 0
# 判断队列是否为空
def is_empty(self):
return self.front == self.rear # 判断头尾节点是否重合
# 判断队列是否已满
def is_full(self):
return (self.rear + 1) % self.size == self.front
# 入队操作
def enqueue(self, value):
if self.is_full():
raise Exception('Queue is full')
else:
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = value
# 出队操作
def dequeue(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
self.queue[self.front] = None
self.front = (self.front + 1) % self.size
return self.queue[self.front]
# 获取队头元素
def front_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
value = self.queue[(self.front + 1) % self.size]
return value
# 获取队尾元素
def rear_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
value = self.queue[self.rear]
return value
2.3 队列的链式存储实现代码
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Queue:
# 初始化空队列
def __init__(self):
head = Node(0)
self.front = head
self.rear = head
# 判断队列是否为空
def is_empty(self):
return self.front == self.rear
# 入队操作
def enqueue(self, value):
node = Node(value)
self.rear.next = node
self.rear = node
# 出队操作
def dequeue(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
node = self.front.next
self.front.next = node.next
# 当尾节点是第一个节点
if self.rear == node:
self.rear = self.front
value = node.value
return value
# 获取队头元素
def front_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
return self.front.next.value
# 获取队尾元素
def rear_value(self):
if self.is_empty():
raise Exception('Queue is empty')
else:
return self.rear.value
三、队列的应用
- 解决计算机的主机与外部设备之间速度不匹配的问题。
比如解决主机与打印机之间速度不匹配问题。主机输出数据给计算机打印，输出数据的速度比打印数据的速度要快很多，如果直接把数据送给打印机进行打印，由于速度不匹配，显然行不通。为此，可以设置一个打印数据缓存队列，将要打印的数据依次写入缓存队列中。然后打印机从缓冲区中按照先进先出的原则依次取出数据并且打印。这样即保证了打印数据的正确，又提高了主机的效率。 - 解决由于多用户引起的系统资源竞争的问题。
比如说一个带有多终端的计算机系统，当有多个用户需要各自运行各自的程序时，就分别通过终端向操作系统提出占用 CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序将它们排成一个队列，每次把 CPU 分配给队头请求的用户使用；当相应的程序运行结束或用完规定的时间间隔之后，将其退出队列，再把 CPU 分配给新的队头请求的用户使用。这样既能满足多用户的请求，又能使 CPU 正常运行。
再比如 Linux 中的环形缓存、高性能队列 Disruptor，都用到了循环并发队列。iOS 多线程中的 GCD、NSOperationQueue 都用到了队列结构。
四、广度优先搜索
广度优先搜索算法（Breadth First Search）：简称为 BFS，又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始，沿着树的宽度遍历树或图的节点。如果所有节点均被访问，则算法中止。
广度优先遍历类似于树的层次遍历过程。呈现出一层一层向外扩张的特点。先看到的节点先访问，后看到的节点后访问。遍历到的节点顺序符合「先进先出」的特点，所以广度优先搜索可以通过「队列」来实现。
- 基于队列实现的广度优先搜索
import collections
def bfs(graph, start):
visited = set(start) # 已经的访问的节点
q = collections.deque([start]) # 队列
# 队列不为空
while q:
node_u = q.popleft()
print(node_u)
for node_v in graph[node_u]:
if node_v not in visited:
visited.add(node_v)
q.append(node_v)
695. 岛屿的最大面积
# 队列+广度优先搜索
import collections
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
# 上 下 左 右 四个方向
directs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
# 行数、列数
row, col = len(grid), len(grid[0])
# 最大岛屿面积
ans = 0
# 遍历进行查找
for i in range(row):
for j in range(col):
# 当该点是岛屿，则对周围进行遍历
if grid[i][j] == 1:
# 为了避免重复计数，及时更新为0
grid[i][j] = 0
# 并进行计数
tmp_ans = 1
# 对该点的坐标使用队列存储
q = collections.deque([(i, j)])
# 对该点进行广度优先搜索
while q:
i, j = q.popleft()
for direct in directs:
new_i = i + direct[0]
new_j = j + direct[1]
if new_i < 0 or new_i >= row or new_j < 0 or new_j >= col or grid[new_i][new_j] == 0:
continue
grid[new_i][new_j] = 0
tmp_ans += 1
q.append((new_i, new_j))
ans = max(tmp_ans, ans)
return ans
752. 打开转盘锁
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，因为当拨动到 "0102" 时这个锁就会被锁定。
import collections
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
queue = collections.deque(['0000'])
visited = set(['0000'])
deadset = set(deadends)
level = 0 # 最小旋转次数
# 结束的条件
while queue:
size = len(queue)
for _ in range(size):
cur = queue.popleft()
# 判断是否会死锁
if cur in deadset:
continue
# 如果满足目标密码，及时输出
if cur == target:
return level
# 枚举法得到每一种变化的可能
for i in range(len(cur)):
up = self.upward_just(cur, i)
if up not in visited:
queue.append(up)
visited.add(up)
down = self.downward_just(cur, i)
if down not in visited:
queue.append(down)
visited.add(down)
level += 1
return -1
# 向上调整数字
def upward_just(self, cur, i):
cur_list = list(cur)
if cur_list[i] == '9':
cur_list[i] = '0'
else:
cur_list[i] = chr(ord(cur_list[i]) + 1)
return ''.join(cur_list)
# 向下调整数字
def downward_just(self, cur, i):
cur_list = list(cur)
if cur_list[i] == '0':
cur_list[i] = '9'
else:
cur_list[i] = chr(ord(cur_list[i]) - 1)
return ''.join(cur_list)
队列-先进先出
from collections import deque
class Test:
def test(self):
# cerate a queue
queue = deque()
# add element
# time complexity: O(1)
queue.append(1)
queue.append(2)
queue.append(3)
print(queue) # [1,2,3]
# get the head of the queue
# time complexity: O(1)
temp1 = queue[0]
print(temp1) # 1
# remove the head of the queue
# time complexity: O(1)
temp2 = queue.popleft()
print(temp2) # 1
print(queue) # [2, 3]
# queue is empty?
# time complexity: O(1)
len(queue) == 0
# the length of queue
# time complexity: O(1)
len(queue)
# interate array
# time complexity:O(n)
while len(queue) > 0:
temp = queue.popleft()
print(temp)
if __name__ == '__main__':
test = Test()
test.test()
力扣933
队列的ADT实现
class Queue():
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
1)热土豆问题（约瑟夫问题）
游戏时，队首始终是持有土豆的人
模拟游戏开始，队首的人出队，之后再到队尾（类似于循环队列）
传递了num次之后，将队首的人移除
如此反复，直到队列中剩余一人
def hotPotato(nameList, num):
simqueue = Queue()
for name in nameList:
simqueue.enqueue(name)
while simqueue.size() > 1:
for i in range(num):
simqueue.enqueue(simqueue.dequeue()) # 完成一次传递
simqueue.dequeue()
return simqueue.dequeue()
print(hotPotato(['a', 'b', 'c'], 2))
2） 模拟算法：打印任务
多人共用一台打印机，采取“先到先服务”的队列策略来执行打印任务
需要解决的问题：1 打印系统的容量是多少？2 在能够接受的等待时间内，系统可容纳多少用户以多高的频率提交打印任务？
import random
class Printer:
def __init__(self, ppm):
self.pagerate = ppm # 打印速度
self.currentTask = None # 打印任务
self.timeRemaining = 0 # 任务倒计时
def tick(self): # 打印 1s
if self.currentTask != None: # 有打印任务
self.timeRemaining = self.timeRemianing - 1
if self.timeRemianing <= 0:
self.currentTask = None
def busy(self): # 打印忙？
if self.currentTask != None:
return True
else:
return False
def startNext(self, newtask):
self.currentTask = newtask
self.timeRemaining = newtask.getPages()*60/self.pagerate
class Task:
def __init__(self, time):
self.timestamp = time # 生成时间戳
self.pages = random.randrange(1, 21) # 打印页数
def getStamp(self):
return self.pages
def getPages(self):
return self.pages
def waitTime(self, currenttime):
return currenttime - self.timestamp # 等待时间
def newPrintTask():
num = random.randrange(1, 181) # 1/180概率生成作业
if num == 180:
return True
else:
return False
def simulation(numSeconds, pagesPerMinute): # 模拟
labprinter = Printer(pagesPerMinute)
printQueue = Queue()
waitingtimes = []
for currentSecond in range(numSeconds):
if newPrintTask():
task = Task(currentSecond)
printQueue.enqueue(task)
if (not labprinter.busy()) and (not printQueue.isEmpty()):
nexttask = printQueue.dequeue()
waitingtimes.append(nexttask.waitTime(currentSecond))
labprinter.startNext(nexttask)
labprinter.tick()
averageWait = sum(waitingtimes)/len(waitingtimes)
print("Average Wait %6.2f secs %3d tasks ramaining."%(averageWait, printQueue.size()))
双端队列-Deque
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0, item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
练习-回文词判定
输入：abba
输出：False
思路：1 先将需要判定的词从队尾加入 deque; 2从两端同时移除字符并判断是否相同，直到deque中剩余0个（偶数）或1个字符（奇数）
def palchecker(aString):
chardeque = Deque()
for ch in aString:
chardeque.addRear(ch)
stillEqual = True
while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False
return stillEqual
print(palchecker('aabbaa'))
print(palchecker('abccd'))
网友评论