基本数据结构

栈和队列

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

栈

栈上的insert操作称为push，无元素参数的delete操作称为pop。栈顶为空时表示栈不含任何元素，即栈为空。如果试图对一个空栈执行pop操作，则称为栈下溢，如果试图对一个满栈push，则称为栈上溢。

---

队列

队列上的insert操作称为入队，delete操作称为出队。如果试图从一个空队列删除一个元素，则队列发生下溢，如果试图向一个满队列插入一个元素，则队列发生上溢。

链表

链表其中的各个对象按照线性顺序排列。链表的顺序是由各个对象里的指针决定的。链表为动态集合提供了一个简单而灵活的表示方法。

双向链表

每个对象有一个关键字和两个指针，如果哪个元素没有前驱，则该元素就是链表的第一个元素即链表的头。如果哪个元素没有后继，则该元素是最后一个元素即链表的尾。如果头指针指向的是null，则链表为空。

---

循环链表

头指针的前驱指向链表尾部元素，尾部元素的后继指向头元素。

链表的基本操作

链表的搜索

LIST-SEARCH(L,k)
x = L.head
while x != null and x.key != k
    x = x->next
return x

链表的插入(头插法)

LIST-INSERT(L,x)
x.next = L.head
if L.head != null
    L.head.prev = x
L.head = x
x.prev = null

链表的删除

LIST-DELETE(L,x)
if x.prev != null
    x.prev.next = x.next
else L.head = x.next
if x.next != null
    x.next.prev = x.prev