队列的 Python 代码实现
队列是一种先进先出的数据类型。
应用场景：我们的计算机实验室有 30 台计算机与一台打印机联网。当学生想要打印时，他们的打印任务与正在等待的所有其他打印任务“一致”。第一个进入的任务是先完成。如果你是最后一个，你必须等待你前面的所有其他任务打印。
接下来，我们将通过 Python 代码创建要给对列：
Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。enqueue(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。size() 返回队列中的项数。它不需要参数，并返回一个整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
if __name__ == '__main__':
q = Queue()
print(q.isEmpty())
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.isEmpty())
print(q.size())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
|
案例：烫手的山芋
烫手山芋游戏介绍：6 个孩子围城一个圈，排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋，需要在计时器计时 1 秒后将山芋传递给下一个孩子，依次类推。规则是，在计时器每计时 7 秒时，手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束，最后剩下的孩子获胜。请使用队列实现该游戏策略，排在第几个位置最终会获胜。
分析：
- 在一轮游戏中山芋会被传递 6 次
- 山芋传递的次数不受孩子个数的影响
- 山芋传递 6 次后一轮游戏结束，淘汰一个孩子游戏继续
- 队列：先进先出，只可以从对头取元素，从队尾添加元素
- 准则：保证队头孩子手里面有山芋（谁手里有山芋谁作为队头）
- 方便删除元素。最终 7 秒到的时候需要将手里有山芋的孩子从队列中剔除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| children = ['A', 'B', 'C', 'D', 'E', 'F']
q = Queue()
for child in children:
q.enqueue(child)
while q.size() > 1:
for i in range(6):
q.enqueue(q.dequeue())
q.dequeue()
print('获胜者：',q.dequeue())
|
双端队列
同普通队列相比，双端队列有两个头部和尾部。可以在双端进行数据的插入和删除，提供了单数据结构中栈和队列的双重特性。
接下来，我们通过 Python 代码创建一个双端队列
Deque() 创建一个空的新 deque。它不需要参数，并返回空的 deque。addFront(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。addRear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。removeFront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。removeRear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。isEmpty() 测试 deque 是否为空。它不需要参数，并返回布尔值。size() 返回 deque 中的项数。它不需要参数，并返回一个整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Deque:
def __init__(self):
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 isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
if __name__ == '__main__':
dq = Deque()
print(dq.isEmpty())
dq.addFront(1)
dq.addRear(2)
dq.addFront(3)
dq.addRear(4)
print(dq.isEmpty())
print(dq.size())
print(dq.removeRear())
print(dq.removeFront())
print(dq.removeFront())
print(dq.removeRear())
|
双端队列应用案例：回文检查
回文是一个字符串，读取首尾相同的字符，例如，radar toot madam。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def check_palindrome(s):
dq = Deque()
for c in s:
dq.addFront(c)
while dq.size() > 1:
if dq.removeFront() != dq.removeRear():
return False
return True
if __name__ == '__main__':
print(check_palindrome('raddar'))
print(check_palindrome('上海自来水来自海上'))
print(check_palindrome('这不是回文'))
print(check_palindrome(''))
print(check_palindrome('a'))
print(check_palindrome('ab'))
|
使用两个栈实现队列
利用两个栈实现先进先出的特性，实现一个队列的功能。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return len(self.items) - 1
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
class Queue:
def __init__(self):
self.s1 = Stack()
self.s2 = Stack()
def enqueue(self, item):
while self.s1.size():
self.s2.push(self.s1.pop())
self.s2.push(item)
while self.s2.size():
self.s1.push(self.s2.pop())
def dequeue(self):
return self.s1.pop()
def isEmpty(self):
return self.s1.isEmpty()
def size(self):
return self.s1.size()
if __name__ == '__main__':
q = Queue()
print(q.isEmpty())
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.isEmpty())
print(q.size())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
|