题目形容
这是 LeetCode 上的 641. 设计循环双端队列 ，难度为 中等。
Tag : 「数组」、「链表」、「数据结构」
设计实现双端队列。
实现 MyCircularDeque 类:
MyCircularDeque(int k)：构造函数,双端队列最大为 $k$ 。boolean insertFront()：将一个元素增加到双端队列头部。 如果操作胜利返回true，否则返回false。boolean insertLast()：将一个元素增加到双端队列尾部。如果操作胜利返回true，否则返回false。boolean deleteFront()：从双端队列头部删除一个元素。 如果操作胜利返回true，否则返回false。boolean deleteLast()：从双端队列尾部删除一个元素。如果操作胜利返回true，否则返回false。int getFront()：从双端队列头部取得一个元素。如果双端队列为空，返回-1。int getRear()：取得双端队列的最初一个元素。 如果双端队列为空，返回-1。boolean isEmpty()：若双端队列为空，则返回true，否则返回false。boolean isFull()：若双端队列满了，则返回true，否则返回false。
示例 1：
输出["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"][[3], [1], [2], [3], [4], [], [], [], [4], []]输入[null, true, true, true, false, 2, true, true, true, 4]解释MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3circularDeque.insertLast(1); // 返回 truecircularDeque.insertLast(2); // 返回 truecircularDeque.insertFront(3); // 返回 truecircularDeque.insertFront(4); // 曾经满了，返回 falsecircularDeque.getRear(); // 返回 2circularDeque.isFull(); // 返回 truecircularDeque.deleteLast(); // 返回 truecircularDeque.insertFront(4); // 返回 truecircularDeque.getFront(); // 返回 4提醒：
- $1 <= k <= 1000$
- $0 <= value <= 1000$
insertFront,insertLast,deleteFront,deleteLast,getFront,getRear,isEmpty,isFull调用次数不大于2000次
根本剖析
一个根本的实现，须要满足除构造函数以外复杂度为 $O(k)$ 以外，其余操作均为 $O(1)$。
惯例实现蕴含两种形式：数组实现 与 链表实现。
其中数组实现能够利用调用次数较小，开成调用次数 $3$ 倍大小，而后从两头开始往两边存储，这样做就不必思考下标边的界问题；而更为惯例的解法是结构一个与限定空间 $k$ 等大的数组，应用两下标并配合坐标转换来做，对于下标自增操作而言，只须要进行「加一取模」即可，而对于下标自减操作，因为思考负值问题，须要进行「减少限定空间偏移后，进行减一再取模」。
而链表实现则毋庸思考额定的下标转换问题，但须要额定定义类。
数组
应用两坐标 he 和 ta 别离代表队列头和尾（初始值均为 $0$），应用 cnt 记录以后队列元素大小，应用 k 记录初始化时指定的空间大小。
对各类操作进行逻辑管制：
insertFront操作：须要对he进行自减操作，即he = (he + k - 1) % k为指标地位，同时对cnt进行自增；insertLast操作：须要对ta进行自增操作，但ta起始指向是待插入地位，因而ta为指标地位，随后更新ta = (ta + 1) % k，同时对cnt进行自增；deleteFront操作：须要对he进行自增操作，间接更新he = (he + 1) % k，同时更新cnt进行自减；deleteLast操作：须要对ta进行自减操作，更新ta = (ta + k - 1) % k，同时更新cnt进行自减；getFront操作：返回nums[he]即可， 若isFull为True，返回-1；getRear操作：返回nums[ta - 1]，因为存在负值问题，须要转换为返回nums[(ta + k - 1) % k]若isFull为True，返回-1；isEmpty操作：依据cnt与k的关系进行返回；isFull操作：依据cnt与k的关系进行返回；
Java 代码：
class MyCircularDeque { int[] nums; int he, ta, cnt, k; public MyCircularDeque(int _k) { k = _k; nums = new int[k]; } public boolean insertFront(int value) { if (isFull()) return false; he = (he + k - 1) % k; nums[he] = value; cnt++; return true; } public boolean insertLast(int value) { if (isFull()) return false; nums[ta++] = value; cnt++; ta %= k; return true; } public boolean deleteFront() { if (isEmpty()) return false; he = (he + 1) % k; cnt--; return true; } public boolean deleteLast() { if (isEmpty()) return false; ta = (ta + k - 1) % k; cnt--; return true; } public int getFront() { return isEmpty() ? -1 : nums[he]; } public int getRear() { return isEmpty() ? -1 : nums[(ta + k - 1) % k]; } public boolean isEmpty() { return cnt == 0; } public boolean isFull() { return cnt == k; }}TypeScript 代码：
class MyCircularDeque { he = 0; ta = 0; cnt = 0; k = 0; nums: number[]; constructor(_k: number) { this.k = _k this.he = this.ta = this.cnt = 0 this.nums = new Array<number>(this.k) } insertFront(value: number): boolean { if (this.isFull()) return false this.he = (this.he + this.k - 1) % this.k this.nums[this.he] = value this.cnt++ return true } insertLast(value: number): boolean { if (this.isFull()) return false this.nums[this.ta++] = value this.ta %= this.k this.cnt++ return true } deleteFront(): boolean { if (this.isEmpty()) return false this.he = (this.he + 1) % this.k this.cnt-- return true } deleteLast(): boolean { if (this.isEmpty()) return false this.ta = (this.ta + this.k - 1) % this.k this.cnt-- return true } getFront(): number { return this.isEmpty() ? -1 : this.nums[this.he] } getRear(): number { return this.isEmpty() ? -1 : this.nums[(this.ta + this.k - 1) % this.k] } isEmpty(): boolean { return this.cnt == 0 } isFull(): boolean { return this.cnt == this.k }}- 工夫复杂度：除在初始化函数中结构容器复杂度为 $O(k)$ 以外，其余操作复杂度均为 $O(1)$
- 空间复杂度：$O(n)$
链表
创立 Node 代指每个操作的元素，应用双向链表来结构循环队列。
各类操作均对应根本的链表操作，不再赘述。
Java 代码：
class MyCircularDeque { class Node { Node prev, next; int val; Node (int _val) { val = _val; } } int cnt, k; Node he, ta; public MyCircularDeque(int _k) { k = _k; he = new Node(-1); ta = new Node(-1); he.next = ta; ta.prev = he; } public boolean insertFront(int value) { if (isFull()) return false; Node node = new Node(value); node.next = he.next; node.prev = he; he.next.prev = node; he.next = node; cnt++; return true; } public boolean insertLast(int value) { if (isFull()) return false; Node node = new Node(value); node.next = ta; node.prev = ta.prev; ta.prev.next = node; ta.prev = node; cnt++; return true; } public boolean deleteFront() { if (isEmpty()) return false; he.next.next.prev = he; he.next = he.next.next; cnt--; return true; } public boolean deleteLast() { if (isEmpty()) return false; ta.prev.prev.next = ta; ta.prev = ta.prev.prev; cnt--; return true; } public int getFront() { return isEmpty() ? -1 : he.next.val; } public int getRear() { return isEmpty() ? -1 : ta.prev.val; } public boolean isEmpty() { return cnt == 0; } public boolean isFull() { return cnt == k; }}TypeScript 代码：
class TNode { prev: TNode = null; next: TNode = null; val: number = 0; constructor(_val: number) { this.val = _val }}class MyCircularDeque { he = null; ta = null; cnt = 0; k = 0; constructor(_k: number) { this.cnt = 0; this.k = _k; this.he = new TNode(-1); this.ta = new TNode(-1); this.he.next = this.ta this.ta.prev = this.he } insertFront(value: number): boolean { if (this.isFull()) return false const node = new TNode(value) node.next = this.he.next node.prev = this.he this.he.next.prev = node this.he.next = node this.cnt++ return true } insertLast(value: number): boolean { if (this.isFull()) return false const node = new TNode(value) node.next = this.ta node.prev = this.ta.prev this.ta.prev.next = node this.ta.prev = node this.cnt++ return true } deleteFront(): boolean { if (this.isEmpty()) return false this.he.next.next.prev = this.he this.he.next = this.he.next.next this.cnt-- return true } deleteLast(): boolean { if (this.isEmpty()) return false this.ta.prev.prev.next = this.ta this.ta.prev = this.ta.prev.prev this.cnt-- return true } getFront(): number { return this.isEmpty() ? -1 : this.he.next.val } getRear(): number { return this.isEmpty() ? -1 : this.ta.prev.val } isEmpty(): boolean { return this.cnt == 0 } isFull(): boolean { return this.cnt == this.k }}- 工夫复杂度：所有操作复杂度均为 $O(1)$
- 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.641 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布