算法导论读书笔记（10）

栈和队列

栈和队列都是动态集合。栈实现了一种 先进先出 的策略。类似地，队列实现了一种 后进先出 的策略。

栈

作用于栈上的 INSERT 操作称为压入（ PUSH ），而无参的 DELETE 操作常称为弹出（ POP ）。可以使用一个数组 S [ 1 .. n ]来实现一个至多有 n 个元素的栈。如下图所示，数组 S 有个属性 S.top ，它指向最近插入的元素。

STACK-EMPTY(S)
1 if S.top == 0
2     return TRUE
3 else
4     return FALSE

PUSH(S, x)
1 S.top = S.top + 1
2 S[S.top] = x

POP(S)
1 if STACK-EMPTY(S)
2     error "underflow"
3 else
4     S.top = S.top - 1
5 return S[S.top + 1]

队列

我们把作用于队列上的 INSERT 操作称为入队（ ENQUEUE ），把作用于队列上的 DELETE 操作称为出队（ DEQUEUE ）。队列有头和尾。当一个元素入队时，将排在队尾，而出队的元素总是队首元素。下图说明了用一个数组 Q [ 1 .. n ]来实现一个至多含 n - 1 个元素的队列的方法。队列具有属性 Q.head ，它指向队列的头，另一个属性为 Q.tail ，它指向新元素将会被插入的地方。

ENQUEUE(Q, x)
1 Q[Q.tail] = x
2 if Q.tail == Q.length
3     Q.tail = 1
4 else
5     Q.tail = Q.tail + 1

DEQUEUE(Q)
1 x = Q[Q.head]
2 if Q.head == Q.length
3     Q.head = 1
4 else
5     Q.head = Q.head + 1
6 return x

链表

在链表中，各对象按线性顺序排序。其顺序由各对象中的指针决定。本节介绍的是无序的双链表。 双链表 的每一个元素都是一个对象，每个对象包含一个关键字域和两个指针域： next 和 prev 。对链表中的某个元素 x ， x.next 指向链表中 x 的后继元素，而 x.prev 则指向链表中 x 的前驱元素。下面给出的是链表的基本操作。

LIST-SEARCH(L, k)
1 x = L.head
2 while x != NIL and x.key != k
3     x = x.next
4 return x

LIST-INSERT(L, x)
1 x.next = L.head
2 if L.head != NIL
3     L.head.prev = x
4 L.head = x
5 x.prev = NIL

LIST-DELETE(L, x)
1 if x.prev != NIL
2     x.prev.next = x.next
3 else
4     L.head = x.next
5 if x.next != NIL
6     x.next.prev = x.prev

有根树的表示

用链表表示有根树

二叉树

如下图所示，用域 p ， left ， right 来存放指向二叉树 T 中的父亲，左儿子和右儿子的指针。如果 x.p = NIL ，则 x 为根。如果结点 x 无左儿子，则 x.left = NIL ，对右儿子也类似。整个树 T 的根由属性 T.root 指向。如果 T.root = NIL ，则树为空。

分支数无限的有根树

可以用二叉树很方便地表示具有任意子女数的树。该方法的优点是对任意含 n 个结点的有根树仅用 O ( n )空间。这种 左孩子 ， 右兄弟 的表示如下图所示。每个结点都包含一个父亲指针 p ， T.root 指向树 T 的根。每个结点 x 不再包含指向每个孩子结点的指针，而仅包含两个指针：

x.left-child 指向结点 x 的最左孩子。
x.right-sibling 指向结点 x 紧右边的兄弟。

如果 x 没有孩子，则 x.left-child = NIL ；如果 x 是其父结点的最右孩子，则 x.right-sibling = NIL 。