简介

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

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

双向队列的实现

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

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

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

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

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

  1. 在头部插入

  1. 在尾部插入

  1. 在头部删除

  1. 在尾部删除

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

双向队列的数组实现

因为数组自身曾经有前后关系，也就是说晓得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/

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

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