Python 数据结构入门 - 双端队列（Deque）

什么是双端队列

Deque ： Double End Queue

由数据类型相似的元素组成，允许在队头和队尾插入和删除的有序列表

类比：队列就像排队，双端队列就是可以从队头和队尾排队和退出的队列

双端队列的特点

输入受限的双端队列：允许一端进行插入和删除操作，但是另一端只允许删除的双端队列

输出受限的双端队列：允许一端进行插入和删除操作，但是另一端只允许插入的双端队列

动手试一试

（提示：点击交互式代码框右上角按钮可运行代码）

下面是一个简单的双端实现，先不要关心实现原理，亲自试一试双端队列的各种操作吧

1.创建一个双端队列，并从前后入队元素，尝试在一个位置上插入一个数据

2.删除头尾元素

3.获得头尾元素

Python 中已实现的 Deque 的使用方法

参考阅读： http://www.php.cn/python-tutorials-358240.html

双端队列经典案例

1.判断回文

回文是指形如 aaabaaa 的字符串

请创建一个函数判断字符串是否是回文。

2.滑动窗口

类比：对一个存放数字的数组，现有一个窗口长度为L，将窗口与数组的左侧对齐，将窗口中最大数（或最小数）记录下来，将窗口向右侧推动一个单位，记录窗口中最大数（或最小数），以此类推，产生一个列表。

举个栗子:      窗口长度：3   数组：[4,2,5,3,6,1]  求滑动最大值列表

                      4 2 5 3 6 1  -> 最大值列表[5]         

                      4 2 5 3 6 1 -> 最大值列表[5,5]

                      4 2 5 3 6 1 -> 最大值列表[5,5,6]         

                      4 2 5 3 6 1 -> 最大值列表[5,5,6,6]

普通方法：对每个窗口遍历一次，并选出最大的值。时间复杂度O(N*L)     N：数组长度   L：窗口长度

双端队列最优解时间复杂度：O(N)

实现方法：