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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.006/sequence-and-set-interface.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.