浅析队列、栈的应用

《浅析队列、栈的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学期论文2专业：计算机科学与技术_______班级：U计算机111__________学号：1111503111__________姓名：于秀芳__________指导教师：孟敏__________完成日期：2012年11月29日______   5浅析队列、栈的应用于秀芳(盐城工学院优集学院江苏盐城224051)摘要：栈和队列是两种常用的数据结构，广泛应用在操作系统、编译程序等各种软件系统中。从数据结构角度看，栈和队列是操作受限的线性表，栈和队列的数据元素具有单一的前驱和后继的线性关系；从抽象数据类型角度看，栈和队列又是两种重要的抽象

2、数据类型。关键词：栈和队列；数据结构；编译程序AnalysisOfTheQueue,StackOfApplicationsYuXiuFang(UGSCollege,YanchengInstituteofTechnology,Yancheng,Jiangsu224051)Abstract:Stacksandqueuesaretwocommondatastructurewidelyusedoperatingsystems,compilersandothersoftwaresystems.Fromtheperspectiveofdatastr

3、ucture,stackandqueueoperationisconstrainedlinearlist,stackandqueuedataelementshavingasingleprecursorandsuccessorlinearrelationship;Fromtheperspectiveofabstractdatatypes,stacksandqueuesaretwokindsofimportantabstractdatatype.Keywords:Stackandqueue;Datastructure;Compilerpro

4、gram0引言：目前我们所学的数据结构包括上学期学过的C++都运用到了栈，队列。1栈的逻辑结构1.1栈的定义栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈中元素除了具有线性关系外，还具有后进先出的特性。1.2栈的顺序存储结构及实现1.2.1栈的顺序存储结构栈的顺序存储结构称为顺序栈。顺序栈本质上是顺序表的简化，唯一需要确定的是用数组的那一端表示栈底。通常把数组中下标为0的一端作为栈底，同时附设指针top指示栈顶元素在元组中的位置。设存储栈元素的数组长度为Stac

5、kSize，则栈空时栈顶指针top=-1；栈满时栈顶指top=StackSize-1。入栈时，栈顶指针top加1；出栈时，栈顶指针top减1。1.2.2顺序栈的实现（1）栈的初始化初始化一个空栈只需将栈顶指针top置为1。（2）入栈操作TemplateVoidSeqStack::Push(DataTypex){If(top==StackSize-1)throw”上溢”;5data[++top]=x;}(3)出栈操作TemplateVoidSeqStack

6、ataType>::Pop(){If(top==-1)throw”上溢”;x=data[top--];returnx;}1.2.3两栈共享空间在一个程序中如果需要同时使用具有相同数据类型的两个栈时，最直接的方法是为每一个栈开辟一个数组空间，同时另一个栈的空间仍有大量剩余而没有得到利用的情况，从而造成存储空间的浪费。一种可取的方法是充分利用顺序栈单向延伸的特性，使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸。1.3栈的链接存储结构及实现1.3.1栈的链接存储结构栈的链接存

7、储结构称为链栈。通常链栈用单链表表示，因此其节点结构与单链表的节点结构相同。因为只能在栈顶执行插入和删除操作，显然以单链表的头部做栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点。1.3.2链栈的实现链栈的结点结构可以复用单链表的结点结构TemplateclassLinkStack{Public:LinkStack(){top=NULL;}~LinkStack();Voidpush(DataTypex);DataTypepop();DataTypeGetTop(){if(top!=NULL

8、)returntop->data;}IntEmpty(){top==NULL?return1:return0;}Private:Node*top;};（1）构造函数构造函数的作用是初始化