这篇文章是对LeetCode641题设计循环双端队列思路进行记录。(PS:后续应该还会在写一篇，等我把双向链表实现搞清楚了，一个指针还能理清，两个指针pre和next看着就有点晕了，等我消化下。)

先看下题：

设计实现双端队列。
你的实现须要反对以下操作：

MyCircularDeque(k)：构造函数,双端队列的大小为k。
insertFront()：将一个元素增加到双端队列头部。 如果操作胜利返回 true。
insertLast()：将一个元素增加到双端队列尾部。如果操作胜利返回 true。
deleteFront()：从双端队列头部删除一个元素。 如果操作胜利返回 true。
deleteLast()：从双端队列尾部删除一个元素。如果操作胜利返回 true。
getFront()：从双端队列头部取得一个元素。如果双端队列为空，返回 -1。
getRear()：取得双端队列的最初一个元素。 如果双端队列为空，返回 -1。
isEmpty()：查看双端队列是否为空。
isFull()：查看双端队列是否满了。
示例：

MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 曾经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4

家喻户晓栈和队列都是限制性的数据结构，在某些业务场景常常用到，而栈和队列其实用两种根本的数据结构数组和链表都能实现的。明天咱们先来看看如何用数组设计循环双端队列。

class MyCircularDeque {    private int[] items;    private int count;    private int head;    private int tail;    public MyCircularDeque(int k) {        this.count = k+1;        this.items = new int[count];        this.head = 0;        this.tail = 0;    }    public boolean insertFront(int value) {        if (isFull()) {            return false;        }        head = (head - 1 + count) % count;        items[head] = value;        return true;    }    public boolean insertLast(int value) {        if (isFull()) {            return false;        }        items[tail] = value;        tail = (tail + 1) % count;        return true;    }    public boolean deleteFront() {        if (isEmpty()) {            return false;        }        head = (head + 1) % count;        return true;    }    public boolean deleteLast() {        if (isEmpty()) {            return false;        }        tail = (tail - 1 + count) % count;        return true;    }    public int getFront() {        if (isEmpty()) {            return -1;        }        return items[head];    }    public int getRear() {        if (isEmpty()) {            return -1;        }        return items[(tail - 1 + count) % count];    }    public boolean isEmpty() {        return head == tail;    }    public boolean isFull() {        return (tail + 1) % count == head;    }}

首先循环队列你能够设想成一个环状，首尾是相连的，再来它的元素地位是随插入删除始终挪动的，因而效率其实是偏低的，插入元素会波及数据迁徙，所以工业上的队列个别是用链表实现的。

而后解释下几个成员变量：

  • items[],理论用来存储数据的数组
  • count,整个数组的具体大小
  • head，头指针所在的下标地位
  • tail,尾指针所在的下标地位。这里须要留神的一点是tail这个地位实际上是不会存储数据的，最初一个元素的下标是(tail-1+count)%count所以会节约一个地位。

设计这个咱们首先思考构造函数，因为有k个元素，而tail会多占一个地位，因而理论须要k+1的空间，head和tail初始值都是0.

接下来先别看插入删除这些，看两个根本函数，isEmpty()和isFull()，先把这两个定义分明后在写其余函数会简略很多。

isEmpty()的条件其实很容易想到，就是head==tail;.

isFull()其实不太好想，满的条件就是tail和head相邻，只差一个元素，用代码示意就是 (tail+1)%count==head;.这里模上count的起因是因为tail+1可能超过count，这时候head其实就是在0的地位。循环队列的下标计算常常会用到%count的操作，这个须要记住。

这两个根本实现了在实现其余的就简略很多了。

insertFront（value）实现就是先判断队列是否满了，如果满了就返回false，否则将head-1存储的值设置成value。须要思考当head=0的时候head-1是正数，所以须要head-1+count去将其变成负数在模上count。

insertLast（value）思路和下面差不多，你能够本人想一下。

deleteFront ()则是首先判断是否为空队列，为空间接返回false，否则将head+1，当然，为避免越界会用 (head+1)%count，这里实际上不须要在将items[head]=null，起因是咱们拜访数组元素都是通过head和tail，当head和tail拜访不到那其实元素是什么都无所谓。你可能会说在插入的时候会不会产生影响，答案是不会，因为在插入的时候都随同赋值操作，以前内存里什么值基本不影响。

deleteLast（）思路同上，而后在下标进行-1的时候都须要思考越界，所以须要(tail-1+count)%count。

getFront() 判断是否为空队列，为空间接返回-1，否则间接返回Items[head]即可。

getRear() 判断是否为空队列，为空间接返回-1，和后面介绍的一样，tail是站位的，理论最初一个元素是在tail-1的地位，而后思考越界，所以最初后果就是items[(tail-1+count)%count].

写在最初

数组实现会相比链表实现低效很多，因为数组在插入和删除会波及前面数据的迁徙，比拟耗时。而链表实现则会快很多。