掌握堆疊、隊列與鏈表的核心概念，理解數據組織與操作的基本原理 Master the core concepts of Stacks, Queues and Linked Lists — understand the fundamentals of data organisation and manipulation
點擊任意模塊快速跳轉到對應章節 Click any module to jump to the corresponding section
了解數據結構的定義、數組和指針的基本概念 Understand the definition of data structures, and the basics of arrays and pointers
數據結構是指在電腦記憶體中組織和管理數據的方法。它決定了數據項在記憶體中的順序和位置。例如，儲存全班同學的成績時，我們使用數組代替數十個變量。
A data structure refers to the methods of organising and managing data in computer memory. They determine the sequences and locations of data items. For example, to store all students' scores, we use an array instead of tens of variables.
數組是一種簡單的線性數據結構，在連續的電腦記憶體中按順序儲存一組數據。可以使用索引直接計算記憶體地址並訪問數據項。例如 the_array[4] 的值為 "E"。
An array is a simple linear data structure that stores a set of data sequentially in continuous computer memory. The computer can use the index to calculate the memory address quickly and access a given item directly. For example, the_array[4] is "E".
指針是一個用於儲存電腦記憶體地址的變量，通常儲存另一個變量的地址。指針就像一個箭頭，指向特定的變量。
A pointer is a variable for storing a computer memory address, usually the address of another variable. A pointer can be compared to an arrow that points to a specific variable.
後進先出 (LIFO) — 最後加入的數據最先被取出
Last-In First-Out (LIFO) — the last item added is the first to be removed
先進先出 (FIFO) — 最先加入的數據最先被取出
First-In First-Out (FIFO) — the first item added is the first to be removed
由節點組成，每個節點儲存數據和指向下一節點的指針
Formed by nodes; each node stores data and a pointer to the next node
除了列表，Python 還有一種數據結構叫「字典」(dictionary)。字典以鍵(key)和值(value)的組合儲存數據。 Apart from lists, Python has a data structure called "dictionary". A dictionary stores data by the combination of key and value.
後進先出 (LIFO) 數據結構 — 最後加入的最先被取出 Last-In First-Out (LIFO) data structure — the last item added is the first to be removed
想象你是一個圖書管理員，把書從書架上取下放到另一個書架。最後取出的書成為堆疊的底部。放回時，你拿起堆疊頂部的書，即最後取出的那本。這種操作模式稱為後進先出 (LIFO)。
Imagine you are a librarian taking books from a bookshelf and stacking them. The first book taken out becomes the bottom of the stack. When putting books back, you pick up the one at the top — the last book taken out. This is called Last-In First-Out (LIFO).
將數據項加入堆疊頂部
Add a data item to the top of the stack
從堆疊頂部移除數據項
Remove a data item from the top of the stack
繪圖軟件中的「復原」和「取消復原」功能使用堆疊數據結構。每次操作加入復原堆疊；按「復原」時，最後一個操作從復原堆疊移到重做堆疊；按「取消復原」時，反向操作。
The "undo" and "redo" operations in drawing software use the stack data structure. Each operation is added to the undo stack; pressing "undo" moves the last operation to the redo stack; pressing "redo" reverses this.
調用堆疊是儲存在RAM中的堆疊，用於協調子程序。當調用子程序時，其堆疊幀（包含返回地址等信息）被推入調用堆疊；子程序執行完畢後，其堆疊幀被彈出。
Call stack is a stack stored in RAM used to coordinate sub-programs. When a sub-program is called, its stack frame (containing return address etc.) is pushed onto the call stack; when the sub-program finishes, its stack frame is popped.
| 堆疊操作Stack Operation | Python 列表操作Python List Operation | 說明Description |
|---|---|---|
| 定義堆疊Define a stack | the_stack = [] |
建立空列表Create an empty list |
| Push 推入 | the_stack.append(item) |
將 item 加入列表末端Add item to the end of the list |
| Pop 彈出 | the_stack.pop() |
返回並刪除列表末端的項目Return and delete the item at the end of the list |
注意事項：Important Notes:
1. 不能從空堆疊彈出數據，否則會發生下溢錯誤 (underflow error)
2. 不能向滿堆疊推入數據，否則會發生溢出錯誤 (overflow error)
1. Cannot pop items from an empty stack — otherwise an underflow error will occur
2. Cannot push items into a full stack — otherwise an overflow error will occur
先進先出 (FIFO) 數據結構 — 最先加入的最先被取出 First-In First-Out (FIFO) data structure — the first item added is the first to be removed
假設你在一家新開張的餐廳外排隊，餐廳沒有訂桌系統，以先到先得的方式讓顧客進入。由於你是隊列中的第一個人，你可以最先進入餐廳。這種操作模式稱為先進先出 (FIFO)。
Suppose you are waiting in a queue outside a restaurant with a first-come, first-served approach. Since you are the first diner in the queue, you can enter the restaurant first. This mode is called First-In First-Out (FIFO).
將數據項加入隊列末端
Add a data item to the end of the queue
從隊列開頭移除數據項
Remove a data item from the beginning of the queue
隊列在電腦系統中有廣泛應用。例如，打印文件的順序儲存為打印機記憶體中的隊列。當用戶發送打印文件的任務時，打印機將任務加入隊列，然後使用先進先出的方法完成隊列中的任務。
Queues are widely applied in computer systems. For example, the order of printing documents is stored as a queue in the printer memory. When the user sends a printing task, the printer adds the task to the queue, then completes the tasks using the first-in first-out approach.
| 隊列操作Queue Operation | Python 列表操作Python List Operation | 說明Description |
|---|---|---|
| 定義隊列Define a queue | the_queue = [] |
建立空列表Create an empty list |
| Enqueue 排隊 | the_queue.append(item) |
將 item 加入列表末端Add item to the end of the list |
| Dequeue 離隊 | the_queue.pop(0) |
返回並刪除列表開頭的項目Return and delete the item at the beginning of the list |
使用兩個指針 head 和 tail 分別指向隊列的第一個和最後一個項目。加入或刪除項目時，只需移動指針，無需移動所有數據。
Use two pointers head and tail to indicate the first and last items of the queue respectively. When adding or deleting, we simply move the pointers without shifting all data.
當指針到達數組末端時，重置指針到數組開頭的索引，形成循環隊列。這樣可以重複使用數組空間，避免浪費電腦資源。
When a pointer reaches the end of the array, reset it to the index of the first item. This forms a circular queue, allowing the array space to be reused and avoiding wasted resources.
使用循環隊列時，應使用額外變量 N 記錄隊列中的項目數量，以區分空隊列和滿隊列。
When using a circular queue, use an extra variable N to record the number of items, to distinguish between an empty and a full queue.
注意事項：Important Notes:
1. 不能從空隊列彈出數據，否則會發生下溢錯誤 (underflow error)
2. 不能向滿隊列加入數據，否則會發生溢出錯誤 (overflow error)
1. Cannot dequeue from an empty queue — otherwise an underflow error will occur
2. Cannot enqueue into a full queue — otherwise an overflow error will occur
由節點組成的靈活數據結構，每個節點儲存數據和指向下一節點的指針 A flexible data structure formed by nodes; each node stores data and a pointer to the next node
鏈表由許多節點 (node) 組成。每個節點儲存自己的數據和一個指針，指針儲存下一個節點的地址。鏈表中的所有節點都通過指針連接。
A linked list is formed by many nodes. Each node stores its own data and a pointer, which stores the address of the next node. Nodes in the linked list are all connected by pointers.
只需修改前一個節點的指針，使其指向被刪除節點的下一個節點
Simply modify the pointer of the previous node to point to the node after the deleted one
先將新節點的指針指向下一個節點，再將前一個節點的指針重定向到新節點
First direct the new node's pointer to the next node, then redirect the previous node's pointer to the new node
文件系統長期使用後，大量文件被創建、編輯和刪除。文件以分散片段的形式儲存在存儲設備中，這種分散排列稱為磁盤碎片化。鏈表是記憶體管理中使用的數據結構之一，電腦系統使用鏈表連接文件的所有片段。
After a file system has been used for a long time, many files are created, edited and deleted. Files are stored as separate fragments — called disk fragmentation. A linked list is one of the data structures used in memory management. The computer system connects all fragments of a file using a linked list.
雙向鏈表的每個節點不僅儲存自己的數據，還儲存兩個指針，分別指向前一個節點和後一個節點。雙向鏈表的優點是可以從兩個方向訪問節點；缺點是需要更多記憶體空間。
A doubly linked list node stores not only its own data but also two pointers: one pointing to the previous node (prev) and one to the next node (next). Advantage: nodes can be accessed from both directions. Disadvantage: more memory is required.
| 特性Feature | 鏈表Linked Lists | 數組Arrays |
|---|---|---|
| 儲存的數據類型Types of data stored | 不同類型Different | 相同類型Same |
| 數據訪問方式Data access method | 順序存取Sequential access | 直接存取 / 隨機存取Direct / Random access |
| 數據訪問速度Speed of data access | 慢Low | 快High |
| 加入/刪除數據速度Speed of adding/deleting data | 快High | 慢Low |
15道題目，測試你對數據結構的掌握程度 15 questions to test your understanding of data structures
the_stack.pop() 返回並刪除列表末端的項目，這對應堆疊的彈出操作。pop(0) 是隊列的離隊操作。
the_stack.pop() returns and deletes the item at the end of the list, corresponding to the stack pop operation. pop(0) is used for queue dequeue.
the_queue.pop(0) 返回並刪除列表開頭的項目，對應隊列的離隊操作（先進先出）。
the_queue.pop(0) returns and deletes the item at the beginning of the list, corresponding to the queue dequeue operation (FIFO).
點擊卡片翻轉查看答案，鞏固核心詞彙和概念 Click a card to flip it and see the answer — reinforce key vocabulary and concepts
點擊查看定義
Click to see definition
tap to flip
在電腦記憶體中組織和管理數據的方法，決定數據項的順序和位置
Methods of organising and managing data in computer memory; determines sequences and locations of data items
點擊查看定義
Click to see definition
tap to flip
後進先出 (LIFO) 數據結構。操作：Push（推入頂部）、Pop（從頂部移除）
Last-In First-Out (LIFO) data structure. Operations: Push (add to top), Pop (remove from top)
點擊查看定義
Click to see definition
tap to flip
先進先出 (FIFO) 數據結構。操作：Enqueue（加入末端）、Dequeue（從開頭移除）
First-In First-Out (FIFO) data structure. Operations: Enqueue (add to end), Dequeue (remove from front)
點擊查看定義
Click to see definition
tap to flip
由節點組成的數據結構，每個節點儲存數據和指向下一節點的指針，通過指針連接所有節點
A data structure formed by nodes; each node stores data and a pointer to the next node, connecting all nodes via pointers
全稱是什麼？
What does it stand for?
tap to flip
Last-In First-Out（後進先出）— 堆疊的操作模式
Last-In First-Out — the operating mode of a stack
全稱是什麼？
What does it stand for?
tap to flip
First-In First-Out（先進先出）— 隊列的操作模式
First-In First-Out — the operating mode of a queue
Python 代碼？
Python code?
tap to flip
the_stack.append(item)
將 item 加入堆疊（列表末端）
Add item to the stack (end of list)
Python 代碼？
Python code?
tap to flip
the_stack.pop()
從堆疊頂部（列表末端）移除並返回項目
Remove and return item from stack top (end of list)
Python 代碼？
Python code?
tap to flip
the_queue.append(item)
將 item 加入隊列末端
Add item to the end of the queue
Python 代碼？
Python code?
tap to flip
the_queue.pop(0)
從隊列開頭移除並返回第一個項目
Remove and return the first item from the front of the queue
何時發生？
When does it occur?
tap to flip
向已滿的堆疊或隊列加入數據時發生
Occurs when pushing/enqueuing data into a full stack or queue
何時發生？
When does it occur?
tap to flip
從空的堆疊或隊列取出數據時發生
Occurs when popping/dequeuing data from an empty stack or queue
點擊查看定義
Click to see definition
tap to flip
用於儲存電腦記憶體地址的變量，通常儲存另一個變量的地址，就像一個指向特定變量的箭頭
A variable for storing a computer memory address, usually the address of another variable — like an arrow pointing to a specific variable
點擊查看定義
Click to see definition
tap to flip
鏈表的基本組成單位，每個節點儲存數據和指向下一個節點的指針
The basic unit of a linked list; each node stores data and a pointer to the next node
點擊查看定義
Click to see definition
tap to flip
表示鏈表末端的特殊指針值，通常用 -1 或 null 表示，表示沒有下一個節點
A special pointer value indicating the end of a linked list, usually represented by -1 or null, meaning there is no next node
哪種數據結構使用？
Which data structure uses this?
tap to flip
數組使用直接存取（隨機存取）。電腦用索引直接計算記憶體地址，無需從頭搜索
Arrays use direct access (random access). The computer uses the index to calculate the memory address directly, without searching from the start
哪種數據結構使用？
Which data structure uses this?
tap to flip
鏈表使用順序存取。訪問特定位置的數據時，必須從頭開始沿指針逐一搜索
Linked lists use sequential access. To access data at a given location, you must search from the beginning and follow the pointers
點擊查看定義
Click to see definition
tap to flip
儲存在RAM中的堆疊，用於協調子程序。調用子程序時推入堆疊幀，執行完畢後彈出
A stack stored in RAM used to coordinate sub-programs. Stack frames are pushed when sub-programs are called and popped when they finish
點擊查看定義
Click to see definition
tap to flip
當指針到達數組末端時，重置到數組開頭，形成循環。使用額外變量 N 記錄項目數量以區分空隊列和滿隊列
When a pointer reaches the end of the array, it resets to the beginning, forming a circle. Use extra variable N to distinguish empty vs full queue
優點和缺點？
Advantage and disadvantage?
tap to flip
優點：可從兩個方向訪問節點（prev 和 next 指針）
缺點：需要更多記憶體空間（每節點兩個指針）
Advantage: nodes can be accessed from both directions (prev and next pointers)
Disadvantage: requires more memory (two pointers per node)
各自的優勢？
Respective advantages?
tap to flip
鏈表：加入/刪除速度快
數組：訪問速度快（直接存取）
Linked list: fast add/delete
Array: fast access (direct access)
與哪種數據結構相關？
Related to which data structure?
tap to flip
鏈表。文件系統使用鏈表連接分散存儲的文件片段，每個節點指向下一個片段的位置
Linked list. File systems use linked lists to connect scattered file fragments; each node points to the location of the next fragment
舉例說明
Give examples
tap to flip
1. 軟件的復原/取消復原 (Undo/Redo)
2. 程序的調用堆疊 (Call Stack)
3. 網頁瀏覽器的返回功能
1. Software Undo/Redo
2. Program Call Stack
3. Browser back button
舉例說明
Give examples
tap to flip
1. 打印機管理打印任務
2. 銀行排隊系統
3. 網絡數據包傳輸
1. Printer managing print jobs
2. Bank queuing system
3. Network packet transmission
參考 DSE 題型設計，涵蓋堆疊、隊列及鏈表的核心考點 Designed after DSE question styles, covering key examination topics on stacks, queues and linked lists
push(S, c)：將裝有 c 瓶軟飲料的塑料箱推入堆疊 Spop(S)：從堆疊 S 取出一個塑料箱並返回其中的軟飲料數量isEmpty(S)：如果堆疊 S 為空則返回 True，否則返回 Falsepush(S1, 30) → push(S1, 10) → push(S1, 10) → push(S1, pop(S1)+pop(S1)) → push(S1, 25)
Austin uses stacks to manage plastic boxes storing soft drinks. The following sub-programs are used:push(S, c): Push a plastic box with c bottles into stack Spop(S): Take a plastic box from stack S and return the number of soft drinksisEmpty(S): Return True if stack S is empty; otherwise return Falsepush(S1, 30) → push(S1, 10) → push(S1, 10) → push(S1, pop(S1)+pop(S1)) → push(S1, 25)
步驟分析：
1. push(S1, 30) → S1 = [30]（底部）
2. push(S1, 10) → S1 = [30, 10]
3. push(S1, 10) → S1 = [30, 10, 10]
4. pop(S1) = 10，pop(S1) = 10，10+10 = 20；push(S1, 20) → S1 = [30, 20]
5. push(S1, 25) → S1 = [30, 20, 25]（頂部）
最終結果：堆疊 S1 從底部到頂部為 30, 20, 25
Step-by-step analysis:
1. push(S1, 30) → S1 = [30] (bottom)
2. push(S1, 10) → S1 = [30, 10]
3. push(S1, 10) → S1 = [30, 10, 10]
4. pop(S1) = 10, pop(S1) = 10, 10+10 = 20; push(S1, 20) → S1 = [30, 20]
5. push(S1, 25) → S1 = [30, 20, 25] (top)
Final result: Stack S1 from bottom to top: 30, 20, 25
reverse(A, B)，用於將堆疊 A 中的所有塑料箱移到堆疊 B，使 B 中的箱子順序與 A 相反。假設初始時 S1 為非空堆疊，S2 為空堆疊，執行 reverse(S1, S2) 後，S1 和 S2 的內容如下：reverse(A, B) 完成偽代碼。
The sub-program reverse(A, B) moves all boxes in stack A to stack B in reverse order. Given initial non-empty S1 and empty S2, after executing reverse(S1, S2):reverse(A, B).
解析：只要堆疊 A 不為空，就持續從 A 的頂部彈出一個項目並推入 B。由於堆疊的 LIFO 特性，A 的頂部（最後加入）會成為 B 的底部，實現反轉。
Explanation: While stack A is not empty, keep popping from the top of A and pushing into B. Due to LIFO, the top of A (last added) becomes the bottom of B, achieving reversal.
分析：
- T123 進站（離隊）：P 增加 1，P = 2
- T136、T587、T364 加入隊列（排隊）：Q 依次增加，Q = 5
結果：
- 數組 T：索引1=T123（已離隊）, 索引2=T746, 索引3=T136, 索引4=T587, 索引5=T364
- P = 2（指向 T746，第一個等待的列車）
- Q = 5（指向 T364，最後加入的列車）
Analysis:
- T123 enters platform (dequeue): P increases by 1, P = 2
- T136, T587, T364 join queue (enqueue): Q increases, Q = 5
Result:
- Array T: index 1=T123 (dequeued), index 2=T746, index 3=T136, index 4=T587, index 5=T364
- P = 2 (pointing to T746, first waiting train)
- Q = 5 (pointing to T364, last joined train)
delQ(T)：如果 T 不為空，返回第一個等待顧客並從 T 中刪除addQ(T, name)：如果 T 有空位，將新顧客姓名儲存在 T 的最後位置delQ(T) 後，N = 2，first = 8。addQ(T, Katie) 後，N = 3，first = 8。delQ(T): If T is not empty, return and remove the first waiting customeraddQ(T, name): If T has an empty position, save the new customer name at the last positiondelQ(T): N = 2, first = 8.addQ(T, Katie): N = 3, first = 8.答案：隊列 (Queue)
解析：這個售票服務採用先到先得的方式（first-come, first-served），即先進入隊列的顧客先得到服務。這正是隊列 (Queue) 的先進先出 (FIFO) 特性。
注意：由於數組有固定大小，且使用 first 變量追蹤第一個顧客的位置，這實際上是一個循環隊列的應用。當 first + N - 1 超過數組末端時，需要使用取模運算回到數組開頭。
Answer: Queue
Explanation: This ticketing service uses a first-come, first-served approach — the first customer to join the queue is served first. This is exactly the First-In First-Out (FIFO) characteristic of a queue.
Note: Since the array has a fixed size and uses variable first to track the first customer's position, this is actually a circular queue application. When first + N - 1 exceeds the array end, modulo arithmetic is used to wrap around.
(a)(i) 追蹤指針：
索引0（start）→ 指針3 → 索引3（Whampoa）→ 指針5 → 索引5（Ho Man Tin）→ 指針2 → 索引2（Yau Ma Tei）→ 指針6 → 索引6（Mong Kok）→ 指針-1（結束）
順序：start, Whampoa, Ho Man Tin, Yau Ma Tei, Mong Kok
(a)(ii) 節點數量：5個節點（包括 start 節點）
(a)(i) Following the pointers:
Index 0 (start) → pointer 3 → Index 3 (Whampoa) → pointer 5 → Index 5 (Ho Man Tin) → pointer 2 → Index 2 (Yau Ma Tei) → pointer 6 → Index 6 (Mong Kok) → pointer -1 (end)
Order: start, Whampoa, Ho Man Tin, Yau Ma Tei, Mong Kok
(a)(ii) Number of nodes: 5 nodes (including the start node)
printList() 按順序打印所有節點的內容。請完成偽代碼。
Jessica uses a linked list to store activities on her schedule, represented by two arrays:printList() to print all nodes in order. Complete the pseudocode.
(a) 追蹤指針（monday = 2）：
索引2（painting）→ ptr[2]=5 → 索引5（tea）→ ptr[5]=4 → 索引4（yoga）→ ptr[4]=1 → 索引1（japanese）→ ptr[1]=null（結束）
順序：painting, tea, yoga, japanese
(a) Following pointers (monday = 2):
Index 2 (painting) → ptr[2]=5 → Index 5 (tea) → ptr[5]=4 → Index 4 (yoga) → ptr[4]=1 → Index 1 (japanese) → ptr[1]=null (end)
Order: painting, tea, yoga, japanese
解析：從 monday 指向的節點開始，持續輸出當前節點的內容，然後將 current 更新為下一個節點的索引，直到遇到空值指針（null）為止。
Explanation: Start from the node pointed to by monday, continuously output the current node's content, then update current to the next node's index, until a null pointer is encountered.