//Deque.java
package dsa//根据自己的程序位置不同
public interface Deque {
public int getSize()//返回队列中元素数目
public boolean isEmpty()//判断队列是否为空
public Object first() throws ExceptionQueueEmpty//取首元素（但不删除）
public Object last() throws ExceptionQueueEmpty//取末元素（但不删除）
public void insertFirst(Object obj)//将新元素作为首元素插入
public void insertLast(Object obj)//将新元素作为末元素插入
public Object removeFirst() throws ExceptionQueueEmpty//删除首元素
public Object removeLast() throws ExceptionQueueEmpty//删除末元素
public void Traversal()//遍历
}
双向链表实现：
//Deque_DLNode.java
/*
* 基于双向链表实现双端队列结构
*/
package dsa
public class Deque_DLNode implements Deque {
protected DLNode header//指向头节点（哨兵）
protected DLNode trailer//指向尾节点（哨兵）
protected int size//队列中元素的数目
//构造函数
public Deque_DLNode() {
header = new DLNode()
trailer = new DLNode()
header.setNext(trailer)
trailer.setPrev(header)
size = 0
}
//返回队列中元素数目
public int getSize()
{ return size}
//判断队列是否为空
public boolean isEmpty()
{ return (0 == size) ? true : false}
//取首元素（但不删除）
public Object first() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空")
return header.getNext().getElem()
}
//取末元素（但不删除）
public Object last() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空")
return trailer.getPrev().getElem()
}
//在队列前端插入新节点
public void insertFirst(Object obj) {
DLNode second = header.getNext()
DLNode first = new DLNode(obj, header, second)
second.setPrev(first)
header.setNext(first)
size++
}
//在队列后端插入新节点
public void insertLast(Object obj) {
DLNode second = trailer.getPrev()
DLNode first = new DLNode(obj, second, trailer)
second.setNext(first)
trailer.setPrev(first)
size++
}
//删除首节点
public Object removeFirst() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空")
DLNode first = header.getNext()
DLNode second = first.getNext()
Object obj = first.getElem()
header.setNext(second)
second.setPrev(header)
size--
return(obj)
}
//删除末节点
public Object removeLast() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空")
DLNode first = trailer.getPrev()
DLNode second = first.getPrev()
Object obj = first.getElem()
trailer.setPrev(second)
second.setNext(trailer)
size--
return(obj)
}
//遍历
public void Traversal() {
DLNode p = header.getNext()
while (p != trailer) {
System.out.print(p.getElem()+" ")
p = p.getNext()
}
System.out.println()
}
}
新建个队列依次往里放就是了。就这样：ArrayList a；//你已经有的a；
ArrayList b；//你已经有的b；
ArrayList c= new ArrayList()
比较a.size()大还是b.size()大,大的=e，小的=q
for(int i=0i<ei++){
if(i<q){
c.add(a.get(i))
c.add(b.get(i))
}
if(i>=q){
c.add(b.get(i))
}
}
写的这样也差不多了吧
