第三章栈和队列的应用
【实验目的】1．熟练掌握栈和队列的结构，以及这两种数据结构的特点；2．能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；3．熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法；
第一节知识准备一、栈：1基本概念栈是一种限定仅在表的一端进行插入与删除操作的线性表。允许进行插入与删除操作的这一端称为栈顶，而另一端称为栈底，不含元素的空表称为空栈，插入与删除分别称进栈与出栈。由于插入与删除只能在同一端进行，所以较先进入栈的元素，在进行出栈操作时，要比较后才能出栈。特别是，最先进栈者，最后才能出栈，而最晚进栈者，必最先出栈。因此，栈也称作后进先出（LastI
FirstOut）的线性表，简称LIFO表。栈示意图见图31
2栈的抽象数据类型定义：ADTStack数据对象：D∈ElemSeti12
0数据关系：R1∈Di2
基本操作：I
itStackS构造一个空栈SStackEmptyS判断栈S是否为空StackLe
gthS返回栈S的元素个数即栈的长度GetTopSe取栈S的栈顶元素PushSe将元素e入栈PopSe删除S的栈顶元素并用e返回其值（即出栈）ADTStack
f3栈的表示：
栈有两种存储表示方法：顺序存储结构和链式存储结构。
1顺序存储结构：
defi
eSTACK_INIT_SIZE100；存储空间初始分配量
defi
eSTACKINCREMENT10；存储空间分配增量
typedefstruct
SElemTypebase；栈底指针
SElemTypetop；
栈顶指针
i
tStackSize；
栈的当前容量
SqStack；
2链式存储结构：
TypedefstructL
ode
ElemTypedata
structL
ode
ext
L
odeLi
kList
二、队列：
1与栈相对应，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。
允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图见图32：
──────────────
出队←a1a2
……
a
1←a
进队
──────────────
队头
队尾
图32队列
2队列的抽象数据类型定义：ADTQueue数据对象：D∈ElemSeti12
0数据关系：R1∈Di2
基本操作：I
itQueueQ构造一个空队列Q
fQueueEmptyQ判断队列是否为空QueueLe
ghtQ返回队列Q的元素个数，即队列的长度GetHeadQe取队列Q的队头元素，并用e返回E
QueueQe将元素e入队列DeQueueQe删除非空队列Q的队头元素，并用e返回其值ADTQueue3队列的表示：队列有两种表示方法：链队列、循环队列（顺序r