為什麼需要 Queue

在事件驅動中，事件會依照發生順序進入「事件佇列」（Event Queue）：

• 先進先處理
  保證滑鼠點擊、鍵盤輸入、網路封包等事件能按照產生的時間順序處理，避免亂序導致邏輯錯亂。

• 緩衝（Buffer）功能
  當事件產生速度 > 處理速度時，Queue 可暫存事件避免遺漏，像leetcode 933. Number of Recent Calls保留3000ms的資訊。

• 解耦產生者與消費者
  事件的產生與處理分開進行，Queue 充當中間橋樑。

照慣例刷個幾題練習

leetcode 346. Moving Average from Data Stream

題目：設計一個計算n個區間的移動平均，MovingAverage為新創立一個大小為n的移動平均佇列，next為插入值並回傳目前平均值

輸入：["MovingAverage", "next", "next", "next", "next"]，[[3], [1], [10], [3], [5]]

輸出：[null, 1.0, 5.5, 4.66667, 6.0]

限制：

• 1 <= size <= 1000

• -10^5 <= val <= 10^5

• At most 10^4 calls will be made to next.

做法：與leetcode 622. Design Circular Queue很像

1. 在結構定義分別記錄目前佇列大小、容量限制、佇列存值、現在的總和

2. 當佇列大小<n時只要(前次總和+目前的值)/目前佇列大小即可得到答案

3. 當佇列滿了先把最前面的值移出佇列，再把目前的值加進來取平均即可。

use std::collections::VecDeque;

struct MovingAverage {
    size:i32,
    capacity:i32,
    queue:VecDeque<i32>,
    sum:f64
}

impl MovingAverage {
    fn new(size: i32) -> Self {
        Self {
            size:0,
            capacity:size,
            queue:VecDeque::with_capacity(size as usize),
            sum:0.0
        }
    }
    
    fn next(&mut self, val: i32) -> f64 {
        if(self.size<self.capacity){
            self.queue.push_back(val);
            self.size +=1;
            self.sum += val as f64;
            return self.sum / self.size as f64
        } else {
            let Some(front) = self.queue.pop_front() else {todo!()};
            self.queue.push_back(val);
            self.sum =self.sum - front as f64+ val as f64;
            return  self.sum / self.size as f64
        }
    }
}

Leetcode 649. Dota2 Senate

題目：給一個兩黨議員排隊投票順序，每個議員可以做兩件事1. 禁止某一位議員的權力 2.當剩下的議員都是自己黨的宣布勝利

輸入：senate = "RD"

輸出："Radiant"

限制：

• n == senate.length

• 1 <= n <= 10^4

• senate[i] is either 'R' or 'D'.

解法：這裡獲勝的解法是每位行使權力的議員去禁止對立政黨的第一位議員，讓對立政黨能行使權力的人越來越少，因此我們需要知道兩黨每位議員的先後順序並依照這順序來行使權力，可以佇列先進先出。

1. 用兩個佇列來存兩黨議員員順序

2. 分別dequeue兩個佇列，找出兩黨第一個行使權力的議員

3. 禁止對方第一個議員權利或是發現對方沒人了宣布勝利

4. 行使權力的議員到最後面排隊繼續下一輪

5. 重複2-4直到某一方宣布勝利

use std::collections::VecDeque;

impl Solution {
    pub fn predict_party_victory(senate: String) -> String {
        //front senate can ban behind senator,use two queue store 2 parties senates idx
        //chose the first position one's party ban the first one in the other party,and enqueue to with last position
        //example sentate="RD" [0] is R queue, [1] is D queue
        // first choose 0 ban 1,and add position 2 to Rqueue
        // if one of two queues is empty , the other party win

        let mut r_queue = VecDeque::new();
        let mut d_queue = VecDeque::new();       
        let mut position = senate.len();

        for (idx,c) in senate.char_indices() {
            if(c=='R'){
                r_queue.push_back(idx);
            } else {
                d_queue.push_back(idx);
            }
        }
        loop {
            let Some(r_front) = r_queue.pop_front() else    {   return String::from("Dire") };
            let Some(d_front) = d_queue.pop_front() else    {   return String::from("Radiant")  };
            position+=1;

            if(r_front<d_front){
                r_queue.push_back(position);
            } else {
                d_queue.push_back(position);
            }

        }
    }
}

Day14 總結

1. Event Queue特性與實作