3.4.5* 双端队列

双端队列是一种特殊的队列，它是在线性表的两端对插入和删除操作限制的线性表。双端队列可以在队列的任何一端进行插入和删除操作，而一般的队列则要求在一端插入元素，在另一端删除元素。如图3.30所示。

图3.30 双端队列

其中，end 1和end 2分别是双端队列的指针。

在实际应用中，还有输入受限和输出受限的双端队列。输入受限的双端队列指的是只允许在队列的一端进行插入元素，两端都可以删除元素的队列。输出受限的双端队列指的是只允许在队列的一端进行删除元素，两端都可以插入元素的队列。

双端队列是一个可以在任何一端进行插入和删除操作的线性表，现采用一个一维数组作为双端队列的数据存储结构，双端队列为空的状态如图3.31所示，在队列左端元素a，b，c依次入队，在队列右端元素d，e依次入队之后，双端队列的状态如图3.32所示。

图3.31 双端队列初始状态

图3.32 双端队列插入元素之后