文章目录
前言
双端队列有两个端部，首部和尾部，并且项在集合中保持不变。
双端队不同的地方是添加和删除项是非限制性的。可以在前面或后面添加新项；同样，可以从任一端移除现有项。
一、双端队列模型
双头队列是队列数据结构的一种更通用的形式，它允许从两端(即正面和背面)插入和删除元素。
二、双端队列的实现
在这里，我们将使用循环数组实现双端队列。 它将具有以下方法：
push_back：在后面插入元素
push_front：在前面插入元素
pop_back：删除最后一个元素
pop_front：删除第一个元素
get_back：返回最后一个元素
get_front：返回第一个元素
empty :如果队列为空，则返回true
full :如果队列已满，则返回true
在这里我们能看出双端队列是有头有尾，虽然我们在队列的两端都可以进行增加删减的操作，但是在编码的过程中头和尾的逻辑一定要搞清楚。
public class Dequeue
{
public int arr[];
public int front, rear;
public void Dequeue()
{
arr = new int[];
front = -1;
rear = -1;
}
}
三、在前面插入元素
首先，我们检查队列是否已满。 如果未满，我们按照给定条件在前端插入一个元素。
如果队列为空，则将前和后初始化为0。两者都将指向第一个元素。
否则，我们递减front并插入元素。 由于我们使用的是圆形数组，因此必须记住，如果front等于0，那么与其将其减1而不是使其等于SIZE-1。
public void push_front(int key)
{
if(full())
{
System.out.println("队列已满");
}
else
{
if(front == -1)
front = rear = 0;
else if(front == 0)
front = SIZE-1;
else
--front;
arr[front] = key;
}
}
四、在后面插入元素
再次，我们检查队列是否已满。 如果未满，我们按照给定条件在后面插入一个元素：
如果队列为空，则将前和后初始化为0。两者都将指向第一个元素。
否则，我们增加后方并插入元素。 由于我们使用的是圆形数组，因此必须记住，如果后方等于SIZE-1，那么与其将其增加1而不是使其等于0
public void push_back(int key)
{
if(full())
{
System.out.println("队列已满");
}
else
{
if(front == -1)
front = rear = 0;
else if(rear == SIZE-1)
rear = 0;
else
++rear;
arr[rear] = key;
}
}
删除元素与添加元素的逻辑基本相同，这里就不过多解释。
五、检查队列是否为空
只需查看前端指向的位置即可对其进行检查。 如果front仍使用-1初始化，则队列为空。
public boolean empty()
{
if(front == -1)
return true;
else
return false;
}
六、检查队列是否已满
由于我们使用的是循环数组，因此我们检查代码中所示的以下条件，以检查队列是否已满。
public boolean full()
{
if((front == 0 && rear == SIZE-1) ||
(front == rear + 1))
return true;
else
return false;
}
总结
双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。
是属于简单的数据结构，熟悉掌握对之后的数据结构会有很大的帮助。