10.4 Abstract Data Types 抽象数据类型简答

ADT definition

An Abstract Data Type is：

• A collection of data。
• Together with a defined set of operations on those data。
• Its behaviour/interface is considered separately from implementation details。

Stack、queue 和 linked list 都是 ADTs。

Stack

• LIFO：last in, first out。
• Add with PUSH；remove/read top with POP。
• One top-of-stack pointer identifies the current top item。
• Suitable for undo history, function calls, expression evaluation and reversing order。

Array implementation：one 1D array stores items；an INTEGER stack pointer is used as the array index；capacity and empty/full conditions must be tracked。

Queue

• FIFO：first in, first out。
• Add at rear with ENQUEUE；remove from front with DEQUEUE。
• Front and rear/end pointers are required；a count can distinguish empty/full states。
• Circular queue wraps pointers to the beginning and reuses released array locations。
• Suitable for print jobs, customer requests and tasks processed in arrival order。

Linked list

• Consists of nodes。
• Each node stores a data item and a pointer/index to the next node。
• A start pointer identifies the first node；null marks the end。
• A free-list pointer may identify unused nodes in an array implementation。
• Items need not occupy consecutive array locations；insertion/deletion changes links rather than shifting all later data。

Suitable when the collection changes frequently or ordered insertion/deletion is required。

Justifying a choice

• Need most recent item first -> stack because LIFO。
• Need arrival order -> queue because FIFO。
• Need frequent insertion/deletion with linked order -> linked list。

Always name the required behaviour, not only the ADT name。

Pointer operations in descriptions

When adding/removing data, describe both data movement and pointer update：

• Stack POP：retrieve top item, then update top pointer。
• Queue ENQUEUE：store at rear/end position, then update rear/count。
• Queue DEQUEUE：retrieve front item, then update front/count。
• Linked list insertion/deletion：update affected next pointers and start/free-list pointers。

Exam checklist

• ADT definition 是否包含 data + operations？
• Stack/queue 是否正确写 LIFO/FIFO？
• Queue 是否说明 front/rear pointers？
• Circular queue 是否说明 wrap around？
• Linked list 是否写 node、data、next pointer、start/null？
• Situation justification 是否联系所需 removal order？

---

本章 syllabus 不要求从零编写这些 ADT 的完整 pseudocode；实际 pointer 操作与 trace 将在专项中处理。