生活裡拿東西各有各的「規矩」:一疊洗好的盤子只能從最上面拿(最後放的最先被拿走),排隊買票卻是先來先買——明明都是一排東西,差別只在「你被允許從哪一頭存放」。這頁的四種結構就是把這些日常規矩寫成程式:動態陣列像可任意翻找的置物架,滿了得整批搬到更大的架子;堆疊像那疊盤子,只認同一端進出;環形佇列像排隊,但把隊伍首尾接成一圈重複利用空間;雙端佇列則前後兩頭都能進出。下面你可以逐步播放每個操作,看指標怎麼移動、空間怎麼被繞回重複使用。
四種結構都是「循序容量格 + 少數合法存取指標」的變形,差異只在允許存取的位置與索引移動規則:
以「容量格 + size 指標」實作:add 在 size 位置寫入並遞增 size,容量不足時先 resize(容量倍增、逐格搬遷舊資料到新陣列); insert 需先把 index 之後的元素整批右移一格才能寫入;remove 需把 index 之後的元素整批左移一格填補空缺。
以「容量格 + top 指標」實作:push 在 top 位置寫入後遞增 top;pop 先遞減 top,取出該格的值再清空(避免殘留)。 只能從同一端(top)存取,是四種結構中不變量最簡單的一種。
以「容量格 + front/rear 指標」實作:enqueue 在 rear 位置寫入後把 rear 以取模方式前進一格;dequeue 讀出 front 位置的值後清空, 再把 front 以取模方式前進一格。當指標走到容量邊界(capacity-1)時會「繞回」索引 0,重複利用陣列前段已釋出的空間, 不需要像動態陣列那樣整批搬遷。
以「容量格 + front/rear 指標」實作環形陣列:addLast/removeFirst 與環形佇列相同方向;addFirst 則把 front「反向」取模前進 (front = (front-1+capacity)%capacity 後才寫入),removeLast 則把 rear 反向取模退一格再讀值。front 在索引 0 時再往前一步會 「反向繞回」到尾端(capacity-1),與環形佇列 front/rear 只會「正向繞回」到 0 的方向相反。