数据结构应用(栈——基础知识)

《数据结构应用(栈——基础知识)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈基础知识栈的定义一摞书籍、一叠盘子往手电筒里放电池,取电池.最先放的是最后被取出铁路调度中用到停车栈生活中栈的实例栈的插入和删除操作分别称为进栈和出栈。进栈是将一个数据元素存放在栈顶，出栈是将栈顶元素取出。图中a1称为栈底元素，an为栈顶元素。定义：栈(stack)是限定仅在表尾的一端进行插入或删除操作的线性表。允许进行插入或删除操作的一端称为栈顶(top)，而另一端称为栈底(bottom)。不含元素的栈称为空栈。栈的定义及基本运算a1a2an-1an…栈顶(top)栈底(bottom)出栈进栈栈底元素栈顶元素栈的“上溢”和“下溢”当栈满时再做进栈运算必定产

2、生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。Init()Destroy(S)Clear(S)Push(S,e)Pop(S,e)IsEmpty(S)Size(S)GetTop(S,e)栈的主要操作顺序栈的操作实现typedefstruct{DataTypedata[MaxSize];inttop;//top指示栈顶元//素在顺序栈中的位置(下标)}SeqStacka1a2an-1an…top栈

3、底(bottom)栈底元素栈顶元素栈的顺序存储定义AEs.top43210s.top=-1(a)空栈43210s.tops.top=0(b)进栈s.top43210ABCDs.top=4(c)栈满s.top43210s.top=2(d)出栈ABCAE⑴置空栈：首先建立栈空间，然后初始化栈顶指针。SeqStack*Init(){SeqStack*s;s=newSeqStack;s->top=-1;returns;}顺序栈的基本操作⑵判空栈boolIsEmpty(SeqStack*s){if(s->top==-1)returntrue;elsereturnfals

4、e;}顺序栈的基本操作⑶入栈intPush(SeqStack*s,DataTypex){if(s->top==MaxSize-1)returnERROR;//栈满不能入栈else{s->top++;s->data[s->top]=x;returnOK;}}顺序栈的基本操作⑷出栈intPop(SeqStack*s,DataType*x){if(IsEmpty(s))returnERROR;//栈空else{*x=s->data[s->top];//栈顶元素存入*xs->top--;returnOK;}}顺序栈的基本操作⑸取栈顶元素DataTypeGetTop(S

5、eqStack*s){if(IsEmpty(s))returnERROR;//栈空returns->data[s->top];}顺序栈的基本操作链栈的操作实现a1a2a3^栈底栈顶…...an若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些。链栈的示意toptypedefstructNode{DataTypedata;Node*next;}StackNode,*LinkStack;栈的链式存储定

6、义⑴置空栈voidInit(LinkStacktop){top=NULL;}链栈的基本操作⑵判栈空boolIsEmpty(LinkStacktop){returntop==NULL;}链栈的基本操作⑶入栈intPush(LinkStacktop,DataTypex){/*将数据元素x压入栈head中*/StackNode*temp=newStackNode;if(temp==NULL)returnERROR;/*申请空间失败*/temp->data=x;temp->next=top;top=temp;/*修改当前栈顶指针*/returnOK;}链栈的基本操作⑷

7、出栈intPop(LinkStacktop,DataType*x){/*将栈head的栈顶元素弹出，放到x所指的存储空间中*/if(top==NULL)/*栈为空*/returnERROR;*x=top->data;LinkStackp=top;top=top->next;deletep;/*释放存储空间*/returnTRUE;}链栈的基本操作问题：当程序中同时使用几个栈时，如何防止栈的上溢？方法一：将栈的容量加到足够大，但这种方法由于事先难以估计容量，有可能浪费空间。方法二：使用两个（或多个）栈共享存储空间办法。两栈的栈底分别设在给定存储空间的两端，然后各

8、自向中间伸延，当两栈的栈顶相遇时才可能