上文 数据结构系列：栈？队列？这俩货应该这么理解和掌握 我们分享了栈和队列最最基础的特点和应用，本篇将拓展一下关于普通队列结构的不同变体，如何实现(基于python)，以及相关的应用。始终记住：数据结构只是一种抽象的概念，是具有某种特点的数据集合，并不是指某一个单独的数据类型。

# 利用单链表实现队列结构
class Node:
    """节点类"""
    def __init__(self, data):
        self.data = data
        self.next = None

# 具体实现
class Queue():
    def __init__(self):
        self._front = None
        self._rear = None
    	self.size = 0
        
    def push(self, new_node):
        new = Node(new_node)
        if self.is_empty():
            self._front = new
        else:
            self._rear.next = new
        self._rear = new
        self._size += 1
        
    def pop(self):
        if self.is_empty():
            raise QueueError('队列为空')
        rm_data = self._front.data
        self._front =self._front.next
        if self._front is None:
            self._rear = None
        self.size -= 1
        return rm_data
    
    def is_empty(self):
        return self._front is None

普通队列

普通队列的特点就是"FIFO"，上文我们已经分享了基于python的内置列表结构实现一个简单的队列结构，所以这里我们将会分享基于链表结构的实现

代码块1

普通队列已经能实现大部分的功能了，但是不够用。

举个例子来说，医院看病排号，正常来讲，就先挂号的先看病，这是没有毛病的，但是突然间来了个需要急救的，你还能让他挂个号，再等着排到号看病吗？肯定他是要先被救治的，毕竟在生死之间，时间就是生命！

所以这时候普通的队列就不够用了，需要给队列搞点变体，比如说在正常队列特点(FIFO)上增加优先级的特点，可以让具有优先级较高的数据体插队到队首，所以优先队列就诞生了。

优先队列

1. 概念理解

优先队列和普通队列结构一样，数据从逻辑队尾进入队列，数据从逻辑队首移除。不同的是，从队首移除数据总会移除优先级最高的数据，而从队尾加入数据，也是根据某种顺序添加到队列中

2. 原理

• 优先队列的数据结构是基于完全二叉树(有关树的结构，后面的文章会写)的特点：从任一叶子节点开始到根节点的一条路径是有序列表，如果是最大堆，则由叶子结点到根节点的路径上的所有节点数据呈现从小到大的变化，而最小堆则刚好相反。完全二叉堆（树）又是二叉树类型中的一种，所以要理解原理，需要理解树结构相关的知识
• 上面所说的树结构为二叉堆（不论是最小堆还是最大堆结构），一般都会提供如下几个接口，用来构建优先队列，二叉堆的数据插入，二叉堆的数据删除，二叉堆的根节点元素的值，以及将杂乱的序列（列表等数据结构）转化为堆结构。优先队列也是通过二叉堆内部的这几个接口达成目的

3. 实现(基于python内置库heapq)

# 参考：Python Cookbook (3rd), O'Reilly.
# 这里使用python内置的堆模块，当然也可以自己写，在树结构一文中有构造过
import heapq

class PriorityQueue(object):
    def __init__(self):
        self._queue = []        #创建一个空列表用于存放队列
        self._index = 0        #保证同等优先级元素插入时的正确排序
    
    def push(self, item, priority):
        """队列每个数据项都由（priority, index, item)元组构成"""
        heapq.heappush(self._queue, (-priority, self._index, item)) 
        self._index += 1
        
    def pop(self):
        #  heappop() 函数总是返回”最小的”的元素
        return heapq.heappop(self._queue)[-1]    #返回拥有最高优先级的项

class Item(object):
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return 'Item: {!r}'.format(self.name)

if __name__ == '__main__':
    >>> q = PriorityQueue()
    >>> q.push(Item('foo'), 1)
    >>> q.push(Item('bar'), 5)
    >>> q.push(Item('spam'), 4)
    >>> q.push(Item('grok'), 1)
    >>> q.pop()
    Item('bar')
    >>> q.pop()
    Item('spam')
    >>> q.pop()
    Item('foo')
    >>> q.pop()
    Item('grok')
    >>>

heapq本就是一个二差堆的结构，优先队列一般都是基于二差堆实现。

原则上讲，一般队列都是基于数组实现，因为简单，且接口性能更好，但是有一个问题：因为顺序存储（底层为数组）的结构特点，数据只能在队首位置出队，那么出队操作需要先将删除的数据从数组中删除，然后将剩下的所有元素前移一位，故而时间复杂度为O(n)，消耗了比较大的性能，所以就将队列做了一次变体，称之为循环队列

循环队列

1. 概念

循环队列是头尾相连的顺序存储结构，循环队列是队列的一种实现方式，并不是一种全新的数据结构

2. 为什么要创造循环队列

为了降低时间复杂度，将入队和出队的操作都可以通过索引以常数时间定位，然后进行入队或出队的操作，而数组的特性决定了这两个操作的时间复杂度都是O(1)

3. 实现循环队列的整体思路

维护两个指针(最开始都指向下标为0的位置)，分别代表着队首位置以及队尾的下一个元素位置，入队，则移动队尾指针，队首指针不动；出队，则移动队首指针，队尾指针不动

4. 循环队列特点及实现的详细思路(感觉解释异常清晰了)

• 循环队列的出队，入队操作的时间复杂度都是O(1)
• 这里约定，指向队首的指针变量命名为front,指向队尾的下一个元素位置的变量指针命名为rear
• front和rear理解为队列的索引，空队列（最开始的时候）,此时front=rear=0;由于front 和rear会随着出队、入队的操作执行索引+1的操作，这里假设不出队，一直入队，直到队满的时候，此时rear已经超过了队列的最大索引值，那么假设rear可以从队首索引重新开始计算，那么此时rear指向队首位置，那么此时front=rear,那么就造成一种尴尬的局面，队空，队满都是一个判断条件（front=rear），为了对这种情况的处理，提出了新的解决方案：将队列长度增加一，占据一个内存单元，但是不存储数据，只是为了通过这个方法判断队列为满还是空的情况
• 举例来说：比如说队列长度为5，开始front=0,rear=0,那么添加5个数据入队，此时rear=5, 但是此时满队列的索引最大才能是4,所以假设rear可以从尾部移动到队首，那么此时rear指向0，那么front=rear=0，此时队列为满.但同时思考一下前面说到的，队为空也是front=rear=0,所以通过front=rear的条件无法分清楚目前是满队列还是空队列，由此提出了以下新的解决方案：将队列长度增加一，占据一个内存单元，但是不存储数据
• 新定义的判断队满的计算方法就是 ，如果 (rear + 1) % queue_max_size == front,此时队满
• 举例来说：假设队列最大长度为5，比如入队4个数据，那么此时队列就是满队列，rear=4（意思是指向索引位置为4的内存空间，也就是队列的最后一个不存储数据的空间位置），此时(4 + 1) % 5 = 0 =front，就可以说是队满（增加的一个额外空间用来判断队满的条件）

• 通过增加一个额外空间的方式判断队满的情况，对于当前队列的长度有两种情况
• Rear > front: current_queue_size = rear - front
• Rear > front: current_queue_size = rear + max_queue_size - front
• 由于rear可能大于front，也可能小于front，以下为两种情况分析
• 综上所述：current_queue_size = （rear - front + max_queue_size）% max_queue_size

5. 实现代码

# 循环队列
class LoopQueue:

    def __init__(self, max_size):
        self._queue = [None] * max_size
        self._front = 0
        self._rear = 0
        self._max_size = max_size

    # 让队列支持遍历，支持for语句
    def __iter__(self):
        cursor = self._front
        while cursor != self._rear:
            yield self._queue[cursor]
            cursor = (cursor + 1) % self._max_size

    def is_empty(self):
        return self._front == self._rear

    def enqueue(self, data):
        if (self._rear + 1) % self._max_size == self._front:
            print("the queue is full")
        self._queue[self._rear] = data
        self._rear = (self._rear + 1) % self._max_size

    def dequeue(self):
        if self._front == self._rear:
            return "the current size of the queue is 0"
        rm_data = self._queue[self._front]
        self._queue[self._front] = None
        self._front = (self._front + 1) % self._max_size
        return rm_data

    def size(self):
        """返回当前队列的长度"""
        return (self._rear + self._max_size - self._front) % self._max_size
    
    # 取队首数据
    def get_front(self):
        if self._front == self._rear:
            return None
        return self._queue[self._front]

好好的看下我上面的详细思路，其实代码也比较好理解，本篇<完>。

我是一名奋战在编程界的pythoner，工作中既要和数据打交道，也要和erp系统，web网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧，在实际应用中遇到的问题以及解决方案，或者源码的阅读等等，欢迎大家一起来讨论！如果觉得写得还不错，欢迎关注点赞，谢谢