双端队列

  双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。我们将使用双链表实现双端队列，下面首先介绍双向链表。

双向链表

  双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。下面给出双向链表的具体实现：

package com.node;

public class DLNode{

    private Object data;
    private DLNode pre;
    private DLNode next;
    
    public DLNode() {
        this(null,null,null);
    }

    public DLNode(Object data, DLNode pre, DLNode next) {
        this.data = data;
        this.pre = pre;
        this.next = next;
    }

    public Object getElem() {
        return data;
    }

    public void setElem(Object elem) {
        
        this.data = elem;
    }

    public DLNode getPre() {
        return pre;
    }

    public void setPre(DLNode pre) {
        this.pre = pre;
    }

    public DLNode getNext() {
        return next;
    }

    public void setNext(DLNode next) {
        this.next = next;
    }
        
}

基于双向链表的双端队列

  在基于NLNode类实现双向链表的时候，为了使编程更加简洁，通常我们都要在最前端和最后端各设置一个哑元节点（Dummy node）。这两个节点分别称作头节点（Header node）和尾节点（Trailer node）㈠，起哨兵（Sentinel）的作用。也就是说，它们并不存储任何实质的数据对象，头（尾）节点的next（prev）引用指向首（末）节点，而prev（next）引用为空。如此构成的列表如图所示，

双端队列示意图

package com.queue;

import com.node.DLNode;

public class Deque_DLNode implements Deque{

    protected DLNode header;
    protected DLNode tailer;
    protected int size;
    
    public Deque_DLNode()
    {
        header = new DLNode();
        tailer = new DLNode();
        header.setNext(tailer);
        tailer.setPre(header);
        size = 0;
    }
    
    @Override
    public int getSize() {

        return size;
    }

    @Override
    public boolean isEmpty() {

        return (0 == size)?true:false;
    }

    @Override
    public Object first() {
        if(isEmpty())
        {
            return null;
        }
        return header.getNext().getElem();
    }

    @Override
    public Object last() {
        if(isEmpty())
        {
            return null;
        }
        return tailer.getPre().getElem();
    }

    @Override
    public void insertFirst(Object elem) {
        DLNode second = header;
        DLNode newNode = new DLNode(elem,header,second);
        second.setPre(newNode);
        header.setNext(newNode);
        size++;
        
    }

    @Override
    public void insertLast(Object elem) {
        DLNode second = tailer.getPre();
        DLNode newNode = new DLNode(elem,second,tailer);
        second.setNext(newNode);
        tailer.setPre(newNode);
        size++;
    }

    @Override
    public Object removeFirst() {
        if(isEmpty())
        {
            System.out.println("队列为空");
            return null;
        }
        
        DLNode temp = header.getNext();
        header.setNext(temp.getNext());
        temp.getNext().setPre(header);
        size--;
        return temp.getElem();
    }

    @Override
    public Object removeLast() {
        if(isEmpty())
        {
            System.out.println("队列为空");
            return null;
        }
        DLNode temp = tailer.getPre();
        tailer.setPre(temp.getPre());
        temp.getPre().setNext(tailer);
        size--;
        return temp.getElem();
    }

    @Override
    public void Traversal() {
        DLNode p =header.getNext();
        while(p != tailer)
        {
            System.out.println(p.getElem()+ " ");
            p = p.getNext();
        }
        System.out.println();
    }

}