Python数据结构：队列及其应用

1.什么是队列？

队列是一种遵循先进先出的原则（First In First Out）d的数据结构。
Python标准库里就有Queue类，标准库导入方法import queue 。

标准库中的queue

标准库中的queue是线程安全的，并且使用了协程。

基于线程锁的asyncio Queue；
优先队列PriorityQueue；
后进先出LifoQueue类似于栈。

队列手绘

2.队列拥有的操作

enqueue：入队（将元素插入队尾）

dequeue：出队（将元素从队头删除）

first：返回最先入队的元素（队列最前面的元素）

3.单链表实现队列

队列如果像栈那样用list类来实现的话会浪费很多的空间，如果重新排布位置就会消耗很多的时间划不来，就不具体实现了。
用单链表实现队列的时候必须使用带尾指针的单链表，不然出栈操作需要遍历整个链表，时间复杂度会达到O（n），用了带尾指针的单链表后，直接用尾指针操作，时间复杂度O（1）。

class Queue:
    """First In First Out"""
    class _Node:
        __slots__='_element','_next'
        def __init__(self,element,next):
            self._element=element
            self._next=next

    def __init__(self):
        self._head=None #=_Node(None,None)
        self._tail=None
        self._size=0

    def __len__(self):
        return self._size

    def isEmpty(self):
        return self._size==0

    def first(self):
        if self.isEmpty():
            raise Exception('Queue is empty')
        return self._head._element

    def dequeue(self):
        if self.isEmpty():
            raise Exception('Queue is empty')
        deleted_elem=self._head._element
        self._head=self._head._next
        self._size-=1
        if self.isEmpty():
            self._tail=None
        return deleted_elem

    def enqueue(self,element):
        new_element=self._Node(element,None)
        if self.isEmpty():
            self._head=new_element #_head._element=new_element
        else:
            self._tail._next=new_element
        self._tail=new_element
        self._size+=1

时间复杂度

时间复杂度分析

操作	时间复杂度
dequeue	O（1）
enqueue	O（1）
first	O（1）
isEmpty	O（1）
len	O（1）

在python里如果使用list数组实现队列，弹出一个元素pop所用时间复杂度是非常高的，所以就不举list实现的例子了。
当然，也可以使用numpy里的array或者collections里的array速度效率都是很可观的，读者可以自己去尝试一下。

队列的应用

队列应用很多，也很常见，比如web服务器资源请求，打印机打印请求，CPU调度等等。