《数据结构与算法》_第3章 栈和队列-PPT.pptxVIP

【本章重点】;【本章难点】;【本章内容】;3.1栈;栈的常用基本运算

（1）InitStack(S)栈初始化，操作结果是构造一个空栈S。

（2）SetNull(S)置空栈，栈S已存在，将栈S清为空栈。

（3）Empty(S)判断栈空，若栈S为空则返回“真”值；否则返回“假”值。

（4）Push(S，x)进栈，若栈S不满，将数据元素x插入栈顶，并返回入栈是否成功的状态信息。入栈操作会改变栈的内容。

（5）Pop(S,x)出栈，若栈S非空，删除栈顶数据元素，通过参数x带回栈顶元素，并返回出栈是否成功的状态信息。出栈操作会使栈的内容发生变化。

（6）GetTop(S,x)取栈顶元素，若栈S非空，通过参数x带回栈顶元素，并返回取栈顶元素是否成功的状态信息。该操作完成后，栈的内容不变。;栈的基本运算应用举例

【例3.1】将一个非负的十进制整数转换为其它进制数（二、八、十六进制），利用栈来实现。

voidConversion(intn,intbase)//以十进制数和基数作为参数

{ Stack*S;intbit;

InitStack(S);//建立空栈

while(n!=0)

{ Push(S,n%base);//余数入栈

n=n/base; //整除基数

}

while(!EmptyStack(S))

{ bit=Pop(S);//余数出栈

if(bit9)printf(%c,bit+55);//将余数转为字符输出

elseprintf(%c,bit+48);

}

printf(\n);

}

;栈的顺序存储结构和基本运算的实现;2、顺序栈基本运算的实现;（3）判断栈空

intEmpty(SeqStack*S)

//若栈S为空栈，返回1；否则返回0

{ if(S-Top==-1)return1;

elsereturn0;

}

（4）入栈

intPush(SeqStack*S,datatypex)

//若栈S未满，则将元素x插入栈顶，并返回1，表示入栈成功；否则返回0，表示入栈不成功

{ if(S-Top==maxsize-1)

{printf(栈上溢);

return0;

}//上溢

else

{S-data[++S-Top]=x;

return1;

}

};（5）出栈

intPop(SeqStack*S,datatypex)

//若栈不空，则删除栈顶元素，由参数x带回栈顶元素，并返回1，表示出栈成功；否则返回0，表示出栈失败

{if(Empty(S))//判断栈是否为空

{printf(栈下溢);

return0;

}//下溢

else

{x=S-data[S-Top--];

return1;

}

};（6）取栈顶元素

intGetTop(SeqStack*S,datatypex)

//若栈不空，则删除栈顶元素，由x带回栈顶元素，并返回1，表示取栈顶元素成功；否则返回0，表示取栈顶元素失败

{if(EmptyS(S))//调用算法4.3，判断栈是否为空

{printf(栈下溢);

return0;

}//下溢

else

{x=S-data[S-Top];

return1;

}

};两个顺序栈共享连续空间，降低溢出的概率;出栈操作的算法：

datatypepop(SeqStack*S,inti)

//i号栈的栈顶元素出栈

{datatypex;

if(i==1)

if(S-Top1==-1)printf(“1号栈下溢”);

else{x=S-v[S-Top1];S-Top1--;}//1号栈出栈

else

if(S-top2==maxsize)printf(“2号栈下溢”);

else{x=S-v[S-Top2];S-Top2++;}//