1. 認(rèn)識(shí)隊(duì)列結(jié)構(gòu)

隊(duì)列是一個(gè) 先進(jìn)先出（FIFO） 的數(shù)據(jù)結(jié)構(gòu)

js 中沒(méi)有隊(duì)列，但我們可以用 數(shù)組或鏈表 實(shí)現(xiàn)隊(duì)列的所有功能

隊(duì)列的常用操作:

enqueue(element)：向隊(duì)列尾部添加一個(gè)（多個(gè)）新的項(xiàng)

dequeue()：移除隊(duì)列的第一項(xiàng)，并返回被移除的元素

front/peek()：返回隊(duì)列中的第一個(gè)元素

isEmpty()：判斷隊(duì)列是否為空

size()：返回隊(duì)列的元素個(gè)數(shù)

隊(duì)列的結(jié)構(gòu)示意圖：

2. 實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)封裝

隊(duì)列的實(shí)現(xiàn)和棧一樣也有兩種實(shí)現(xiàn)方式：

• 基于 數(shù)組 實(shí)現(xiàn)
• 基于 鏈表 實(shí)現(xiàn)

鏈表也是一種數(shù)據(jù)結(jié)構(gòu)，js 中沒(méi)有自帶鏈表結(jié)構(gòu)，后續(xù)會(huì)寫關(guān)于鏈表的文章，本章先使用數(shù)組來(lái)實(shí)現(xiàn)。

實(shí)現(xiàn)：

// 封裝一個(gè)隊(duì)列
export default class ArrayQueue<T = any> {
  private data: T[] = [];
  constructor(data: T[]) {
    this.data = data || [];
  }
  enqueue(element: T): void {
    this.data.push(element);
  }
  dequeue(): T | undefined {
    return this.data.shift();
  }
  peek(): T | undefined {
    return this.data[0];
  }
  isEmpty(): boolean {
    return this.data.length === 0;
  }
  size(): number {
    return this.data.length;
  }
}

測(cè)試：

const queue = new ArrayQueue<number>();
queue.push(1);
queue.push(2);
queue.pop();
queue.push(3);
console.log(queue); // ArrayQueue { data: [ 2, 3 ] }

3. 實(shí)戰(zhàn)一：最近的請(qǐng)求次數(shù)

這是 Leetcode 上的第 933 道題，難度為 簡(jiǎn)單

3.1 題目描述

寫一個(gè) RecentCounter 類來(lái)計(jì)算特定時(shí)間范圍內(nèi)最近的請(qǐng)求。

請(qǐng)你實(shí)現(xiàn) RecentCounter 類：

• RecentCounter() 初始化計(jì)數(shù)器，請(qǐng)求數(shù)為 0 。
• int ping(int t) 在時(shí)間 t 添加一個(gè)新請(qǐng)求，其中 t 表示以毫秒為單位的某個(gè)時(shí)間，并返回過(guò)去 3000 毫秒內(nèi)發(fā)生的所有請(qǐng)求數(shù)（包括新請(qǐng)求）。確切地說(shuō)，返回在 [t-3000, t] 內(nèi)發(fā)生的請(qǐng)求數(shù)。

保證 每次對(duì) ping 的調(diào)用都使用比之前更大的 t 值。

示例 1：

輸入：
["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
• 保證每次對(duì) ping 調(diào)用所使用的 t 值都 嚴(yán)格遞增
• 至多調(diào)用 ping 方法 104 次

3.2 解一：隊(duì)列

思路：

我們可以用一個(gè)隊(duì)列維護(hù)發(fā)生請(qǐng)求的時(shí)間，當(dāng)在時(shí)間 t 收到請(qǐng)求時(shí)，將時(shí)間 t 入隊(duì)。 保證隊(duì)列的 尾部值 減去隊(duì)列的 首部值 小于等于 3000，隊(duì)列中的元素?cái)?shù)量即為 最近的請(qǐng)求次數(shù)

代碼：

class RecentCounter {
  queue: ArrayQueue<number>;
  constructor() {
    this.queue = new ArrayQueue<number>();
  }
  ping(t: number): number {
    this.queue.enqueue(t);
    while (this.queue.peek() < t - 3000) {
      this.queue.dequeue();
    }
    return this.queue.size();
  }
}
/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

復(fù)雜度分析：

時(shí)間復(fù)雜度：均攤 O(1)，每個(gè)元素至多入隊(duì)出隊(duì)各一次。

空間復(fù)雜度：O(L)，其中 L 為隊(duì)列的最大元素個(gè)數(shù)。

4. 實(shí)戰(zhàn)二：無(wú)法吃午餐的學(xué)生數(shù)量

這是 Leetcode 上的第 1700 道題，難度為 簡(jiǎn)單

4.1 題目描述

學(xué)校的自助午餐提供圓形和方形的三明治，分別用數(shù)字 0 和 1 表示。所有學(xué)生站在一個(gè)隊(duì)列里，每個(gè)學(xué)生要么喜歡圓形的要么喜歡方形的。
餐廳里三明治的數(shù)量與學(xué)生的數(shù)量相同。所有三明治都放在一個(gè) 棧 里，每一輪：

• 如果隊(duì)列最前面的學(xué)生 喜歡 棧頂?shù)娜髦?，那么?huì) 拿走它 并離開(kāi)隊(duì)列。
• 否則，這名學(xué)生會(huì) 放棄這個(gè)三明治 并回到隊(duì)列的尾部。

這個(gè)過(guò)程會(huì)一直持續(xù)到隊(duì)列里所有學(xué)生都不喜歡棧頂?shù)娜髦螢橹埂?/p>

給你兩個(gè)整數(shù)數(shù)組 students 和 sandwiches ，其中 sandwiches[i] 是棧里面第 i?????? 個(gè)三明治的類型（i = 0 是棧的頂部）， students[j] 是初始隊(duì)列里第 j?????? 名學(xué)生對(duì)三明治的喜好（j = 0 是隊(duì)列的最開(kāi)始位置）。請(qǐng)你返回?zé)o法吃午餐的學(xué)生數(shù)量。

示例 1：

輸入： students = [1,1,0,0], sandwiches = [0,1,0,1]
輸出： 0 解釋：
- 最前面的學(xué)生放棄最頂上的三明治，并回到隊(duì)列的末尾，學(xué)生隊(duì)列變?yōu)?students = [1,0,0,1]。
- 最前面的學(xué)生放棄最頂上的三明治，并回到隊(duì)列的末尾，學(xué)生隊(duì)列變?yōu)?students = [0,0,1,1]。
- 最前面的學(xué)生拿走最頂上的三明治，剩余學(xué)生隊(duì)列為 students = [0,1,1]，三明治棧為 sandwiches = [1,0,1]。
- 最前面的學(xué)生放棄最頂上的三明治，并回到隊(duì)列的末尾，學(xué)生隊(duì)列變?yōu)?students = [1,1,0]。
- 最前面的學(xué)生拿走最頂上的三明治，剩余學(xué)生隊(duì)列為 students = [1,0]，三明治棧為 sandwiches = [0,1]。
- 最前面的學(xué)生放棄最頂上的三明治，并回到隊(duì)列的末尾，學(xué)生隊(duì)列變?yōu)?students = [0,1]。
- 最前面的學(xué)生拿走最頂上的三明治，剩余學(xué)生隊(duì)列為 students = [1]，三明治棧為 sandwiches = [1]。
- 最前面的學(xué)生拿走最頂上的三明治，剩余學(xué)生隊(duì)列為 students = []，三明治棧為 sandwiches = []。
所以所有學(xué)生都有三明治吃。

示例 2：

輸入： students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
輸出： 3

提示：

• 1 <= students.length, sandwiches.length <= 100
• students.length == sandwiches.length
• sandwiches[i] 要么是 0 ，要么是 1 。
• students[i] 要么是 0 ，要么是 1 。

4.2 解一：隊(duì)列

思路： 我們可以維護(hù)兩個(gè)隊(duì)列，一個(gè)是學(xué)生隊(duì)列，一個(gè)是三明治隊(duì)列。

循環(huán)比較 學(xué)生隊(duì)列 和 三明治隊(duì)列 的 頭部第一個(gè)元素，如果相同則都 移除 它們，如果不相同則將學(xué)生隊(duì)列的頭部元素移到尾部，直到碰到下一組相同的兩個(gè)頭部元素 或者 學(xué)生隊(duì)列所有學(xué)生都不喜歡三明治隊(duì)列的第一個(gè)三明治。

代碼：

function countStudents(students: number[], sandwiches: number[]): number {
  const studentsQueue = new ArrayQueue<number>(students);
  const sandwichesQueue = new ArrayQueue<number>(sandwiches);
  let count = 0;
  while (studentsQueue.size()) {
    if (studentsQueue.peek() === sandwichesQueue.peek()) {
      studentsQueue.dequeue();
      sandwichesQueue.dequeue();
      count = 0;
    } else {
      studentsQueue.enqueue(studentsQueue.dequeue()!);
      count++;
    }
    if (count === studentsQueue.size()) return sandwichesQueue.size();
  }
  return 0;
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中 n 是學(xué)生的數(shù)量。
• 空間復(fù)雜度：O(1)。

5. 實(shí)戰(zhàn)三：字符串中的第一個(gè)唯一字符

這是 Leetcode 上的第 387 道題，難度為 簡(jiǎn)單

5.1 題目描述

給定一個(gè)字符串 s ，找到 它的第一個(gè)不重復(fù)的字符，并返回它的索引 。如果不存在，則返回 -1 。

示例 1：

輸入: s = "leetcode"
輸出: 0

示例 2:

輸入: s = "loveleetcode"
輸出: 2

示例 3:

輸入: s = "aabb"
輸出: -1

提示:

• 1 <= s.length <= 105
• s 只包含小寫字母

5.2 解一：哈希表

思路：

維護(hù)一個(gè) map，分兩次遍歷字符串

• 第一次遍歷存儲(chǔ)每個(gè)字符對(duì)應(yīng)的出現(xiàn)次數(shù)
• 第二次遍歷取出第一個(gè)只出現(xiàn)第一次的字符

代碼：

function firstUniqChar(s: string): number {
  const map = new Map<string, number>();
  for (let i = 0; i < s.length; i++) {
    let n = map.get(s[i]);
    n ? map.set(s[i], n + 1) : map.set(s[i], 1);
  }
  for (let i = 0; i < s.length; i++) {
    if (map.get(s[i]) === 1) return i;
  }
  return -1;
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(∣Σ∣)，其中 Σ 是字符集，在本題中 s 只包含小寫字母，因此 ∣Σ∣≤26 。我們需要 O(∣Σ∣) 的空間存儲(chǔ)哈希映射。

5.3 解二：隊(duì)列

思路：

維護(hù)一個(gè)隊(duì)列，按照順序存儲(chǔ)每一個(gè)字符以及它們第一次出現(xiàn)的位置。當(dāng)我們對(duì)字符串進(jìn)行遍歷時(shí)，設(shè)當(dāng)前遍歷到的字符為 c，如果 c 不在哈希映射中，我們就將 c 與它的索引作為一個(gè)二元組放入隊(duì)尾，否則我們就需要檢查隊(duì)列中的元素是否都滿足「只出現(xiàn)一次 的要求，即我們不斷地根據(jù)哈希映射中存儲(chǔ)的值（是否為 −1）選擇彈出隊(duì)首的元素，直到隊(duì)首元素 「真的」 只出現(xiàn)了一次或者隊(duì)列為空。

在遍歷完成后，如果隊(duì)列為空，說(shuō)明沒(méi)有不重復(fù)的字符，返回 −1，否則隊(duì)首的元素即為第一個(gè)不重復(fù)的字符以及其索引的二元組

代碼：

function firstUniqChar(s: string): number {
  const map = new Map<string, number>();
  const queue = new ArrayQueue<[string, number]>();
  for (let i = 0; i < s.length; i++) {
    if(!map.has(s[i])) {
      map.set(s[i], i)
      queue.enqueue([s[i], i]);
    } else {
      map.set(s[i], -1)
      while(queue.size() && map.get((queue.peek() as [string,number])[0]) === -1) {
        queue.dequeue()
      }
    }
  }
  return queue.size() ? (queue.peek() as [string, number])[1] : -1;
}

復(fù)雜度分析:

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(∣Σ∣)

以上就是TypeScript數(shù)據(jù)結(jié)構(gòu)之隊(duì)列結(jié)構(gòu)Queue教程示例的詳細(xì)內(nèi)容，更多關(guān)于TypeScript 隊(duì)列結(jié)構(gòu)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論