栈和队列：链式映象的数据结构

"链队列——链式映象" **栈的定义和特点** 栈是一种限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶（Top），另一端为栈底（Bottom）。当表中没有元素时称为空栈。栈的修改是按后进先出的原则进行的，因此，栈称为后进先出表（LIFO）。 **栈的类型定义** 栈的抽象数据类型的定义如下： ``` ADTStack{ 数据对象： D＝{ai|aiElemSet,i=1,2,,n,n≥0} ∈ 数据关系： R1＝{<ai-1,ai>|ai-1,aiD,i=2,,n} ∈ /*约定an端为栈顶，a1端为栈底。*/ 基本操作： ADTStackInitStack(&S) DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S,&e) ClearStack(&S) Push(&S,e) Pop(&S,&e) StackTravers(S,visit()) } ``` **栈的实现** 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。 **栈的应用** 栈的应用非常广泛，例如，一叠书或一叠盘子。栈也广泛应用于编译器、解释器、计算器等领域。 **队列的定义和特点** 队列是一种特殊的链表，队列的元素按先进先出的原则进行插入和删除操作。队列的应用也非常广泛，例如，打印机队列、网络队列等。 **队列的类型定义** 队列的抽象数据类型的定义如下： ``` ADTQueue{ 数据对象： D＝{ai|aiElemSet,i=1,2,,n,n≥0} ∈ 数据关系： R1＝{<ai-1,ai>|ai-1,aiD,i=2,,n} ∈ /*约定an端为队首，a1端为队尾。*/ 基本操作： ADTQueueInitQueue(&Q) DestroyQueue(&Q) QueueLength(Q) QueueEmpty(Q) GetFront(Q,&e) ClearQueue(&Q) Enqueue(&Q,e) Dequeue(&Q,&e) QueueTravers(Q,visit()) } ``` **队列的实现** 队列的实现可以使用链表或数组来实现。链式队列的实现可以使用链表来存储队列的元素，而顺序队列的实现可以使用数组来存储队列的元素。 **队列的应用** 队列的应用非常广泛，例如，打印机队列、网络队列等。队列也广泛应用于操作系统、数据库、_compiler等领域。