← 回首頁

線性結構(動態陣列 / 堆疊 / 環形佇列 / 雙端佇列)

生活裡拿東西各有各的「規矩」:一疊洗好的盤子只能從最上面拿(最後放的最先被拿走),排隊買票卻是先來先買——明明都是一排東西,差別只在「你被允許從哪一頭存放」。這頁的四種結構就是把這些日常規矩寫成程式:動態陣列像可任意翻找的置物架,滿了得整批搬到更大的架子;堆疊像那疊盤子,只認同一端進出;環形佇列像排隊,但把隊伍首尾接成一圈重複利用空間;雙端佇列則前後兩頭都能進出。下面你可以逐步播放每個操作,看指標怎麼移動、空間怎麼被繞回重複使用。

四種結構都是「循序容量格 + 少數合法存取指標」的變形,差異只在允許存取的位置與索引移動規則:

1. 動態陣列(Dynamic Array,擴容搬遷)

以「容量格 + size 指標」實作:add 在 size 位置寫入並遞增 size,容量不足時先 resize(容量倍增、逐格搬遷舊資料到新陣列); insert 需先把 index 之後的元素整批右移一格才能寫入;remove 需把 index 之後的元素整批左移一格填補空缺。

固定示範腳本(容量 2 起始):兩次擴容 + 中間插入(右移)+ 刪除(左移)。終態(獨立模擬):[9,8,3,7],容量 8。

操作腳本

    寫格次數:0
    每格代表一個容量位置;藍色外框(active)為本幀真正被寫入的格,粉紅(pivot)標示本次操作的目標索引;空格顯示為空白。

    指標面板

    size0
    capacity0

    已執行操作紀錄

    2. 堆疊(Stack,LIFO)

    以「容量格 + top 指標」實作:push 在 top 位置寫入後遞增 top;pop 先遞減 top,取出該格的值再清空(避免殘留)。 只能從同一端(top)存取,是四種結構中不變量最簡單的一種。

    固定示範腳本(容量 6):push 5,8,3 → pop → push 7 → pop → pop。終態(獨立模擬):[5],top=0。

    操作腳本

      操作次數:0
      每格代表一個容量位置;藍色外框(active)為本幀操作的格,粉紅(pivot)標示 pop 後新的頂端位置;空格顯示為空白。

      指標面板

      top

      已執行操作紀錄

      3. 環形佇列(Circular Queue,FIFO)

      以「容量格 + front/rear 指標」實作:enqueue 在 rear 位置寫入後把 rear 以取模方式前進一格;dequeue 讀出 front 位置的值後清空, 再把 front 以取模方式前進一格。當指標走到容量邊界(capacity-1)時會「繞回」索引 0,重複利用陣列前段已釋出的空間, 不需要像動態陣列那樣整批搬遷。

      固定示範腳本(容量 4):進 5,8,3 → 出 → 出 → 進 7,2,6(wrap)→ 出。終態(邏輯序):[7,2,6];rear 於第 6 個 enqueue(7)時繞回 0。

      操作腳本

        操作次數:0
        每格代表一個容量位置;藍色外框(active)為本幀寫入/清空的格,粉紅(pivot)標示目前 rear/front 指向。容量滿時 rear 會從尾端「繞回」索引 0 繼續寫入;front 消費到尾端同樣會繞回 0,不需搬移既有資料。

        指標面板

        front0
        rear0
        size0

        已執行操作紀錄

        4. 雙端佇列(Deque,兩端插入/刪除)

        以「容量格 + front/rear 指標」實作環形陣列:addLast/removeFirst 與環形佇列相同方向;addFirst 則把 front「反向」取模前進 (front = (front-1+capacity)%capacity 後才寫入),removeLast 則把 rear 反向取模退一格再讀值。front 在索引 0 時再往前一步會 「反向繞回」到尾端(capacity-1),與環形佇列 front/rear 只會「正向繞回」到 0 的方向相反。

        固定示範腳本(容量 5):addLast 5 → addFirst 8 → addLast 3 → removeFirst → addFirst 7 → removeLast。終態(邏輯序):[7,5];addFirst(8) 時 front 反向繞回 4。

        操作腳本

          操作次數:0
          每格代表一個容量位置;藍色外框(active)為本幀寫入/清空的格,粉紅(pivot)標示目前最前端/最後端位置。addFirst 在 front=0 時會反向繞回容量尾端(capacity-1),與環形佇列 front 只會正向繞回 0 的方向相反。

          指標面板

          front0
          rear0
          size0

          已執行操作紀錄