Python实现双端队列数据结构及其基本方法

队列是一种特殊的线性表，是一种先进先出（FIFO）的数据结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头，队列中没有元素时，称为空队列。

队列可由线性表来实现，包括列表和链表都可实现队列，不过在安全性上来说链表比较安全，但是增加额外的内存开销，一般考虑列表来实现队列。

查看Python队列库queue提供的队列源码如下：

Queue提供了一些基本方法：task_done、join、qsize、empty、full、put、get、put_nowait、get_nowait，但是他的实现依旧是通过操作内部的私有方法，而这些私有方法是队列的本质。

包括最后的初始化创建一个列表、获取列表长度返回队列大小、以及对列表进行元素操作等，这一切本质上都是对liest操作。

什么是双端队列？双端队列是在普通队列的基础上，既可以在前端弹出元素也可以在前端插入元素，既可以在后端插入元素也可以在后端弹出元素，下面来实现这一基本模型。

双端队列分类：

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列，而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈了。