共计 15902 个字符，预计需要花费 40 分钟才能阅读完成。
大厂算法面试之 leetcode 精讲 18. 队列
视频解说（高效学习）: 点击学习
目录：
1. 开篇介绍
2. 工夫空间复杂度
3. 动静布局
4. 贪婪
5. 二分查找
6. 深度优先 & 广度优先
7. 双指针
8. 滑动窗口
9. 位运算
10. 递归 & 分治
11 剪枝 & 回溯
12. 堆
13. 枯燥栈
14. 排序算法
15. 链表
16.set&map
17. 栈
18. 队列
19. 数组
20. 字符串
21. 树
22. 字典树
23. 并查集
24. 其余类型题
- 队列的特点：先进先出（FIFO）
- 队列的工夫复杂度：入队和出队
O(1)，查找O(n) - 优先队列：
priorityQueue，按优先级出队，实现Heap(Binary,Fibonacci...) - js 里没有队列，然而能够用数组模仿
225. 用队列实现栈 (easy)
办法 1. 应用两个 Queue 实现
- 思路：还是考查栈和队列的相熟水平，没有什么具体的工程实际意义，能够用两个队列来实现栈的性能，然而一个队列的数据导入另一个队列程序还是没有扭转，所以其中一个队列只是用来做备份的，在代码里 queue2 就是备份队列，入栈的时候，队列 1 入队，出栈的时候，如果队列 1 为空，则替换队列 1 和队列 2，为的是将备份队列的元素全副退出队列 1，而后将队列 1 中除了最初一个元素外全副出队，并且退出备份队列，
- 复杂度剖析：push 的工夫复杂度为
O(1)，pop 的工夫复杂度为O(n)。空间复杂度O(n)，其中 n 是栈内元素的个数，用两个队列来存储
动画过大，点击查看
Js:
var MyStack = function() {this.queue1 = [];
this.queue2 = [];// 备份的队列};
MyStack.prototype.push = function(x) {this.queue1.push(x);
};
MyStack.prototype.pop = function() {
// 缩小两个队列替换的次数，只有当 queue1 为空时，替换两个队列
if(!this.queue1.length) {[this.queue1, this.queue2] = [this.queue2, this.queue1];
}
while(this.queue1.length > 1) {// 当队列 1 的元素数量大于 1 的时候一直将元素 push 进备份队列
this.queue2.push(this.queue1.shift());
}
return this.queue1.shift();// 最初将队列 1 最初一个元素出队};
MyStack.prototype.top = function() {const x = this.pop();// 查看栈顶，队列出队，而后在 push 进队列 1
this.queue1.push(x);
return x;
};
MyStack.prototype.empty = function() {return !this.queue1.length && !this.queue2.length;};
Java:
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {queue1 = new LinkedList<>();
queue2 = new LinkedList<>();}
public void push(int x) {queue2.offer(x);
while (!queue1.isEmpty()){queue2.offer(queue1.poll());
}
Queue<Integer> queueTemp;
queueTemp = queue1;
queue1 = queue2;
queue2 = queueTemp;
}
public int pop() {return queue1.poll();
}
public int top() {return queue1.peek();
}
public boolean empty() {return queue1.isEmpty();
}
}
办法 2. 应用一个 队列 实现
动画过大，点击查看
- 思路：应用一个 队列 实现，入栈的时候间接 push 进队列就行，出栈的时候将除了最初一个元素外的元素全副退出到队尾。
- 复杂度剖析：push 的工夫复杂度为
O(1)，pop 的工夫复杂度为O(n)，空间复杂度O(n)
js:
var MyStack = function() {this.queue = [];
};
MyStack.prototype.push = function(x) {this.queue.push(x);
};
MyStack.prototype.pop = function() {
let size = this.queue.length;
while(size-- > 1) {// 将除了最初一个元素外的元素全副退出到队尾。this.queue.push(this.queue.shift());
}
return this.queue.shift();};
MyStack.prototype.top = function() {const x = this.pop();// 先出栈，而后在退出队列
this.queue.push(x);
return x;
};
MyStack.prototype.empty = function() {return !this.queue.length;};
java:
class MyStack {
Deque<Integer> queue1;
public MyStack() {queue1 = new ArrayDeque<>();
}
public void push(int x) {queue1.addLast(x);
}
public int pop() {int size = queue1.size();
size--;
while (size-- > 0) {queue1.addLast(queue1.peekFirst());
queue1.pollFirst();}
int res = queue1.pollFirst();
return res;
}
public int top() {return queue1.peekLast();
}
public boolean empty() {return queue1.isEmpty();
}
}
703. 数据流中的第 K 大元素 (easy)
办法 1: 暴力排序
- 思路：当数据流有新的元素的时候，从新按升序排序数组，倒数第 k 个元素就是第 k 大的数
- 复杂度剖析：工夫复杂度
O(c*zlogz)，z 为数据流的最长长度，c 为退出元素的个数，排序复杂度是O(zlogz)，退出 c 次排序就须要排序 c 次。
办法 2: 堆
- 思路：用一个 size 是 k 的小顶堆来存贮前 k 个元素，堆顶是最小的元素，在循环数组的过程中，一直退出元素而后调整元素在堆中的地位，如果此时优先队列的大小大于 k，咱们须要将优先队列的队头元素弹出，以保障优先队列的大小为 k，最初堆顶就是第 K 大元素的地位
- 复杂度剖析：工夫复杂度
O(nlogk)，n 是初始数组的大小，k 是堆的大小，初始堆化和单次插入堆的复杂度都是O(logk)，数组的每个数都要插入堆中一次，所以是O(nlogk)。空间复杂度：O(k), 即堆的大小
js:
var KthLargest = function (k, nums) {
this.k = k;
this.heap = new Heap();
for (const x of nums) {// 将数组中的数退出小顶堆
this.add(x);// 退出小顶堆
}
};
KthLargest.prototype.add = function (val) {this.heap.offer(val);// 退出堆
if (this.heap.size() > this.k) {// 大小超过了小顶堆的 size，就从小顶堆删除一个最小的元素
this.heap.poll();// 删除最小的元素}
return this.heap.peek();// 返回堆顶};
class Heap {constructor(comparator = (a, b) => a - b, data = []) {
this.data = data;
this.comparator = comparator;// 比拟器
this.heapify();// 堆化}
heapify() {if (this.size() < 2) return;
for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) {this.bubbleDown(i);//bubbleDown 操作
}
}
peek() {if (this.size() === 0) return null;
return this.data[0];// 查看堆顶
}
offer(value) {this.data.push(value);// 退出数组
this.bubbleUp(this.size() - 1);// 调整退出的元素在小顶堆中的地位
}
poll() {if (this.size() === 0) {return null;}
const result = this.data[0];
const last = this.data.pop();
if (this.size() !== 0) {this.data[0] = last;// 替换第一个元素和最初一个元素
this.bubbleDown(0);//bubbleDown 操作
}
return result;
}
bubbleUp(index) {while (index > 0) {const parentIndex = (index - 1) >> 1;// 父节点的地位
// 如果以后元素比父节点的元素小，就替换以后节点和父节点的地位
if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {this.swap(index, parentIndex);// 替换本人和父节点的地位
index = parentIndex;// 一直向上取父节点进行比拟
} else {break;// 如果以后元素比父节点的元素大，不须要解决}
}
}
bubbleDown(index) {const lastIndex = this.size() - 1;// 最初一个节点的地位
while (true) {
const leftIndex = index * 2 + 1;// 左节点的地位
const rightIndex = index * 2 + 2;// 右节点的地位
let findIndex = index;//bubbleDown 节点的地位
// 找出左右节点中 value 小的节点
if (
leftIndex <= lastIndex &&
this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
) {findIndex = leftIndex;}
if (
rightIndex <= lastIndex &&
this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
) {findIndex = rightIndex;}
if (index !== findIndex) {this.swap(index, findIndex);// 替换以后元素和左右节点中 value 小的
index = findIndex;
} else {break;}
}
}
swap(index1, index2) {// 替换堆中两个元素的地位
[this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
}
size() {return this.data.length;}
}java:
class KthLargest {
PriorityQueue<Integer> pq;
int k;
public KthLargest(int k, int[] nums) {
this.k = k;
pq = new PriorityQueue<Integer>();
for (int x : nums) {add(x);
}
}
public int add(int val) {pq.offer(val);
if (pq.size() > k) {pq.poll();
}
return pq.peek();}
}
23. 合并 K 个升序链表 (hard)
办法 1. 分治
- 思路：自底而上归并，第一次归并 2 个链表，第二次归并 4 个链表 …，每次归并一直合并两个有序链表，直到合并完所有分治后的链表
- 复杂度：工夫复杂度
O(n * logk)，n 是每个链表节点数，k 个链表个数，每次归并，链表数量较少一半，复杂度是O(logk)，将两个链表合并成一个程序链表复杂度是O(2n)，所以工夫复杂度是O(n * logk)。空间复杂度是O(logk)，即递归的空格复杂度
js:
// 自顶而下归并 先分在合
var mergeKLists = function (lists) {
// 当是空数组的状况下
if (!lists.length) {return null;}
// 合并两个排序链表
const merge = (head1, head2) => {let dummy = new ListNode(0);
let cur = dummy;
// 新链表，新的值小就先接谁
while (head1 && head2) {if (head1.val < head2.val) {
cur.next = head1;
head1 = head1.next;
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
// 如果前面还有残余的就把残余的接上
cur.next = head1 == null ? head2 : head1;
return dummy.next;
};
const mergeLists = (lists, start, end) => {if (start + 1 == end) {return lists[start];
}
// 输出的 k 个排序链表，能够分成两局部，前 k / 2 个链表和后 k / 2 个链表
// 如果将这前 k / 2 个链表和后 k / 2 个链表别离合并成两个排序的链表，再将两个排序的链表合并，那么所有链表都合并了
let mid = (start + end) >> 1;
let head1 = mergeLists(lists, start, mid);
let head2 = mergeLists(lists, mid, end);
return merge(head1, head2);
};
return mergeLists(lists, 0, lists.length);
};
// 自底而上合并
var mergeKLists = function (lists) {if (lists.length <= 1) return lists[0] || null;// 当归并的节点只有一个时 返回这个节点
const newLists = [];
// 自底而上归并，第一次归并大小为 2 的链表，第二次归并大小 4 的链表...
for (let i = 0; i < lists.length; i += 2) {newLists.push(merge(lists[i], lists[i + 1] || null));
}
return mergeKLists(newLists);
};
const merge = (list_1, list_2) => {// 合并两个有序链表
const dummyNode = new ListNode(0);
let p = dummyNode;
while (list_1 && list_2) {if (list_1.val < list_2.val) {// 先将小的节点退出
p.next = list_1;
list_1 = list_1.next;
} else {
p.next = list_2;
list_2 = list_2.next;
}
p = p.next;
}
p.next = list_1 ? list_1 : list_2;// 遍历实现还有节点残余
return dummyNode.next;
};java:
class Solution {public ListNode mergeKLists(ListNode[] lists) {return mergeLists(lists, 0, lists.length - 1);
}
public ListNode mergeLists(ListNode[] lists, int start, int end) {if (start == end) {return lists[start];
}
if (start > end) {return null;}
int mid = (start + end) >> 1;
return merge(mergeLists(lists, start, mid), mergeLists(lists, mid + 1, end));
}
public ListNode merge(ListNode head1, ListNode head2) {if (head1 == null || head2 == null) {return head1 != null ? head1 : head2;}
ListNode dummyNode = new ListNode(0);
ListNode cur = dummyNode;
while (head1 != null && head2 != null) {if (head1.val < head2.val) {
cur.next = head1;
head1 = head1.next;
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
cur.next = (head1 != null ? head1 : head2);
return dummyNode.next;
}
}办法 2. 优先队列
- 思路：新建小顶堆，小顶堆的大小是 k，一直从每个链表的头节点开始一直退出小顶堆中，而后取出堆顶值，也就是最小值，而后持续往小顶堆中插入这个最小值在链表的 next 节点
- 复杂度：工夫复杂度
O(kn * logk)，优先队列的大小是 k，每次插入和删除是O(logk)，总共 k * n 的节点个数，每个节点插入删除一次，所以总的复杂度是O(kn*logk)。空间复杂度是O(k)，即优先队列的大小
js:
class Heap {constructor(comparator = (a, b) => a - b, data = []) {this.data = data; this.comparator = comparator;// 比拟器 this.heapify();// 堆化 } heapify() { if (this.size() < 2) return; for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) {this.bubbleDown(i);//bubbleDown 操作 } } peek() { if (this.size() === 0) return null; return this.data[0];// 查看堆顶 } offer(value) {this.data.push(value);// 退出数组 this.bubbleUp(this.size() - 1);// 调整退出的元素在小顶堆中的地位 } poll() { if (this.size() === 0) {return null;} const result = this.data[0]; const last = this.data.pop(); if (this.size() !== 0) {this.data[0] = last;// 替换第一个元素和最初一个元素 this.bubbleDown(0);//bubbleDown 操作 } return result; } bubbleUp(index) {while (index > 0) {const parentIndex = (index - 1) >> 1;// 父节点的地位 // 如果以后元素比父节点的元素小，就替换以后节点和父节点的地位 if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {this.swap(index, parentIndex);// 替换本人和父节点的地位 index = parentIndex;// 一直向上取父节点进行比拟 } else {break;// 如果以后元素比父节点的元素大，不须要解决} } } bubbleDown(index) {const lastIndex = this.size() - 1;// 最初一个节点的地位 while (true) {const leftIndex = index * 2 + 1;// 左节点的地位 const rightIndex = index * 2 + 2;// 右节点的地位 let findIndex = index;//bubbleDown 节点的地位 // 找出左右节点中 value 小的节点 if ( leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex]) < 0 ) {findIndex = leftIndex;} if (rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex]) < 0 ) {findIndex = rightIndex;} if (index !== findIndex) {this.swap(index, findIndex);// 替换以后元素和左右节点中 value 小的 index = findIndex; } else {break;} } } swap(index1, index2) {// 替换堆中两个元素的地位 [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]]; } size() { return this.data.length;}}var mergeKLists = function(lists) {const res = new ListNode(0); let p = res; const h = new Heap(comparator = (a, b) => a.val - b.val); lists.forEach(l => {// 插入每个链表的第一个节点 if(l) h.offer(l); }) while(h.size()) {// const n = h.poll();// 取出最小值 p.next = n;// 最小值退出 p 的 next 后 p = p.next;// 挪动 p 节点 if(n.next) h.offer(n.next);// 插入最小节点的后一个节点 } return res.next;};java:
class Solution {
class Status implements Comparable<Status> {
int val;
ListNode ptr;
Status(int val, ListNode ptr) {
this.val = val;
this.ptr = ptr;
}
public int compareTo(Status status2) {return this.val - status2.val;}
}
PriorityQueue<Status> h = new PriorityQueue<Status>();
public ListNode mergeKLists(ListNode[] lists) {for (ListNode node: lists) {if (node != null) {h.offer(new Status(node.val, node));
}
}
ListNode res = new ListNode(0);
ListNode p = res;
while (!h.isEmpty()) {Status n = h.poll();
p.next = n.ptr;
p = p.next;
if (n.ptr.next != null) {h.offer(new Status(n.ptr.next.val, n.ptr.next));
}
}
return res.next;
}
}
347. 前 K 个高频元素（medium）
办法 1: 优先队列
- 思路：循环数组，退出小顶堆，当堆的 size 超过 k 时，出堆，循环实现之后，堆中所有的元素就是前 k 大的数字
- 复杂度：工夫复杂度
O(nlogk)，循环 n 次，每次堆的操作是O(logk)。空间复杂度O(k)，
js：
class Heap {constructor(comparator = (a, b) => a - b, data = []) {
this.data = data;
this.comparator = comparator;// 比拟器
this.heapify();// 堆化}
heapify() {if (this.size() < 2) return;
for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) {this.bubbleDown(i);//bubbleDown 操作
}
}
peek() {if (this.size() === 0) return null;
return this.data[0];// 查看堆顶
}
offer(value) {this.data.push(value);// 退出数组
this.bubbleUp(this.size() - 1);// 调整退出的元素在小顶堆中的地位
}
poll() {if (this.size() === 0) {return null;}
const result = this.data[0];
const last = this.data.pop();
if (this.size() !== 0) {this.data[0] = last;// 替换第一个元素和最初一个元素
this.bubbleDown(0);//bubbleDown 操作
}
return result;
}
bubbleUp(index) {while (index > 0) {const parentIndex = (index - 1) >> 1;// 父节点的地位
// 如果以后元素比父节点的元素小，就替换以后节点和父节点的地位
if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {this.swap(index, parentIndex);// 替换本人和父节点的地位
index = parentIndex;// 一直向上取父节点进行比拟
} else {break;// 如果以后元素比父节点的元素大，不须要解决}
}
}
bubbleDown(index) {const lastIndex = this.size() - 1;// 最初一个节点的地位
while (true) {
const leftIndex = index * 2 + 1;// 左节点的地位
const rightIndex = index * 2 + 2;// 右节点的地位
let findIndex = index;//bubbleDown 节点的地位
// 找出左右节点中 value 小的节点
if (
leftIndex <= lastIndex &&
this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
) {findIndex = leftIndex;}
if (
rightIndex <= lastIndex &&
this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
) {findIndex = rightIndex;}
if (index !== findIndex) {this.swap(index, findIndex);// 替换以后元素和左右节点中 value 小的
index = findIndex;
} else {break;}
}
}
swap(index1, index2) {// 替换堆中两个元素的地位
[this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
}
size() {return this.data.length;}
}
var topKFrequent = function (nums, k) {const map = new Map();
for (const num of nums) {// 统计频次
map.set(num, (map.get(num) || 0) + 1);
}
// 创立小顶堆
const priorityQueue = new Heap((a, b) => a[1] - b[1]);
//entry 是一个长度为 2 的数组，0 地位存储 key，1 地位存储 value
for (const entry of map.entries()) {priorityQueue.offer(entry);// 退出堆
if (priorityQueue.size() > k) {// 堆的 size 超过 k 时，出堆
priorityQueue.poll();}
}
const ret = [];
for (let i = priorityQueue.size() - 1; i >= 0; i--) {// 取出前 k 大的数
ret[i] = priorityQueue.poll()[0];
}
return ret;
};
java：
class Solution {public int[] topKFrequent(int[] nums, int k) {int[] ret = new int[k];
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);
}
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
for (Map.Entry<Integer, Integer> entry : entries) {priorityQueue.offer(entry);
if (priorityQueue.size() > k) {priorityQueue.poll();
}
}
for (int i = k - 1; i >= 0; i--) {ret[i] = priorityQueue.poll().getKey();
}
return ret;
}
}692. 前 K 个高频单词(medium)
办法 1: 排序
js：
var topKFrequent = function (words, k) {const map = {};
words.forEach(v => map[v] = (map[v] || 0) + 1);
const keys = Object.keys(map).sort((a, b) => map[b] - map[a] || a.localeCompare(b))
return keys.slice(0, k);
};办法 2：堆
js:
class Heap {constructor(comparator = (a, b) => a - b, data = []) {
this.data = data;
this.comparator = comparator;// 比拟器
this.heapify();// 堆化}
heapify() {if (this.size() < 2) return;
for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) {this.bubbleDown(i);//bubbleDown 操作
}
}
peek() {if (this.size() === 0) return null;
return this.data[0];// 查看堆顶
}
offer(value) {this.data.push(value);// 退出数组
this.bubbleUp(this.size() - 1);// 调整退出的元素在小顶堆中的地位
}
poll() {if (this.size() === 0) {return null;}
const result = this.data[0];
const last = this.data.pop();
if (this.size() !== 0) {this.data[0] = last;// 替换第一个元素和最初一个元素
this.bubbleDown(0);//bubbleDown 操作
}
return result;
}
bubbleUp(index) {while (index > 0) {const parentIndex = (index - 1) >> 1;// 父节点的地位
// 如果以后元素比父节点的元素小，就替换以后节点和父节点的地位
if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {this.swap(index, parentIndex);// 替换本人和父节点的地位
index = parentIndex;// 一直向上取父节点进行比拟
} else {break;// 如果以后元素比父节点的元素大，不须要解决}
}
}
bubbleDown(index) {const lastIndex = this.size() - 1;// 最初一个节点的地位
while (true) {
const leftIndex = index * 2 + 1;// 左节点的地位
const rightIndex = index * 2 + 2;// 右节点的地位
let findIndex = index;//bubbleDown 节点的地位
// 找出左右节点中 value 小的节点
if (
leftIndex <= lastIndex &&
this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
) {findIndex = leftIndex;}
if (
rightIndex <= lastIndex &&
this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
) {findIndex = rightIndex;}
if (index !== findIndex) {this.swap(index, findIndex);// 替换以后元素和左右节点中 value 小的
index = findIndex;
} else {break;}
}
}
swap(index1, index2) {// 替换堆中两个元素的地位
[this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
}
size() {return this.data.length;}
}
var topKFrequent = function (nums, k) {const map = new Map();
for (const num of nums) {// 统计频次
map.set(num, (map.get(num) || 0) + 1);
}
// 创立小顶堆
const priorityQueue = new Heap((a, b) => {return a[1] === b[1] ? b[0].localeCompare(a[0]) : a[1] - b[1]
});
//entry 是一个长度为 2 的数组，0 地位存储 key，1 地位存储 value
for (const entry of map.entries()) {priorityQueue.offer(entry);// 退出堆
if (priorityQueue.size() > k) {// 堆的 size 超过 k 时，出堆
priorityQueue.poll();}
}
const ret = [];
for (let i = priorityQueue.size() - 1; i >= 0; i--) {// 取出前 k 大的数
ret[i] = priorityQueue.poll()[0];
}
return ret;
};
933. 最近的申请次数 (easy)
- 思路：将申请退出队列，如果队头元素申请的工夫在
[t-3000,t]之外 就一直出队 - 复杂度：工夫复杂度
O(q)，q 是 ping 的次数。空间复杂度O(w)，w 是队列中最多的元素个数
js：
var RecentCounter = function() {this.queue = []
};
RecentCounter.prototype.ping = function(t) {this.queue.push(t);// 新申请入队
const time = t-3000;// 计算 3000ms 前的工夫
while(this.queue[0] < time){// 如果队头元素申请的工夫在 [t-3000,t] 之外 就一直出队
this.queue.shift();}
return this.queue.length;// 在 [t-3000,t] 区间内队列残余的元素就是符合要求的申请数
};
java：
class RecentCounter {
Queue<Integer> q;
public RecentCounter() {q = new LinkedList();
}
public int ping(int t) {q.add(t);
while (q.peek() < t - 3000)
q.poll();
return q.size();}
}
622. 设计循环队列 (medium)
- 复杂度: 工夫复杂度
O(1)，空间复杂度O(k)
js:
var MyCircularQueue = function(k) {
this.front = 0
this.rear = 0
this.max = k
this.list = Array(k)
};
MyCircularQueue.prototype.enQueue = function(value) {if(this.isFull()) {return false} else {this.list[this.rear] = value
this.rear = (this.rear + 1) % this.max
return true
}
};
MyCircularQueue.prototype.deQueue = function() {let v = this.list[this.front]
this.list[this.front] = undefined
if(v !== undefined) {this.front = (this.front + 1) % this.max
return true
} else {return false}
};
MyCircularQueue.prototype.Front = function() {if(this.list[this.front] === undefined) {return -1} else {return this.list[this.front]
}
};
MyCircularQueue.prototype.Rear = function() {
let rear = this.rear - 1
if(this.list[rear < 0 ? this.max - 1 : rear] === undefined) {return -1} else {return this.list[rear < 0 ? this.max - 1 : rear]
}
};
MyCircularQueue.prototype.isEmpty = function() {return this.front === this.rear && !this.list[this.front]
};
MyCircularQueue.prototype.isFull = function() {return (this.front === this.rear) && !!this.list[this.front]
};
正文完