佇列Queue介紹

如圖所示佇列(Queue)是先進先出(First in First Out的資料結構，主要操作有進入佇列enqueue，離開佇列dequeue。

優點

1. 自然模擬現實中排隊、分批處理需求
2. 確保任務、資源處理的公平性，不會「插隊」

限制

1. 只能操作前端端元素(雙邊佇列可操作前後端)，不能直接存取中間資料

在Rust中我們用VecDeque雙邊佇列結構解題

資料來源:https://doc.rust-lang.org/std/collections/struct.VecDeque.html

用法

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque<i32> = VecDeque::new();

    // 從尾端加入元素 (enqueue)
    queue.push_back(1);
    queue.push_back(3001);

    // 從頭端移除元素 (dequeue)
    if let Some(front) = queue.pop_front() {
        println!("Dequeued: {}", front); // Dequeued: 1
    }

    // 從尾端移除元素
    if let Some(back) = queue.pop_back() {
        println!("Popped from back: {}", back); // Popped from back: 3001
    }

    // 從頭端加入元素
    queue.push_front(3002); 

    // 查看目前頭端和尾端元素
    if let Some(&front) = queue.front() {
        println!("Front: {}", front); //Front: 3002
    }
    if let Some(&back) = queue.back() {
        println!("Back: {}", back); //Back: 3002
    }

    // 佇列長度
    println!("Queue size: {}", queue.len()); //Queue size: 1
}

Queue常見的用途

1. 任務排程、資源管理

2. 廣度優先搜尋BFS(Broad First Search)

3. 事件處理

4. 緩衝處理

任務排程、資源管理

leetcode 933. Number of Recent Calls

題目：你要設計個RecentCounter來記錄收到的請求並保留特定時間區間內的請求資料，RecentCounter有兩個方法(method)

1. RecentCounter：建立一個新計數器
2. int ping(int t)：代表在t ms時有人發請求，並回傳3000ms內[t-3000,t]的請求總數

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

• 1 <= t <= 109
• Each test case will call ping with strictly increasing values of t.
• At most 10^4 calls will be made to ping.

解法：主要目標是寫出一個3000ms內請求記錄總數，我們可以用queue資料結構來記錄3000ms內的請求，每當收到ping時就去刪掉300ms前的請求數量並回傳目前有多少個請求被記錄在queue。

use std::collections::VecDeque;

struct RecentCounter {
    queue:VecDeque<i32>
}

impl RecentCounter {

    fn new() -> Self {
        Self {
            queue: VecDeque::new()
        }
    }
    
    fn ping(&mut self, t: i32) -> i32 {
        self.queue.push_back(t);
        while let Some(&time) = self.queue.front() {
            if t-time>3000 {
                self.queue.pop_front();
            } else {
                break
            }
        }
        return self.queue.len() as i32
    }
}

leetcode 622. Design Circular Queue

題目：設計一個circle queue,queue 使用陣列時，當你一直 dequeue，front 往右移，左邊的空間無法再利用 —— 雖然陣列還沒滿，但無法再插入元素， circular queue 解決這個問題，讓空間能循環使用。

輸入：["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"] [[3], [1], [2], [3], [4], [], [], [], [4], []]

輸出：[null, true, true, true, false, 3, true, true, true, 4]
限制：

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

解法1：VecDeque就是會自動擴容的環狀佇列，只要把佇列大小固定就可以跟這題要實作的吻合。

use std::collections::VecDeque;

struct MyCircularQueue {
    queue:VecDeque<i32>,
    max_size:usize
}

impl MyCircularQueue {

    fn new(k: i32) -> Self {
       Self {
        queue:VecDeque::with_capacity(k as usize),
        max_size:k as usize
       }
    }
    
    fn en_queue(&mut self, value: i32) -> bool {
        if(self.queue.len()<self.max_size){
            self.queue.push_back(value);
            return true
        }
        return false
    }
    
    fn de_queue(&mut self) -> bool {
        if (!self.queue.is_empty()){
            self.queue.pop_front();
            return true
        }
        return false
    }
    
    fn front(&mut self) -> i32 {
        if let Some(&front) = self.queue.front() {
            return front
        } else {
            return -1
        }
    }
    
    fn rear(&mut self) -> i32 {
        if let Some(&rear) = self.queue.back() {
            return rear
        } else {
            return -1
        }
    }
    
    fn is_empty(&self) -> bool {
        return self.queue.is_empty()
    }
    
    fn is_full(&self) -> bool {
        return self.queue.len() == self.max_size
    }
}

解法2：使用陣列來實作circle queue，根據限制1 <= k <= 1000所以將陣列最大值設為1000，並需要有front、rear、size、capacity分別記錄最前面位置、最後面位置、目前大小、queue最大能用多少。

1. MyCircularQueue.new() →創建一個最大能存k個Some<i32>的新實例
2. MyCircularQueue.en_queue(value)→如果還有空間就把value加入佇列，rear往後一格，如果繞一圈但前面有空位就往前移(self.rear = (self.rear+1)%self.capacity)，成功就回傳true
3. MyCircularQueue.dequeue()→如果還有值就把值移出佇列，並把front指到目前最先進來的位置
4. MyCircularQueue.front()→找出目前最早進到佇列的值也就是front指的位置的值
5. MyCircularQueue.rear()→找出目前最晚進到佇列的值也就是rear指的位置前一格的值，如果目前剛好指到0最後一個位置就是k-1。

const MAX_SIZE:usize = 1000; 
struct MyCircularQueue {
    queue:[Option<i32>;MAX_SIZE],
    front:usize,
    rear:usize,
    size:usize,
    capacity:usize,
}

impl MyCircularQueue {

    fn new(k: i32) -> Self {
        Self {
            queue:[None;MAX_SIZE],
            front:0,
            rear:0,
            size:0,
            capacity:k as usize,
        }
    }
    
    fn en_queue(&mut self, value: i32) -> bool {
        if(self.is_full()){
            return false
        }
        self.queue[self.rear] = Some(value);
        self.rear = (self.rear+1)%self.capacity;
        self.size +=1;
        return true;
    }
    
    fn de_queue(&mut self) -> bool {
         if(self.is_empty()){
            return false
        }
        self.queue[self.front] = None;
        self.front = (self.front+1)%self.capacity;
        self.size -=1;
        return true
    }
    
    fn front(&self) -> i32 {
        if(self.is_empty()){
            return -1
        }
        return self.queue[self.front].unwrap();
    }
    
    fn rear(&self) -> i32 {
        if(self.is_empty()){
            return -1
        }
        let rear_idx = if self.rear==0 {
            self.capacity-1
        } else {
            self.rear-1
        };
        return self.queue[rear_idx].unwrap();
    }
    
    fn is_empty(&self) -> bool {
        if(self.size==0){
            return true
        }
        false
    }
    
    fn is_full(&self) -> bool {
        if(self.size==self.capacity){
            return true
        }
        false
    }
}

Day12總結

1. Queue 先進先出
2. Rust VecDeque用法
3. 如何用陣列實作Circular Queue

參考資料

1. https://doc.rust-lang.org/std/collections/struct.VecDeque.html