文档介绍：** 队列** 离散事件模拟栈和队列是重要的线性结构,实质上是操作受限的线性表。 栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端(表尾)进行。进行插入和删除的一端是浮动端,通常被称为栈顶(TOP),并用一个“栈顶指针”指示;而另一端是固定端,通常被称为栈底(bottom)。当表中没有元素时称为空栈。我们经常将栈用下图的形式描述S=(a1,a2,a3,…an),则a1称为栈底元素, an为栈顶元素。栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。出栈入栈后进先出(LastInFirstOut),简称为LIFO线性表。举例1:家里吃饭的碗。举例2:在建筑工地上使用的砖块ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。基本操作:}ADTStack下面我们先给出栈结构的基本操作:(1)初始化栈InitStack(&S)(2)入栈Push(&S,e)(3)出栈Pop(&S,&e)(4)获取栈顶元素内容GetTop(S,&e)(5)判断栈是否为空StackEmpty(S) (6)清空栈 ClearStack(&S)(7)返回栈的长度 StackLength(S)-顺序栈由于栈是运算受限的线性表,因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈,是用一组连续的存储单元依次存放栈中的每个数据元素。用起始端作为栈底,用指针base标记,它是固定的。栈顶位置是随着进栈和退栈操作而变化的,故需用一个指针top来标记。顺序栈的定义栈的空间能够扩充。设两个常量: STACK_INIT_SIZE(初始分配量) STACKINCREMENT(分配增量)typedefstruct{SElemType*baseSElemType*topintstacksize//顺序栈的存储容量}SqStack;top初值指向栈底,每插入一个元素(入栈)增1,始终指向栈顶元素的下一个位置,每删除一个元素减1(出栈)。base==NULL 栈不存在栈空:top==base栈満:top-base>=stacksize元素个数??topbaseEDCBAbasetopAbasetop基本操作的实现StatusInitStack(SqStack&S){=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!)exit(OVERFLOW);=;=STACK_INIT_SIZE;returnOK;}//InitStack(1)初始化typedefstruct{SElemType*baseSElemType*topintstacksize}SqStack;(2)取栈顶元素StatusGetTop(SqStackS,SElemType&e){if(==)returnERROR;e=*(-1);returnok;}(3)出栈StatusPop(SqStack&S,SElemType&e){if(==)returnERROR;e=*--; returnOK;}--;e=*