Sequence and Set Interface

Interface (API/ADT) vs. Data structure

二者的主要区别如下：

Interface (API/ADT)	Data Structure
规范 (Specification)	表现形式 (Representation)
需要维护什么数据	如何维护数据
指定支持的操作及其语义	实现所支持操作的算法
提出问题	解决方案

Sequence Interface

Static Sequence Interface

维护一个数据序列（sequence）， $x_0, x_1, x_2, ..., x_{n-1}$ ，同时支持以下操作：

• len()：返回数据序列的长度 n

• seq-iter()：遍历 $x_0, x_1, x_2, ..., x_{n-1}$

• at(i)：返回序号为 i 的数据 $x_i$

  • left() => at(0)

  • right() => at(n-1)

• set-at(i, x)：将序号为 i 的元素替换为 x

我们有哪些数据结构可以实现 static sequence interface？如静态数组 A[0...n]

Dynamic Sequence Interface

维护一个数据序列， $x_0, x_1, x_2, ..., x_{n-1}$ ，除了支持 Static Sequence Interface 之外，还支持以下操作：

• insert-at(i, x)：将 x 插入到序号为 i 的位置上，同时将所有原来序号 ≥ i 的元素向右移动一个位置

• delete-at(i): 将所有序号 ≥ i+1 的元素向左移动一个位置

• set-at(i, x)：语义上等同于连续执行 delete-at(i) 和 insert-at(i, x)

特殊案例：

• Stack

  • right() - top

  • insert/delete-right() - push/pop

• queue

  • insert-right() - enqueue

  • delete-left() - dequeue

• deque

  • insert/delete left/right

Set Interface

Static Set Interface

维护一个键值对集合，支持以下操作：

• find-key(k)：如果可以，找到对应 k 的值

• iter()：按任意顺序遍历所有键值对/键/值

Dynamic Set Interface

维护一个键值对集合，在支持 static set interface 所有操作的基础上，支持以下操作：

• insert(k, x)：将键值对 k, v 存入键值对中，若键已存在，则覆盖值

• delete-key(k)：将键为 k 的键值对从集合中删除

Ordered Set Interface

维护一个键值对集合，所有键按顺序排列。在支持 static set interface 所有操作的基础上，支持以下操作：

• find-next(k)：找到键大于 k 的最小键对应的值

• find-prev(k)：找到键小于 k 的最大键对应的值

• find-min()：找到最小键对应的值

• find-max()：找到最大键对应的值

• order-iter()：按键的顺序依次遍历所有键值对/键/值

Dynamic Ordered Set Interface

在 Ordered Set Interface 的基础上，支持以下操作：

• delete-min()：删除最小键对应的键值对

• delete-max()：删除最大键对应的键值对

Priority Queue Interface

priority queue 是 dynamic ordered set 的一个特殊例子，支持：

• insert(x)

• find/delete-min() 或者 find/delete-max()