简介

队列的性质：先进先出

队列的相关操作：
出队：从队首出队，头指针向后移动一位
入队：队尾入队，尾指针向后移动一位，并放入元素

队列相关的几个概念：
长度
尺寸
头指针
尾指针

普通队列

普通队列的简单实现

  1. function Queue(n) {
  2.     this.queue = new Array(n);
  3.     this.head = 0;
  4.     this.tail = 0;
  5. }
  7. Queue.prototype = {
  8.     ...Queue.prototype,
  9.     enqueue(val) {
  10.         if (this.full()) return;
  11.         this.queue[this.tail] = val;
  12.         this.tail += 1;
  13.     },
  14.     dequeue() {
  15.         if (this.empty()) return;
  16.         const res = this.queue[this.head];
  17.         this.head += 1;
  18.         return res;
  19.     },
  20.     front() {
  21.         if (this.empty()) return;
  22.         return this.queue[this.head]
  23.     },
  24.     full() {
  25.         return this.tail === this.queue.length;
  26.     },
  27.     empty() {
  28.         return this.head === this.tail;
  29.     },
  30.     size() {
  31.         return this.tail - this.head
  32.     },
  33.     output() {}
  34. };

循环队列

  1. function Queue(n) {
  2.     this.queue = new Array(n);
  3.     this.head = 0;
  4.     this.tail = 0;
  5.     this.size = 0;
  6. }
  8. Queue.prototype = {
  9.     ...Queue.prototype,
  10.     enqueue(val) {
  11.         if (this.isFull()) return;
  12.         this.queue[this.tail] = val;
  13.         this.tail++;
  14.         this.tail %= this.queue.length;
  15.         this.size++;
  16.     },
  17.     dequeue() {
  18.         if (this.isEmpty()) return;
  19.         const res = this.queue[this.head];
  20.         this.head++;
  21.         this.head %= this.queue.length;
  22.         this.size--;
  23.     },
  24.     front() {
  25.         return this.queue[this.head];
  26.     },
  27.     isEmpty() {
  28.         return this.size === 0;
  29.     },
  30.     isFull() {
  31.         return this.size === this.queue.length;
  32.     },
  33.     output() {
  34.         let temp = [];
  35.         for (let i = 0, j = this.head; i < this.size; i++) {
  36.             temp.push(this.queue[j]);
  37.             j++;
  38.             if (j === this.queue.length) j = 0;
  39.         }
  40.         return temp;
  41.     }
  42. };
  44. function test(opts, vals) {
  45.     let queue = new Queue(5);
  47.     for (let i = 0; i < opts.length; i++) {
  48.         switch (opts[i]) {
  49.             case 'insert':
  50.                 queue.enqueue(vals[i]);
  51.                 break;
  52.             case 'front':
  53.                 console.log(`front element: ${queue.front()}`);
  54.                 break;
  55.             case 'dequeue':
  56.                 queue.dequeue();
  57.                 break;
  58.             case 'size':
  59.                 console.log(`queue size: ${queue.size()}`);
  60.                 break;
  61.             default:
  62.                 break;
  63.         }
  64.         console.log(queue.output());
  65.     }
  66. }
  68. let opts = ['insert', 'insert', 'insert', 'dequeue', 'insert', 'insert', 'dequeue', 'insert', 'insert'];
  69. let vals = [1, 2, 3, '', 4, 5, '', 6, 7]
  70. test(opts, vals)

双端队列

分享课练习题

641.设计双端队列

设计实现双端队列。
你的实现需要支持以下操作：

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



提示：

所有值的范围为 [1, 1000]
操作次数的范围为 [1, 1000]
请不要使用内置的双端队列库。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-circular-deque
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number} k
 */
var MyCircularDeque = function (k) {
    this.queue = new Array(k);
    this.len = k;
    this.count = 0;
    this.head = 0;
    this.tail = 1;
};

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertFront = function (value) {
    if (this.isFull()) return false;
    this.queue[this.head] = value;
    this.head = (this.head - 1 + this.len) % this.len;
    this.count++;
    return true;
};

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertLast = function (value) {
    if (this.isFull()) return false;
    this.queue[this.tail] = value;
    this.tail = (this.tail + 1) % this.len;
    this.count++;
    return true;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function () {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.len;
    this.count--;
    return true;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function () {
    if (this.isEmpty()) return false;
    this.tail = (this.tail - 1 + this.len) % this.len;
    this.count--;
    return true;
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getFront = function () {
    if (this.isEmpty()) return -1;
    return this.queue[(this.head + 1) % this.len]
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getRear = function () {
    if (this.isEmpty()) return - 1;
    return this.queue[(this.tail - 1 + this.len) % this.len]
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isEmpty = function () {
    return this.count === 0;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isFull = function () {
    return this.count === this.len;
};

933.最近请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。



示例：

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3


提示：

1 <= t <= 109
保证每次对 ping 调用所使用的 t 值都 严格递增
至多调用 ping 方法 104 次

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-recent-calls
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：

var RecentCounter = function() {
    this.queue = [];
};

RecentCounter.prototype.ping = function(t) {
    this.queue.push(t);
  // 注意 while 循环不能改成 if 因为可能出现连续要删除的项，改成 if 只能删除一项
  while (this.queue[0] < t - 3000) {
      this.queue.shift();
  }
    return this.queue.length;
};

方法二：

var RecentCounter = function() {
    this.queue = [];
  this.index = 0;
};

RecentCounter.prototype.ping = function(t) {
    this.queue.push(t);
  while (t - this.queue[this.index] > 3000) {
      this.index++;
  }
    return this.queue.length - this.index;
};

859.亲密字符串

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。


示例 1：

输入：s = "ab", goal = "ba"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。
示例 2：

输入：s = "ab", goal = "ab"
输出：false
解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。
示例 3：

输入：s = "aa", goal = "aa"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。
示例 4：

输入：s = "aaaaaaabc", goal = "aaaaaaacb"
输出：true


提示：

1 <= s.length, goal.length <= 2 * 104
s 和 goal 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/buddy-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var buddyStrings = function (s, goal) {
    const len = s.length;
    if (len !== goal.length) return false;
    if (s === goal) return len > new Set(s).size;
    const temp = [];
    for (let i = 0; i < len; i++) {
        if (s[i] !== goal[i]) {
            temp.push(s[i], goal[i]);
        }
    }
    return (temp.length === 4) && (temp[0] === temp[3]) && (temp[1] === temp[2]);
};

86.分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。



示例 1：


输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：

输入：head = [2,1], x = 2
输出：[1,2]


提示：

链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var partition = function(head, x) {
    const smallList = new ListNode(null);
  const largeList = new ListNode(null);
    let small = smallList, large = largeList;
  while (head) {
    if (head.val < x) {
        small.next = head;
        small = small.next;
    }else {
        large.next = head;
      large = large.next;
    }
    head = head.next;
  }
  large.next = null;
  smallList.next = largeList;
  return smallList.next;
}

622.设计循环队列

860.柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。



示例 1：

输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：

输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
示例 3：

输入：bills = [5,5,10]
输出：true
示例 4：

输入：bills = [10,10]
输出：false


提示：

1 <= bills.length <= 105
bills[i] 不是 5 就是 10 或是 20 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lemonade-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[]} bills
 * @return {boolean}
 */
var lemonadeChange = function (bills) {
  const money = {
    5: 0,
    10: 0
  };

  for (let i = 0, len = bills.length; i < len; i++) {
    let it = bills[i];
    switch (it) {
      case 5:
        money[5]++;
        break;
      case 10:
        if (money[5] < 1) return false;
        money[5]--;
        money[10]++;
        break;
      case 20:
        if (money[10]) {
          if (!money[5]) return false;
          money[5]--;
          money[10]--;
        }else {
          if (money[5] < 3) return false;
          money[5] -= 3;
        }
        break;
    }
  }
  return true;
};

969.煎饼排序

给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。

一次煎饼翻转的执行过程如下：

选择一个整数 k ，1 <= k <= arr.length
反转子数组 arr[0...k-1]（下标从 0 开始）
例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。

以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。



示例 1：

输入：[3,2,4,1]
输出：[4,2,4,3]
解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 arr = [3, 2, 4, 1]
第一次翻转后（k = 4）：arr = [1, 4, 2, 3]
第二次翻转后（k = 2）：arr = [4, 1, 2, 3]
第三次翻转后（k = 4）：arr = [3, 2, 1, 4]
第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。 
示例 2：

输入：[1,2,3]
输出：[]
解释：
输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如 [3，3] ，也将被判断为正确。


提示：

1 <= arr.length <= 100
1 <= arr[i] <= arr.length
arr 中的所有整数互不相同（即，arr 是从 1 到 arr.length 整数的一个排列）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pancake-sorting
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var pancakeSort = function(arr) {
    const res = [];
    reverse(arr, res);
    return res;    
};

function reverse(arr, res) {
    const len = arr.length;
    let arr1 = [];
    if (len === 1) return;
    for (let i = 0; i < len; i++) {
        if (arr[i] === len) {
            res.push(i + 1);
            arr1 = arr.slice(0, i).reverse().concat(arr.slice(i + 1));
        }
    }
    res.push(len);
    reverse(arr1.reverse(), res);
}

小册练习题

其他练习题

199.二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。



示例 1:



输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:

输入: [1,null,3]
输出: [1,3]
示例 3:

输入: []
输出: []


提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100 


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。