# 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()