简介

dequeue 指的是双向队列，能够别离从队列的头部插入和获取数据，也能够从队列的尾部插入和获取数据。

本文将会介绍一下怎么创立 dequeue 和 dequeue 的一些基本操作。

双向队列的实现

和一般队列我的项目，双向队列能够别离在头部和尾部进行插入和删除工作，所以一个 dequeue 须要实现这 4 个办法：

• insertFront(): 从 dequeue 头部插入数据
• insertLast(): 从 dequeue 尾部插入数据
• deleteFront(): 从 dequeue 头部删除数据
• deleteLast(): 从 dequeue 尾部删除数据

同样的咱们也须要一个 head 和一个 rear 来指向队列的头部和尾部节点。

也就是说实现了这四个办法的队列就是双向队列。咱们不论它外部是怎么实现的。

接下来咱们来直观的感受一下 dequeue 的插入和删除操作：

1. 在头部插入

2. 在尾部插入

3. 在头部删除

4. 在尾部删除

双向队列也能够有很多种实现形式, 比方循环数组和链表。

双向队列的数组实现

因为数组自身曾经有前后关系，也就是说晓得 head 能够拿到它前面一个数据，晓得 rear 也能够拿到它后面一个数据。

所以数组的实现中，存储 head 和 rear 的 index 值曾经够了。

咱们只须要增加向头部插入数据和向尾部删除数据的办法即可：

// 从头部入队列
    public void insertFront(int data){if(isFull()){System.out.println("Queue is full");
        }else{
            // 从头部插入 ArrayDeque
            head = (head + capacity - 1) % capacity;
            array[head]= data;
            // 如果插入之前队列为空, 将 real 指向 head
            if(rear == -1){rear = head;}
        }
    }

 // 从尾部取数据
    public int deleteLast(){
        int data;
        if(isEmpty()){System.out.println("Queue is empty");
            return -1;
        }else{data= array[rear];
            // 如果只有一个元素，则重置 head 和 real
            if(head == rear){
                head= -1;
                rear = -1;
            }else{rear = (rear + capacity - 1)%capacity;
            }
            return data;
        }
    }

双向队列的动静数组实现

动静数组能够动静扭转数组大小，这里咱们应用倍增的形式来扩大数组。

看下扩大办法怎么实现：

    // 因为是循环数组，这里不能做简略的数组拷贝
    private void extendQueue(){
        int newCapacity= capacity*2;
        int[] newArray= new int[newCapacity];
        // 先全副拷贝
        System.arraycopy(array,0,newArray,0,array.length);
        // 如果 rear<head, 示意曾经进行循环了，须要将 0 -head 之间的数据置空，并将数据拷贝到新数组的相应地位
        if(rear < head){for(int i=0; i< head; i++){
                // 重置 0 -head 的数据
                newArray[i]= -1;
                // 拷贝到新的地位
                newArray[i+capacity]=array[i];
            }
            // 重置 rear 的地位
            rear = rear +capacity;
            // 重置 capacity 和 array
            capacity=newCapacity;
            array=newArray;
        }
    }

因为是循环数组，这里不能做简略的数组拷贝，咱们须要判断 rear 和 head 的地位来判断是否进入到了循环构造。

如果进入到了循环构造，咱们须要重置相应的字段数据，并拷贝到新数组中。

向头部插入数据和向尾部删除数据的办法和根本队列的实现是统一的，这里就不列出来了。

双向队列的链表实现

如果应用链表来实现双向队列会有什么问题呢？

在头部插入和在尾部插入都能够疾速定位到指标节点。然而咱们考虑一下尾部删除的问题。

尾部删除咱们须要找到尾部节点的前一个节点，将这个节点置位 rear 节点。这就须要咱们可能通过 rear 节点找到它的前一个节点。

所以根本的链表曾经满足不了咱们的需要了。这里咱们须要应用双向链表。

public class LinkedListDeQueue {
    //head 节点
    private Node headNode;
    //rear 节点
    private Node rearNode;

    class Node {
        int data;
        Node next;
        Node prev;
        //Node 的构造函数
        Node(int d) {data = d;}
    }

    public boolean isEmpty(){return headNode==null;}

    // 从队尾插入
    public void insertLast(int data){Node newNode= new Node(data);
        // 将 rearNode 的 next 指向新插入的节点
        if(rearNode !=null){
            rearNode.next=newNode;
            newNode.prev=rearNode;
        }
        rearNode=newNode;
        if(headNode == null){headNode=newNode;}
    }

    // 从队首插入
    public void insertFront(int data){if(headNode == null){headNode= new Node(data);
        }else{Node newNode= new Node(data);
            newNode.next= headNode;
            headNode.prev= newNode;
            headNode= newNode;
        }
    }

    // 从队首删除
    public int deleteFront(){
        int data;
        if(isEmpty()){System.out.println("Queue is empty");
            return -1;
        }else{
            data=headNode.data;
            headNode=headNode.next;
            headNode.prev=null;
        }
        return data;
    }

    // 从队尾删除
    public int deleteLast(){
        int data;
        if(isEmpty()){System.out.println("Queue is empty");
            return -1;
        }else{
            data=rearNode.data;
            rearNode=rearNode.prev;
            rearNode.next=null;
        }
        return data;
    }

}

双向链表中的每一个节点都有 next 和 prev 两个指针。通过这两个指针，咱们能够疾速定位到他们的后一个节点和前一个节点。

双向链表的工夫复杂度

下面的 3 种实现的 enQueue 和 deQueue 办法，基本上都能够立马定位到要入队列或者出队列的地位，所以他们的工夫复杂度是 O(1)。

本文的代码地址：

learn-algorithm

本文已收录于 http://www.flydean.com/13-algorithm-dequeue/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！