15-3 環狀排列物件 建立佇列 Cirular Queue

Original: https://course.andys.pro/Javascript-Intro/15-3-arranging-objects-in-a-circular-queue-creating-a-cirular-queue/

講義

1. 基本資料結構：佇列 (Queue) 與 堆疊 (Stack)

在處理資料時，資料進出的順序非常重要。

• 佇列 (Queue)：
  • 特性：先進先出 (First In First Out, FIFO)。
  • 生活範例：排隊買高鐵票。第一個排隊的人第一個買完離開。
  • JavaScript 實作：使用 push() 從後面加入，使用 shift() 從前面取出。
• 堆疊 (Stack)：
  • 特性：先進後出 (First In Last Out, FILO)。
  • 生活範例：堆疊書本或盤子。最後放上去的那一個，會最先被拿走。
  • JavaScript 實作：使用 push() 從後面加入，使用 pop() 從後面取出。

2. 封裝一個 Queue 物件

我們可以利用 JavaScript 的函式來建立一個具備「排隊功能」的物件：

function MyQueue() {
    var items = [];
    this.enqueue = function(item) { items.push(item); }; // 排隊
    this.dequeue = function() { return items.shift(); }; // 離開
    this.show = function() { console.log(items); };      // 顯示
}

3. 環狀佇列 (Circular Queue)

這是一種進階的資料結構，它的最後一個位置會連接回第一個位置形成一個圓環。

• 目的：更有效率地利用固定大小的記憶體空間。
• 原理：透過指標（Head 與 Tail）以及取餘數運算，讓資料在滿額時可以從頭開始填補空間。

4. 小結

• 如果你需要處理「有先後順序」的任務（例如印表機待印文件），請使用 Queue。
• 如果你需要處理「最近的優先處理」（例如網頁的「回上一頁」功能），請使用 Stack。

影片逐字稿 (AI 生成)

接下來我們來看15-3 環狀排列物件那這邊呢 大家不見得一定要把環狀柱列做出來而且那個定義其實 就比較偏向是演算法和資料結構那我們比較不會 我們不用講那麼仔細好的 我們先了解什麼是Q然後在JavaScript裡面建立Q好的 我們來看什麼是Q呢Q有一個特性 就是它就是一個Array最簡單的就是一個Array那這個Array有什麼特性它有First In First OutOK 那First In First Out在我們現實中 像是什麼我們在排隊對不對 我們排隊的時候第一個 第一個開始排隊的第一個領票 第一個買票這叫做一個QOK就是說 你第一個進去排隊你當然是第一個出了 你第一個去買那有另外一個東西叫做 First In Last OutFirst In Last OutFirst In Last Out那First In Last Out是什麼呢這是Stack那Stack比較像什麼呢生活場景中的Stack是最像什麼像是你有很多的書 像是前面這邊有一堆的書對不對你放第一本下去 放第二本下去 放第三本下去的時候當你要拿的時候 你是從最上面開始拿所以它是 First In Last Out你先放進去 可是卻是最後拿出來它是堆疊的它是疊在 就是好那我們簡單的理解了 什麼是Q 什麼是Stack以後呢我們來看看 這個要怎麼寫好的 那這邊呢我其實昨天晚上看到很不開心原因是因為就是它把這個 In 當作一個變數來做可是實際上 In 是保留字所以不要用 In用 I 就好In 是保留字啊然後你如果直接用的話你不能把它當變數用那我昨天有寫我昨天有看一下寫又寫15章好的那這邊我們要看到的是呃 從Function那邊我們要去看第9章然後那個延伸的閱讀那在延伸的閱讀裡面我們會看到的事情是呃 這個其實是一個Class就是一個呃 OO就是物件導向那我們可以看到這邊是一個呃 Function然後 Function 裡面我有一個變數是 Q是空的 Array然後裡面有好幾個 Function那這個 Function 在做的事情其實就是跟我們在我們在做那個比如說Let然後我有一個 Q然後這個 Q 是一個物件然後物件不是大家還記得嗎我們是不是可以寫說什麼 FirstOut然後裡面可以寫一個 Function是類似的意思這樣子那只是這邊我們的寫法是怎麼樣我們這邊寫法是我們可以 Q Shift然後來做那只是我們現在換成用 Class的寫法來寫那寫起來就會像這樣OK所以這個 Q比如說我現在 New 了一個 Q那 A 它自然的就有什麼功能它 A 自然就有 Show 的功能A 自然就有 FirstIn 的功能A 自然就有 FirstOut 的功能A 自然就有 FirstOut 的功能可以嗎如果有點難以接受沒有關係我們這邊把 A 印出來或是說欸對然後我們這邊其實我們在 Chrome 裡面來看來看好 我們先建一個這樣的東西然後我們看一下那個 A 裡面有什麼A 裡面是不是就有 FirstIn有 FirstOut 有 Show這幾個這幾個這幾個那個這幾個 Function然後這幾個 Function 同時會怎樣呢因為我們如果大家還記得 Scope 的話它的這個 Q取用的這個 Q是這裡面這個 QOK好的所以我今天我可以做對這個 A 做什麼事情我可以對它 FirstIn然後我可以塞什麼東西給它我可以塞比如說我塞一個數字 5然後這是我 A Show我給大家看有沒有Consol log Q.toStream我可以讓大家看到裡面有一個 5然後我可以再塞6然後我可以看到裡面有什麼有5 6我再塞一個7然後裡面我們看A.Show我們可以看到裡面有5 6 7這樣OK嗎好那這時候呢我這邊有大家還記得Shift嗎好我對 A來做我可以對 A來做我可以對 A來做我直接用這個因為我不能直接對它做 Shift因為它的 Q是在它自己本身裡面的嘛然後我要用它裡面的功能來操作它那所以我這邊 Q的 Shift我就要 call這個 First Out的功能然後我的 A點 Show可以看它有什麼它有六七OK嗎我FIRST IN嘛5今天進去的嘛5 6 7然後我 First Out5就不見了剩6 7這樣可以接受嗎我今天在高鐵買那個高鐵票的時候有一個人叫5 他先去排隊有一個人叫6 他先去排隊有一個人叫7 他進去排隊好 現在穿口空了對不對我現在來來來一個來一個排隊來一個是不是第一個進去的人突出啦排隊只剩6跟7這樣可以理解嗎好那這段 quote我應該也要放上去好 那這就是一個呃Cue的一個實作那這個實作也是我看它這邊的範例的 quote然後去把它寫出來的OK 這邊有show對不對然後show去console.log把 cue to string印出來那配合剛剛那個圖push是從後面推一個進去shift是從前面拿一個出來那你如果今天要implement你今天要去做你今天要去實作一個stack那你要怎麼做第一個進去最後一個出來所以我這只要push跟pop就好OK回到剛剛這張圖回到剛剛這個對不對我進去是push然後cue是first in first out所以這邊是shift出來那我如果是stack是不是first in last out所以我用pop就我要拿東西的時候我從後面拿一個是從前面拿一個是從後面拿這樣大家可以理解嗎好了我們快速來講一下環狀助力環狀助力它其實環狀助力的跟剛剛的cue其實很類似只是呢它今天它的做法是我的尾巴我最尾巴比如說我今天開了55的長度的環狀助力那它的尾巴到這邊最尾巴還會再連到最前面去所以它是一個環形的結構然後它有幾個條件就是說滿的情況下是rear跟front相鄰一個位置然後代表數列為滿那這個我覺得是有一點在現在來講的話是有點難的然後我們也可以看一下網路上有人用Java script來寫那個Circular Queue環狀助力那這個呢就有點可怕就是幾行有點可怕100多行好那大家來看一下快速看一下就好首先呢它是不是也是建一個functioncue然後在這邊呢它有一個空的叫做listcue就是它list的話你就可以把它想像成就是物件就有點像object然後object裡面去建一個cue然後這個cue是空的然後它這邊是list.reset是一個功能然後它的頭看尾是-1-1然後它可以去call它這邊去執行它嘛就執行這個function然後這邊有inqueueinqueue就是有好幾個條件然後會怎麼樣去增加啊然後然後去移動起始位置就是head跟tail的位置所以是有點複雜好那下面這邊呢因為前面是把這個東西先建構起來這個cue可以幹嘛那這邊的cue這邊的cue是說我建一個大小為5的一個circularcue然後我塞一個東西2 2 3 4東西進去然後把它丟出來再塞兩個東西再塞好幾個東西進去然後丟丟丟丟丟出來那這邊是在操作這個cue這邊是宣告這個cue這邊是宣告這個cue所以大概是這樣子的所以大概是這樣子的好那這就是15章第15章OK那Lab3這邊大家都可以參考我的call然後來來做好先這樣囉謝謝謝謝謝謝謝謝謝謝

影片逐字稿largev2

接下來我們來看15-3 環狀排列物件那這邊呢大家不見得一定要把環狀註列做出來而且那個定義其實就比較偏向是演算法和資料結構那我們比較不會 我們不用講那麼仔細好了 我們先了解什麼是Q然後在 JavaScript 裡面建立 Q好的 我們來看什麼是 Q 呢Q 有一個特性就是它就是一個 Array最簡單的就是一個 Array那這個 Array 有什麼特性它有 First In First Out那 First In First Out 在我們現實中像是什麼我們在排隊我們排隊的時候第一個開始排隊的第一個領票 第一個買票這叫做一個 Queue就是說你第一個進去排隊你當然是第一個去買那有另外一個東西叫做 First In Last OutFirst In Last Out那 First In Last Out 是什麼呢這是 Stack那 Stack 比較像什麼呢生活場景中的 Stack 是最像什麼像是你有很多的書像是前面這邊有一堆的書你放第一本下去放第二本下去放第三本下去的時候當你要拿的時候你是從最上面開始拿所以它是 First In Last Out你先放進去可是卻是最後拿出來它是堆疊的那我們簡單的理解了什麼是 Queue什麼是 Stack 以後呢我們來看看這個要怎麼寫好的 那這邊呢我其實昨天晚上看到很不開心原因是因為就是它把這個 In 當作一個變數來做可是實際上 In 是保留字所以不要用 In用 I 就好OkIn 是保留字啊然後你如果直接用的話你不能把它當變數用那我昨天有寫15 張好的那這邊我們要看到的是從 Function 那邊我們要去看第九章那個延伸的閱讀那在延伸的閱讀裡面我們會看到的事情是這個其實是一個 Class就是一個OO就是物件導向那我們會看到這邊是一個 Function然後在 Function 裡面我有一個變數是 Q是空的 Array然後裡面有好幾個 Function那這個 Function 在做的事情其實就是跟我們在我們在做那個 比如說 Let然後我有一個 Q然後這個 Q 是一個物件然後物件不是大家還記得嗎我們是不是可以寫說什麼 First Out然後裡面可以寫一個 Function是類似的意思這樣子那只是這邊我們的寫法是怎麼樣我們這邊寫法是我們可以 Q Shift然後來做那只是我們現在換成用 Class 的寫法來寫那寫起來就會像這樣OK所以這個 Q比如說我先 New 了一個 Q那 A 它自然的就有什麼功能它 A 自然就有 Show 的功能A 自然就有 First In 的功能A 自然就有 First Out 的功能可以嗎如果有點難以接受沒有關係我們這邊把 A 印出來或是說 欸對然後我們這邊其實我們在 Chrome 裡面來看我們先建一個這樣的東西然後我們看一下那個 A 裡面有什麼A 裡面是不是就有 First In 有 First Out 有 Show這幾個這幾個那個這幾個 Function然後這幾個 Function 同時會怎樣呢因為我們如果大家還記得 Scope 的話它的這個 Q取用的這個 Q是這裡面的這個 QOK好的所以我今天我可以做對這個 A 做什麼事情我可以對它 First In然後我可以塞什麼東西給它我可以塞比如說我塞一個數字 5 好了然後這時候 A Show 我給大家看有沒有 Console.log Q.toString我可以讓大家看到裡面有一個 5然後我可以再塞6然後我可以看到裡面有什麼有 5,6然後我可以再塞5,6我再塞一個 7然後裡面我們看A.Show我們可以看到裡面有 5,6,7這樣 OK 嗎好那這時候呢我這邊有大家還記得 Shift 嗎好我對 A 來做我可以對 A 來做我直接用這個因為我不能直接對它做 Shift因為它的 Q 是在它自己本身裡面的然後我要用它裡面的功能來操作它那所以我這邊 Q 的 Shift我就要 Call 這個 First Out的功能然後我的 A.Show我可以看它有什麼它有 6,7OK 嗎First In 嘛5 進去的嘛5,6,7然後我 First Out5 就不見了剩 6,7這樣可以接受嗎我今天在高鐵買那個高鐵票的時候有一個人叫 5他先去排隊有一個人叫 6他進去排隊有一個人叫 7他進去排隊好現在穿口空了對不對我現在來一個來一個排隊的來一個是不是第一個進去的人吐出啦排隊的只剩 6 跟 7這樣可以理解嗎好那這段 Code我應該也要放上去好那這就是一個Q 的一個實作那這個實作也是我看它這邊的範例的 Code然後就把它寫出來的OK 這邊有 Show對不對然後 Show 去 Console.log把 Q to String 印出來那配合剛剛那個圖Push 是從後面推一個進去Shift 是從前面拿一個出來那你如果今天要 Implement你今天要去做你今天要去實作一個 Stack那你要怎麼做第一個進去最後一個出來所以我就只要Push 跟 Pop 就好OK回到剛剛這一張圖回到剛剛這個對不對我進去是Push然後 Q 是First In First Out所以這邊是 Shift 出來那我如果是 Stack是不是 First In Last Out所以我用 Pop就我要拿東西的時候我從後面拿一個是從前面拿一個是從後面拿這樣大家可以理解嗎好好了我們快速來講一下環狀佇列那其實環狀佇列跟剛剛的 Q 其實很類似只是呢它今天它的做法是我的尾巴比如說我今天開了五的長度的環狀佇列那它的尾巴到這邊最尾邊還會再連到最前面去所以它是一個環形的結構然後它有幾個條件就是說滿的情況下是Rear 跟 Front相鄰一個位置然後代表佇列尾馬那這個我覺得是有點在現在來講的話是有點難的然後我們也可以看一下網路上有人用 Javascript 來寫那個Circular Q 環狀佇列那這個呢就有點可怕就是幾行有點可怕一百多行好那大家來看一下快速看一下就好首先呢它是不是也是建一個 Function Q然後在這邊呢它有一個空的叫做 List 的 Q就是它 List 的話你就可以把它想像成就是物件就有點像 Object然後 Object 裡面去建一個 Q然後這個 Q 是空的然後它這邊是 ResetList.Reset 是一個功能然後它的頭和尾是負一負一然後它可以去它這邊去執行它嘛就執行這個 Function然後這邊有 In QIn Q 就是有好幾個條件然後會怎麼樣去增加然後去移動起始位置就是Head 跟 Tail 的位置所以是有點複雜好那下面這邊呢因為前面是把這個東西 Q先建構起來這個 Q 可以幹嘛那這邊的 Q 是說我建一個大小為 5 的一個 Circular Q然後我塞一個東西二三四的東西進去然後把它丟出來再塞兩個東西再塞好幾個東西進去然後丟丟丟丟丟丟丟出來OK那這邊是在操作這個 Q這邊是宣稿這個 Q所以大概是這樣子的好那這就是十五張第十五張OK那 Lab 3 這邊大家都可以參考我的 Code然後來來做好 先這樣囉