队列的基础知识+Python实现

队列

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行删除。允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。先进先出(FIFO)。

循环队列

为充分利用向量空间,克服”假上溢”现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。即:循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界(QueueSize-1)时,其加1操作的结果是指向向量的下界0。

循环队列

  1. 队空条件:rear=front
  2. 队满条件:(rear+1)%capacity=front。有两种情况:1.front=rear+1(如图);2.front=0rear=capacity-1。使用取余运算可以简单涵盖这两种情况;
  3. 队列长度:(rear-front+capacity)%capacity
  4. 入队:rear=(rear+1)%capacity
  5. 出队:front=(front+1)%capacity

Python实现

使用Python中的list可以简单的实现队列。

普通队列

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
class Queue(object):
"""队列"""
def __init__(self, maxsize=0):
"""maxsize<=0代表队列不限定大小"""
self.queue = []
self.maxsize = maxsize

def is_empty(self):
return len(self.queue) == 0

def is_full(self):
if self.maxsize <= 0:
return False
else:
return len(self.queue) == self.maxsize

def enqueue(self, item):
"""入队"""
if self.is_full():
raise Exception("Queue is full!")
else:
self.queue.append(item)

def dequeue(self):
"""出队"""
if self.is_empty():
raise IndexError("Queue is empty!")
else:
return self.queue.pop(0)

def size(self):
return len(self.queue)

def get_front(self):
"""返回队头元素"""
if self.is_empty():
raise IndexError("Queue is empty!")
else:
return self.queue[0]

def get_rear(self):
"""返回队尾元素"""
if self.is_empty():
raise IndexError("Queue is empty!")
else:
return self.queue[-1]

def print_queue(self):
return self.queue

循环队列

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
52
53
class CircleQueue(object):
"""循环队列"""
def __init__(self, capacity):
"""capacity是队列大小,但实际大小为capacity-1,由于尾指针浪费了一个位置"""
self.capacity = capacity
self.queue = [None] * capacity
self.front, self.rear = 0, 0

def is_empty(self):
return self.front == self.rear

def is_full(self):
# 1.front=rear+1;2.front=0,rear=capacity-1
return (self.rear + 1) % self.capacity == self.front

def enqueue(self, item):
if self.is_full():
raise Exception("Queue is full!")
else:
self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.capacity

def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty!")
else:
tmp = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front + 1) % self.capacity
return tmp

def size(self):
return (self.rear - self.front + self.capacity) % self.capacity

def get_front(self):
if self.is_empty():
raise IndexError("Queue is empty!")
else:
return self.queue[self.front]

def get_rear(self):
if self.is_empty():
raise IndexError("Queue is empty!")
else:
return self.queue[(self.rear - 1 + self.capacity) % self.capacity]

def print_queue(self):
tmp = self.front
ls = []
while tmp != self.rear:
ls.append(self.queue[tmp])
tmp = (tmp + 1) % self.capacity
return ls

测试函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def test_Q():
Q = Queue()
print("队列是否为空:", Q.is_empty())
print("入队'1'")
Q.enqueue(1)
print("队列大小:", Q.size())
print("入队'2'")
Q.enqueue(2)
print("队头元素:", Q.get_front())
print("出队:", Q.dequeue())
print("队头元素:", Q.get_front())
# print("出队:", Q.dequeue())
print("队尾元素:", Q.get_rear())
print("队列为:", Q.print_queue())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def test_CQ():
CQ = CircleQueue(4)
print("循环队列是否为空:", CQ.is_empty())
print("入队'1'")
CQ.enqueue(1)
print("入队'2'")
CQ.enqueue(2)
print("队头元素:", CQ.get_front())
print("入队'3'")
CQ.enqueue(3)
print("循环队列是否为满:", CQ.is_full())
print("出队:", CQ.dequeue())
print("队尾元素:", CQ.get_rear())
print("循环队列为:", CQ.print_queue())

队列的应用—击鼓传花大逃杀

题目描述

你和你的 39 个同学外出露营,晚上无聊时,大家围在火堆边做游戏。游戏规则如下:40人围成一个圈,其中一人被指定为第一个人,顺时针报数到第七人,就将他杀死。之后,下一个活着的人继续报数,每次都是杀死第七个人。直到只剩一人时,游戏结束。如果你并不想死,那么应该坐到哪里才能成为最后一人?(假设第一个报数者的位置记为1)

解题思路

如果能想到将这个问题抽象为一个简单队列的问题,那么就已经解决了一大半。

  • 报数而不被杀的人:相当于从队首出队再从队尾入队;
  • 被杀的人:只出队;
  • 留到最后的人:当队列长度为1时,再出队一次,返回。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def dataosha(name_list, kill_num=7):
"""击鼓传花大逃杀"""
Q = Queue()
for name in name_list:
Q.enqueue(name)
while Q.size() > 1:
for _ in range(kill_num - 1):
Q.enqueue(Q.dequeue())
print("Kill:", Q.dequeue())
return Q.dequeue()


name_list = []
for i in range(40):
name_list.append(i + 1)
print("Safe number:", dataosha(name_list))

结果:

1
Safe number: 24

参考

数据结构:队列
https://blog.csdn.net/Annihilation7/article/details/82847774
https://blog.csdn.net/theLostLamb/article/details/79233615
https://www.jianshu.com/p/ecb1e515a3f4