Chapter 3: Lists, Stacks, and Queues

§1 Abstract Data Type (ADT)

【定义】 Data Type = { Objects } ∪

例：int = { 0, ±1, ±2, …, INT_MAX, INT_MIN } ∪ { +, -, *, /, %, … }

【定义】 An Abstract Data Type (ADT) is a data type organized such that the specification of objects and operations is separated from the representation and implementation.

即：用户只关心"能做什么"，不关心"怎么做"。

---

§2 The List ADT

Objects： $(ite{m}_0,ite{m}_1,\dots ,ite{m}_{N-1})$

Operations：

• 求长度 $N$

• 打印所有元素

• 创建空表

• 查找第 $k$ 个元素，$0\le k<N$

• 在第 $k$ 个元素之后插入新元素

• 删除某元素

• 查找当前元素的 Next / Previous

---

1. 简单数组实现（Simple Array）

array[i] = item_i;   // 顺序映射

• MaxSize 必须预估（静态分配）

• Find_Kth：$O(1)$（随机访问）

• 插入/删除：$O(N)$，且需大量移动数据

---

2. 链表实现（Linked List）

typedef struct list_node *list_ptr;
typedef struct list_node {
    char     data[4];
    list_ptr next;
};
list_ptr ptr;

节点在内存中不连续，位置每次运行可能不同。

Insertion（在 node 之后插入 temp）：

temp->next = node->next;
node->next = temp;

⚠ 顺序不能颠倒！先接后断。时间复杂度：$O(1)$

Deletion（删除 node，pre 为其前驱）：

pre->next = node->next;
free(node);

若要删除第一个节点，可在链表头部加一个哑结点（dummy head node）。时间复杂度：$O(1)$

---

双向循环链表（Doubly Linked Circular List）

使用场景： 需要快速访问前驱节点时（如删除节点）。单链表找前驱需从头遍历 $O(N)$。

typedef struct node *node_ptr;
typedef struct node {
    node_ptr llink;
    element  item;
    node_ptr rlink;
};

性质：ptr = ptr->llink->rlink = ptr->rlink->llink

带头结点的空列表：头结点的 llink 和 rlink 均指向自身。

---

两个应用

Application 1：多项式 ADT（Polynomial ADT）

$P(x)=a_1{x}^{e_1}+a_2{x}^{e_2}+\cdots +a_n{x}^{e_n}$

存储有序对 $⟨e_i,a_i⟩$，$e_i$ 为非负整数指数，$a_i$ 为系数。

表示方法 1（数组）：

typedef struct {
    int CoeffArray[MaxDegree + 1];
    int HighPower;
} *Polynomial;

• 优点：实现简单，加法和乘法直接按下标操作

• 缺点：对稀疏多项式（如 $10x^{1000}+5x^{14}+1$ 和 $3x^{1990}-2x^{1492}+11x+5$）大量空间浪费，且乘法 $O(N_1\cdot N_2)$ 实际很慢

表示方法 2（链表，按指数排序）：

typedef struct poly_node *poly_ptr;
struct poly_node {
    int      Coefficient;
    int      Exponent;
    poly_ptr Next;
};
typedef poly_ptr a; /* sorted by exponent */

仅存储非零项，适合稀疏多项式。

Application 2：多重列表（Multilists）

问题： 40000 名学生，2500 门课程，需打印每门课的学生名单，以及每个学生的选课列表。

表示方法 1（二维数组）：int Array[40000][2500] — 空间 $O(NM)$，极度浪费

表示方法 2（交叉链表）： 每个学生节点同时挂在学生链表和课程链表上，节省空间，$O(\text{选课总数})$。

---

3. 游标实现（Cursor Implementation，无指针）

用一个全局数组模拟链表，不使用指针，避免 malloc/free 开销。

• malloc 模拟：

p = CursorSpace[0].Next;
CursorSpace[0].Next = CursorSpace[p].Next;

• free(p) 模拟：

CursorSpace[p].Next = CursorSpace[0].Next;
CursorSpace[0].Next = p;

CursorSpace[0] 充当空闲链表的头结点。

游标实现通常比指针实现快，因为省去了系统内存管理例程的调用。接口与指针实现相同（透明替换）。

---

§3 The Stack ADT

1. ADT

Stack 是一个 Last-In-First-Out (LIFO) 的有序列表，插入和删除只在一端（顶部 Top）进行。

Operations：

int     IsEmpty(Stack S);
Stack   CreateStack();
void    DisposeStack(Stack S);
void    MakeEmpty(Stack S);
void    Push(ElementType X, Stack S);
ElementType Top(Stack S);
void    Pop(Stack S);

⚠ 对空栈执行 Pop 或 Top 是 ADT 错误；对满栈执行 Push 是实现错误（不是 ADT 错误）。

---

2. 实现

① 链表实现（带头结点）

Push（在头部插入）：

TmpCell->Next = S->Next;
S->Next = TmpCell;

Top：

return S->Next->Element;

Pop（删除头部节点）：

FirstCell = S->Next;
S->Next = S->Next->Next;
free(FirstCell);

malloc/free 调用代价较高 → 可用一个额外的"回收栈"（recycle bin）缓存释放的节点，避免频繁系统调用。

② 数组实现

struct StackRecord {
    int          Capacity;      /* 栈容量 */
    int          TopOfStack;    /* 栈顶指针，空栈时为 -1 */
    ElementType *Array;         /* 存储元素的数组 */
};

⚠ 栈模型必须严格封装：除栈操作例程外，其他代码不得直接访问 Array 或 TopOfStack。每次 Push/Pop 前必须做边界检查。

---

3. 应用

① 括号匹配（Balancing Symbols）

Algorithm:
    Make an empty stack S;
    while (read a character c) {
        if (c is an opening symbol)      Push(c, S);
        else if (c is a closing symbol) {
            if (S is empty)              ERROR;
            else if (Top(S) doesn't match c)  ERROR;
            else                         Pop(S);
        }
    }
    if (S is not empty)  ERROR;

$T(N)=O(N)$，其中 $N$ 是表达式长度。这是一个在线算法。

---

② 后缀表达式求值（Postfix Evaluation）

形式	示例
中缀（Infix）	$a+b\times c-d\times e$
前缀（Prefix）	$-+a\times bc\times de$
后缀（Postfix）	$abc\times +de\times -$

也称 逆波兰表示法（Reverse Polish notation）。

求值规则（用栈）：

• 读到操作数：压栈

• 读到运算符：弹出两个操作数，计算，结果压栈

• 结束时栈顶即为结果

〖Example〗 $62÷3-42\times +$

步骤	栈状态
push 6	[6]
push 2	[6, 2]
÷ → pop 2,6, push 3	[3]
push 3	[3, 3]
- → pop 3,3, push 0	[0]
push 4, push 2	[0, 4, 2]
× → pop 2,4, push 8	[0, 8]
+ → pop 8,0, push 8	[8]
结果 = 8

$T(N)=O(N)$，且无需知道运算符优先级。

---

③ 中缀转后缀（Infix to Postfix Conversion）

规则：

• 操作数直接输出

• 运算符：若栈顶运算符优先级 ≥ 当前运算符，先弹出输出，再压入当前运算符

• (：压栈（不在栈内时优先级最高，在栈内时优先级最低）

• )：弹出并输出直到遇到 (（( 出栈但不输出）

两个关键处理原则：

1. 永远不要因为 ) 以外的原因弹出 (
2. 为 ( 分别定义 in-stack 优先级（最低）和 incoming 优先级（最高）

〖Example〗 $a+b\times c-d\to abc\times +d-$

〖Example〗 $a\times (b+c)÷d\to abc+\times d÷$

$T(N)=O(N)$

---

④ 函数调用（Function Calls）—— System Stack

每次函数调用，系统在调用栈（System Stack）上压入一个栈帧（Stack Frame），包含：

• 返回地址（Return Address）

• 旧的帧指针（Old Frame Pointer）

• 局部变量（Local Variables）

尾递归（Tail Recursion）： 递归调用是函数最后一个操作，可被编译器自动转换为循环，无栈溢出风险：

// 尾递归版（坏习惯，会有爆栈风险）
void PrintList(List L) {
    if (L != NULL) {
        PrintElement(L->Element);
        PrintList(L->next);
    }
}

// 等价的迭代版
void PrintList(List L) {
top:
    if (L != NULL) {
        PrintElement(L->Element);
        L = L->next;
        goto top;
    }
}

• 递归可以被完全消除

• 非递归程序通常比等价的递归程序更快

• 但递归程序通常更简单易懂

---

§4 The Queue ADT

1. ADT

Queue 是一个 First-In-First-Out (FIFO) 的有序列表，插入在一端（Rear），删除在另一端（Front）。

Operations：

int         IsEmpty(Queue Q);
Queue       CreateQueue();
void        DisposeQueue(Queue Q);
void        MakeEmpty(Queue Q);
void        Enqueue(ElementType X, Queue Q);
ElementType Front(Queue Q);
void        Dequeue(Queue Q);

---

2. 数组实现（Array Implementation）

struct QueueRecord {
    int          Capacity;  /* 最大容量 */
    int          Front;     /* 队头指针 */
    int          Rear;      /* 队尾指针 */
    int          Size;      /* 当前元素个数（可选） */
    ElementType *Array;
};

循环队列（Circular Queue）：

用取模操作使数组循环利用。普通数组实现会出现"假满"（front 右移后前面有空位但显示满）问题。

• 判满/判空的问题：若仅靠 front 和 rear，当 front == rear 时无法区分队空还是队满。

  • 解决方案 1：牺牲一个空位，front == (rear+1) % Capacity 表示满。

  • 解决方案 2：增加 Size 字段，既能区分空满，又不浪费空间。

链表实现的队列是平凡的（trivial），通常不作重点讨论。