常见算法题分类总结之线程池与任务队列(Task-Queue)

队列有两种存储表示方法：「顺序存储的队列」 和 「链式存储的队列」

队列有两种基本操作：「插入操作」 和  「删除操作」。
队列的插入操作又称为「入队」。 队列的删除操作又称为「出队」

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了， 我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储 新的值。
你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
​​​​​​​isFull(): 检查循环队列是否已满。

这里需要重点学习的地方：

1. 用数组实现一个顺序队列 2.  用链表实现一个链式队列 3 .实现一个循环队列

LeetCode
Design Circular Deque（设计一个双端队列）：https://leetcode-cn.com/problems/designcircular-deque/
Sliding Window Maximum（滑动窗口最大值）：https://leetcodecn.com/problems/sliding-window-maximum/

接下来我们来看一些我分类做的一些题

这里首先放几个承接上个博客的链表题目，大家可以借此复习一下上一次所学内容，可以看看自己看题目之后是不是有思路了，可以先去力扣手动实现一下。

//分隔链表public class Num86 {public ListNode partition(ListNode head, int x) { ListNode small = new ListNode(-1, head); ListNode big = new ListNode(-1, head); ListNode s = small, b = big; while(head != null){     //小的那一段     if(head.val < x){  s.next = head;  s = s.next;     }else{  //大于等于那一段  b.next = head;  b= b.next;     }     //迭代     head = head.next; } b.next = null; s.next = big.next; return small.next;}}/ * 复制带随机指针的链表 * @author William * @date 2022-03-04 */class Node {    int val;    Node next;    Node random;    public Node(int val) { this.val = val; this.next = null; this.random = null;    }}public class Num138 {public Node copyRandomList(Node head) { if(head == null) return null; Node p = head, q; while(p != null) { // copy node q = new Node(p.val); q.random = p.random; q.next = p.next; //插入新节点 p.next = q; p = q.next; } //整理随机指针 p = head.next; while(p != null) {     if(p.random != null)     /*p.random = p.random.next; p = p.next; if(p != null) p = p.next;*/     p.random = p.random == null ? null : p.random.next;     p = p.next == null ? null : p.next.next; }  //拆分链表 p = q = head.next; while(p.next != null) { head.next = head.next.next; p.next = p.next.next; head = head.next; p = p.next; } head.next = null; return q;    }}

任务队列使用场景：

1. CPU的超线程技术

2. 线程池的任务队列

我们先来一些常规的题目来热热身，话不多说，直接上代码

/ * 面试题17.09 第k个数 * @author William * @date 2022-03-05 */public class Num17_09 {//这里用动态规划了public int getKthMagicNumber(int k) {int p3 = 0, p5 = 0, p7 = 0;int[] dp = new int[k];dp[0] = 1;for(int i = 1; i < k; i++) {//选出最小的数字dp[i] = Math.min(dp[p3]*3,Math.min(dp[p5]*5, dp[p7]*7));//将该数字对应的指针向前移动一步if(dp[i] == dp[p3]*3) p3++;if(dp[i] == dp[p5]*5) p5++;if(dp[i] == dp[p7]*7) p7++;}return dp[k-1];    }public static void main(String[] args){ int res = (new Num17_09()).getKthMagicNumber(643); System.out.println(res);    }}/ * 煎饼排序 * @author William * @date 2022-03-06 */public class Num969 {public List pancakeSort(int[] arr) {//初始化List ret = new ArrayList();//从最后一位算起for(int n = arr.length; n > 1; n--) {int index = 0;for(int i = 1; i = arr[index]) {index = i;}}if(index == n - 1) {//如果最大值的位置和当前n的位置一样，就不需要转换了continue;}reverse(arr, index);//将最大值转换到开头位置reverse(arr, n - 1);//将最大值转换到末尾ret.add(index + 1);//增加返回信息ret.add(n);//增加返回信息}return ret;}public void reverse(int[] arr, int end) {for(int i = 0, j = end; i  0 && ten > 0) {five--;ten--;}else if(five >= 3) {five -= 3;}else {return false;}}}return true;    }}/ * 亲密字符串 * @author William * @date 2022-03-05 */public class Num859 {//穷举法 模拟//当 ss 与 goalgoal 长度 或 词频不同，必然不为亲密字符；///当「ss 与 goalgoal 不同的字符数量为 2（能够相互交换）」//或「ss 与 goalgoal 不同的字符数量为 0，//但同时 ss 中有出现数量超过 2 的字符（能够相互交换）」时，//两者必然为亲密字符public boolean buddyStrings(String s, String goal) {int n = s.length(), m = goal.length(); if (n != m) return false; int[] cnt1 = new int[26], cnt2 = new int[26]; int sum = 0; for (int i = 0; i < n; i++) {     int a = s.charAt(i) - 'a', b = goal.charAt(i) - 'a';     cnt1[a]++; cnt2[b]++;     if (a != b) sum++; } boolean ok = false; for (int i = 0; i  1) ok = true; } return sum == 2 || (sum == 0 && ok);    }public boolean buddyStrings1(String s, String goal) {if(s.length() != goal.length()) return false;if(s.equals(goal)) {//字符串完全一样看看有没有重复字符Set set = new HashSet();for(char c : s.toCharArray()) {set.add(c);}//大于代表有重复字符串return s.length() > set.size();}//字符串不一样就只能要求只有两处不一样int first = -1, second = -1;for(int i = 0; i < s.length(); i++) {if(s.charAt(i) != goal.charAt(i)) {if(first == -1) {first = i;}else if(second == -1) {second = i;}else {return false;}}}return second != -1 && s.charAt(first) == goal.charAt(second)&& s.charAt(second) == goal.charAt(first);}}/ * 最近请求次数 * @author William * @date 2022-03-04 */public class Num933 {class RecentCounter {Queue q;    public RecentCounter() {    q = new LinkedList();    } public int ping(int t) {    q.add(t);    while(q.peek() < t - 3000)    q.poll();    return q.size();    }}}/ * 任务调度器 * @author William * @date 2022-03-06 */public class Num621 {public int leastInterval1(char[] tasks, int n) {//贪心算法：先安排出现次数最多的任务，让这个任务两次执行的时间间隔正好为n//再在这个时间间隔内填充其他的任务int[] buckets = new int[26];for(int i= 0; i = 1; i--) {//if(buckets[i] == buckets[i - 1]) //maxCount++;//else//break;//}//改进一下int maxCount = 0;for(int num : buckets) {if(num == maxTimes) maxCount++;}int res = (maxTimes - 1) * (n + 1) + maxCount;return Math.max(res,  tasks.length);//构造//Map freq = new HashMap();////最多的执行次数//int maxExec = 0;//for(char ch : tasks) {//int exec = freq.getOrDefault(ch, 0) + 1;//freq.put(ch, exec);//maxExec = Math.max(maxExec, exec);//}//////具有最多执行次数的任务数量//int maxCount = 0;//Set<Map.Entry> entrySet = freq.entrySet();//for(Map.Entry entry : entrySet) {//int value = entry.getValue();//if(value == maxExec) {//++maxCount;//}//}//return Math.max((maxExec - 1) * (n + 1) + maxCount, tasks.length);}}

再来设计一下双端循环队列，有基于链表和数组实现的两个不同版本

/ * 设计双端循环队列 * @author: William * @time:2022-03-16 */public class Num641 {class MyCircularDeque {class Node{int val;Node pre;Node next;public Node(int val) {this.val = val;this.pre = null;this.next = null;}}int count, max;Node head, tail;    public MyCircularDeque(int k) {    count = 0;    max = k;    } public boolean insertFront(int value) {    if(isFull()) return false;    Node node = new Node(value);    if(isEmpty()) {    head = tail = node;    }else {    node.next = head;    head.pre = node;    head = head.pre;    }    count++;    return true;    } public boolean insertLast(int value) {    if(isFull()) return false;    Node node = new Node(value);    if(isEmpty()) {    head = tail = node;    }else {    tail.next = node;    node.pre = tail;    tail = tail.next;    }    count++;    return true;    } public boolean deleteFront() {    if(isFull()) return false;    head = head.next;    count--;    return true;    } public boolean deleteLast() {    if(isFull()) return false;    tail = tail.pre;    count--;    return true;    } public int getFront() {    if(isEmpty()) return -1;    return head.val;    } public int getRear() {    if(isEmpty()) return -1;    return tail.val;    } public boolean isEmpty() {    return count == 0;    } public boolean isFull() {    return count == max;    }}//数组实现class MyCircularDeque2 {//核心思想//前移：(下标-1+k) % k   后移：(下标+1) % kint[] queue;int front, rear;int max, count;public MyCircularDeque2(int k) {queue = new int[k];front = 0;rear = 0;max = k;count = 0;    } public boolean insertFront(int value) {    if(isFull()) return false;    front = (front - 1 + max) % max;    queue[front] = value;    count++;    return true;    } public boolean insertLast(int value) {    if(isFull()) return false;    queue[rear] = value;    rear++;    rear %= max;    count++;    return true;    } public boolean deleteFront() {    if(isEmpty()) return false;    front++;    front %= max;    count--;    return true;    } public boolean deleteLast() {    if(isEmpty()) return false;    rear = (rear - 1 + max) % max;    count--;    return true;    } public int getFront() {    if(isEmpty()) return -1;    return queue[front];    } public int getRear() {    if(isEmpty()) return -1;    return queue[(rear - 1 + max) % max];    } public boolean isEmpty() {    return count == 0;    } public boolean isFull() {    return count == max;    }}public class MyCircularDeque3 {    // 1、不用设计成动态数组，使用静态数组即可    // 2、设计 head 和 tail 指针变量    // 3、head == tail 成立的时候表示队列为空    // 4、tail + 1 == head    private int capacity;    private int[] arr;    private int front;    private int rear;    /     * Initialize your data structure here. Set the size of the deque to be k.     */    public MyCircularDeque3(int k) { capacity = k + 1; arr = new int[capacity]; // 头部指向第 1 个存放元素的位置 // 插入时，先减，再赋值 // 删除时，索引 +1（注意取模） front = 0; // 尾部指向下一个插入元素的位置 // 插入时，先赋值，再加 // 删除时，索引 -1（注意取模） rear = 0;    }    /     * Adds an item at the front of Deque. Return true if the operation is successful.     */    public boolean insertFront(int value) { if (isFull()) {     return false; } front = (front - 1 + capacity) % capacity; arr[front] = value; return true;    }    /     * Adds an item at the rear of Deque. Return true if the operation is successful.     */    public boolean insertLast(int value) { if (isFull()) {     return false; } arr[rear] = value; rear = (rear + 1) % capacity; return true;    }    /     * Deletes an item from the front of Deque. Return true if the operation is successful.     */    public boolean deleteFront() { if (isEmpty()) {     return false; } // front 被设计在数组的开头，所以是 +1 front = (front + 1) % capacity; return true;    }    /     * Deletes an item from the rear of Deque. Return true if the operation is successful.     */    public boolean deleteLast() { if (isEmpty()) {     return false; } // rear 被设计在数组的末尾，所以是 -1 rear = (rear - 1 + capacity) % capacity; return true;    }    /     * Get the front item from the deque.     */    public int getFront() { if (isEmpty()) {     return -1; } return arr[front];    }    /     * Get the last item from the deque.     */    public int getRear() { if (isEmpty()) {     return -1; } // 当 rear 为 0 时防止数组越界 return arr[(rear - 1 + capacity) % capacity];    }    /     * Checks whether the circular deque is empty or not.     */    public boolean isEmpty() { return front == rear;    }    /     * Checks whether the circular deque is full or not.     */    public boolean isFull() { // 注意：这个设计是非常经典的做法 return (rear + 1) % capacity == front;    }}}

最后再来一个甜点，相信大家了解双端循环队列的设计之后，再来设计循环队列肯定就已经信手拈来了

/ * 设计循环队列 * @author William * @date 2022-03-04 */public class Num622 {class MyCircularQueue {//front -> 队首  rear -> 队尾下一位置int[] queue;    int front, rear;    int max, count; public MyCircularQueue(int k) {    queue = new int[k];    front = 0;    rear = 0;    max = k;    count = 0;    } public boolean enQueue(int value) {    if(isFull()) return false;    queue[rear] = value;    rear++;    rear %= max;    count++;    return true;    } public boolean deQueue() {    if(isEmpty()) return false;    front++;    front %= max;    count--;    return true;    } public int Front() {    if(isEmpty()) return -1;    return queue[front];    } public int Rear() {    if(isEmpty()) return -1;    return queue[(rear - 1 + max) % max];    } public boolean isEmpty() {    return count == 0;    } public boolean isFull() {    return count == max;    }}class MyCircularQueue1 {class Node {int val;Node next;public Node(int val) {this.val = val;this.next = null;}}Node front, rear;int count, max;    public MyCircularQueue1(int k) {    count = 0;    max = k;    } public boolean enQueue(int value) {    if(isFull()) return false;    Node node = new Node(value);    if(count == 0) {    front = rear = node;    }else {    rear.next = node;    rear = rear.next;    }    count++;    return true;    } public boolean deQueue() {    if(isEmpty()) return false;    count--;    front = front.next;    return true;    } public int Front() {    if(isEmpty()) return -1;    return front.val;    } public int Rear() {    if(isEmpty()) return -1;    return rear.val;    } public boolean isEmpty() {    return count == 0;    } public boolean isFull() {    return count == max;    }}}

相信大家经过这些学习对线程池与任务队列这方面的算法题会有更加深刻的理解，这其中应该再重点掌握以下循环队列的实现，其中的构造思想非常重要，自己设计好之后也可以去jdk官方源码看看，看看自己写的和大神写的有哪些区别，从而找到自己的不足之处，在自己的代码里面考虑更多的情况，注意一些常用的指针移动方式，再好好修改自己写的代码，相信这样之后我们也离大佬的距离又近了一步。