"链队列——链式映象"
**栈的定义和特点**
栈是一种限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶（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等领域。
我的内容管理
展开
