1.2 抽象数据类型的表示与实现
<strong>抽象数据类型的定义</strong>
重要程度：8 分
<h2>抽象数据类型的定义</h2>
<p><strong>抽象数据类型（Abstract Data Type, ADT）</strong>是一种数学模型，以及定义在此模型上的一组操作。它封装了数据对象的表示细节和操作实现，仅通过接口提供对数据的操作。这种设计方法有助于提高程序的可维护性和重用性。</p>
<h3>关键点：</h3>
<ul>
<li>ADT包括数据对象、数据关系及一组基本操作。</li>
<li>数据对象是具有相同特性的元素集合；数据关系描述了这些元素之间的联系方式。</li>
<li>基本操作则指定了对该数据结构可以执行的动作，如插入、删除等。</li>
<li>ADT强调的是逻辑层面的定义，而不是具体的物理实现。</li>
</ul>
<h3>示例：栈（Stack）</h3>
<p>栈是一种常见的抽象数据类型，遵循后进先出(LIFO)原则。其基本操作包括：</p>
<ol>
<li><code>push(item)</code>: 向栈顶添加一个新元素。</li>
<li><code>pop()</code>: 移除并返回栈顶元素。</li>
<li><code>peek()</code> 或 <code>top()</code>: 返回栈顶元素但不移除。</li>
<li><code>isEmpty()</code>: 判断栈是否为空。</li>
</ol>
<p>对于用户来说，只需要知道如何使用这些接口来操作栈，而不需要了解栈内部是如何具体实现这些功能的。</p>
<h4>例题说明：</h4>
<p>假设我们需要利用栈来解决括号匹配问题。给定一个字符串，判断其中的圆括号()、方括号[]、花括号{}是否正确配对。</p>
<pre>
<code>
// 定义栈
class Stack {
constructor() {
this.items = [];
}
// 基本操作
push(element) { this.items.push(element); }
pop() { return this.items.pop(); }
peek() { return this.items[this.items.length - 1]; }
isEmpty() { return this.items.length === 0; }
}
function isMatched(str) {
let s = new Stack();
for (let i = 0; i < str.length; i++) {
let char = str[i];
if (char === '(' || char === '[' || char === '{') {
s.push(char);
} else {
if (s.isEmpty()) return false;
let last = s.pop();
if ((last === '(' && char !== ')') ||
(last === '[' && char !== ']') ||
(last === '{' && char !== '}')) {
return false;
}
}
}
return s.isEmpty();
}
console.log(isMatched("([{}])")); // true
console.log(isMatched("([{])}")); // false
</code>
</pre>
<p>在这个例子中，我们定义了一个简单的栈类，并利用它来检查输入字符串中的括号是否正确闭合。这里体现了ADT的思想——通过有限的操作集来完成复杂任务。</p>