浅谈栈和队列

《浅谈栈和队列》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅谈栈和队列摘要：栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基木操作的特殊性，栈必须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操作。和线性表相比，它们的插入和删除操作受史多的约來和限定，故又称为限定忭的线性表结构。关键词:栈和队列；数据结构；线性表；抽象数据类型StackandQueueAbstract:Stackasakindofdatastructure，itisakindofcanintheendoftheinsertanddeleteoperationofthespecialline

2、arlist.Queueisaspecialkindoflinearlist，itisallowedonlyinthefrontofthetable(front)todeleteoperation,butinthetableafterend(rear)insertionoperation.Forinsertionoperationoftheendcalledrear,todeleteoperationoftheendcalledteamhead.Thequeuenoelement，calledemptyqueue.Keywords：St

3、ackandqueue;Datastructure;Linearlist;Abstractdatatypeo引言栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。队列是一种特殊的线性表，它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。在队列这种数据结构屮，最先插入的元素将足姒先被删除的元素;反之鉍后插入的元素将是鉍后被删除的元素，因此队列又称为“先进先出”(FIFO—firstinfirstout)的线性表。1栈1.1栈的逻辑结构栈的逻辑结构和我们先前学过的线性表相冋，如果它是非空的，则

4、有且只有一个开始结点，有且只能有一个终端结点，W它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继)，仴足栈的运算规则与线性表相比有更多的限制，栈(Stack)足仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(LastInFirstOut).1.2栈的顺序存储结构及实现由于栈也是线性表，因此线性农的存储结构对栈也适用，通常栈有顺序栈和链栈W种存储结构,这两种存储结构的不同，则使得实现栈的基木运算的算法也有所不同。

5、#includestructnodeintdata;node*next;classLinkStackpublic:LinkStack(){top=NULL;}//构造函数置空链栈〜LinkStack();//析构函数，释放链栈屮个节点的存储空间voidPush(intx);//将元索x进浅intPop();//将栈顶元素出梭intGettopO//获取栈顶元素{if(top!=NULL)retumtop->data;}//取找顶元素(外不删陳)boolcmptyO//判断链栈是也为空栈{if(top==NULL)

6、return1;elsereturn0;}private:node*top;//栈顶指针即链栈的头指针}；voidLinkStack::Push(intx)//元素进栈{node*s=newnode;//申清一个数据域力x的节点ss->data=x;s-〉next=top;//将节点s插在栈顶top=s;)intLinkStack::Pop()//元素出栈{intx;if(top==NULL)throw"下溢n;x=top->data;//暂存栈顶元素node*p=top;//将栈顶jj'点摘链top=top->next;deletep

7、;returnx;LinkStack:>LinkStack()//析构函数将链栈中所有节点的存储空间释放{while(top){node*p=top->next;deletetop;top=p;))voidmain(){LinkStacklink;intdata;cout«"请输入进栈的10个元素:";for(inti=0;i<10;i++)//输入进栈的10个元素{cin»data;link.Push(data);)link.PopO;//栈顶元素出栈coul«n现在栈顶的元素为:n«link.Gettop()«endl;//输Hi栈

8、顶元素while(!link.empty())cout«'•现在出栈的足："«link.Pop()«endl;//所有元素一个一个出栈}1.3顺序栈和链桟的比较实现顺序栈和链栈的所有基木操作的算法都从能需要