Sequence and Set Interface

Interface (API/ADT) vs. Data structure

二者的主要区别如下:

Interface (API/ADT)

Data Structure

规范 (Specification)

表现形式 (Representation)

需要维护什么数据

如何维护数据

指定支持的操作及其语义

实现所支持操作的算法

提出问题

解决方案

Sequence Interface

Static Sequence Interface

维护一个数据序列(sequence), x0,x1,x2,...,xn1x_0, x_1, x_2, ..., x_{n-1} ,同时支持以下操作:

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

  • seq-iter():遍历 x0,x1,x2,...,xn1x_0, x_1, x_2, ..., x_{n-1}

  • at(i):返回序号为 i 的数据 xix_i

    • left() => at(0)

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

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

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

Dynamic Sequence Interface

维护一个数据序列, x0,x1,x2,...,xn1x_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()