Queue是一種先進先出(First-In-First-Out,簡稱FIFO)的資料結構,最先進入的元素也會最先被取出。
Queue可用在哪裡?
Queue可用來實現按照先進先出的順序處理任務。例如一售票網站,Queue可以提供一個Buffer,讓使用者可以在同時操作網站時,按照先來先得的順序購買到產品。Queue可以允許多個使用者並發訪問售票網站,並確保任務以正確的順序執行,從而提高網站的效率和可擴展性。除了售票網站,Queue還可以用於許多其他需要處理任務的場景,例如消息佇列、網路通訊、圖像處理等。
Loading balancing和Buffer
在學到上面Buffer用法時我想到了Loading balancing,Loading balancing(負載平衡)和Queue的Buffer(緩衝區)是兩個不同的概念,雖然它們在某些情況下可能會一起使用。
Loading balancing指的是將工作負載分配給多個伺服器,以實現較高的性能、可用性和容錯能力。通常,Load balancing會將輸入請求分發到不同的處理器或服務器,從而平衡輸入流量,並將工作負載分散到不同的計算資源上。Load balancing通常需要使用特定的算法來確定輸入請求應該由哪個計算機或服務器處理,以實現最佳的性能和容錯能力。
Queue的Buffer是一種資料結構,用於在系統中平衡不同部分之間的資料流量。它可以允許一部分系統在輸出資料之前緩存大量的資料,以避免資料流量過大而導致系統崩潰或壅塞。Queue的Buffer通常是一個暫存區,當資料被輸入到系統時,它們會被存儲在緩衝區中,直到被處理或移動到下一個階段。
在某些情況下,它們可以一起使用,例如在使用多個計算機或服務器進行負載平衡時,可以使用緩衝區來緩存輸入的資料,並確保平均分配到不同的計算機或服務器上。這樣可以避免在負載不均時出現資料流量過大的問題,從而提高系統的效率和容錯能力。
Queue的種類
deque是「雙向queue」的簡稱,可以在兩端加入(push)或取出(pop)元素。
circular queue是一個循環的資料結構,當Queue已滿時,下一個被加入的元素會被放到Queue的開頭,原本Queue的第一個元素會被移除。當Queue的尾端到達資料結構的末尾時,它會環繞回到Queue的開頭。
387. First Unique Character in a String
353. Design Snake Game
貪吃蛇題目(有難度,需多看幾次)
933. Number of Recent Calls
題目很難看懂,可以參考巴哈姆特的講解 LeetCode – 933. Number of Recent Calls 解題心得
346. Moving Average from Data Stream
MovingAverage滑動窗口大小為3,所以超過就得把一開始存的值給去除