队列的基础知识+Python实现

本文首发于我的个人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/02/queue.html　　作者: Suixin

队列

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

循环队列

为充分利用向量空间，克服"假上溢"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。即：循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。
<center><img src='https://ws2.sinaimg.cn/large/006tKfTcly1g0hkwsivzsj30wl0kkq4h.jpg' width='50%' alt='循环队列'></center>

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

Python实现

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

普通队列

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

循环队列

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

测试函数

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())

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时，再出队一次，返回。

代码

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))

结果：

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