这篇文章是对 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].
写在最初
数组实现会相比链表实现低效很多,因为数组在插入和删除会波及前面数据的迁徙,比拟耗时。而链表实现则会快很多。