数据结构-栈教材

一、教学内容：

1、 栈和队列的定义及特点；

2、 栈的顺序存储表示和链接存储表示；

3、 队列的顺序存储表示和链接存储表示；

4、 栈和队列的应用举例。

第三章栈和队列二、教学要求：

1、掌握栈和队列的定义、特性，并能正确应用它们解决实际问题；

2、熟练掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；

3、熟练掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况

栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性数据结构。栈栈的应用队列队列的应用3.1栈（stack）一、栈的定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的特点根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。

stack栈的基本操作1.初始化栈：INISTACK(&S)将栈S置为一个空栈(不含任何元素)。2.进栈：PUSH(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。3.出栈：POP(&S)

删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。4.取栈顶元素：GETTOP(S,&e)取栈S中栈顶元素。5.判栈空：StackEmpty(S)判断栈S是否为空，若为空，返回值为true，否则返回值为false。例1：对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？43512不可能实现，主要是其中的12顺序不能实现；

12345的输出可以实现，只需压入一个立即弹出一个即可。435612中到了12顺序不能实现；

135426可以实现。例3：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？答：答：例4：计算机系2005年考研题（程序设计基础）设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。答：二、顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下（静态）

#defineStackSize100typedefstruct{ElemTypedata[StackSize];inttop;}SeqStack;//-----栈的顺序存储表示

-----（动态）

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈顶top的值为下一个将要进栈的元素下标。

设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s–>data[0]是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>top加1，退栈时需将s–>top减1。因此，s–>top=0表示空栈，s–>top=stacksize表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。1、置空栈

voidinitstack(seqstack*s){s–>top=0;}2、判断栈空

intstackempty(seqstack*s){return(s–>top==0);}3、判断栈满

intstackfull(seqstack*s){return(s–>top==stacksize);}4、进栈

voidpush(seqstack*s，ElemTypex){if(stackfull(s))error(“stackoverflow”);s–>data[s–>top++]=x;}5、退栈

voidpop(seqstack*s,ElemType*x){if(stackempty(s))error(“stackunderflow”);s–>top--;*x=s–>data[top];}

6、取栈顶元素ElemTypestacktop(seqstack*s){if(stackempty(s)error(“stackisempty”);returns–>data[s–>top-1];}

3.1.3链栈

栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表可以没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：

栈的链接存储结构链栈的结点定义typedefstructnode{ElemTypedata;structnode*next;}LinkStack;

栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作在链栈中,栈的基本运算算法如下:(1)初始化栈initStack(&L)

建立一个空栈L。实际上是创建链栈的头结点,并将其next域置为NULL。对应算法如下:voidInitStack(ListStack*&L){ L=(ListStack*)malloc(sizeof(ListStack)); L->next=NULL;}

(2)销毁栈ClearStack(&L)

释放栈L占用的全部存储空间。对应算法如下:voidClearStack(ListStack*&L){ ListStack*p=L->next; while(p!=NULL) { free(L); L=p; p=p->next; }}

(3)求栈的长度StackLength(L)

从第一个数据结点开始扫描单链表,用i记录访问的数据结点个数,最后返回i值。对应算法如下:intStackLength(ListStack*L){ inti=0; ListStack*p; p=L->next; while(p!=NULL) {i++;p=p->next;} return(i);}

(4)判断栈是否为空StackEmpty(L)

栈L为空的条件是L->next==NULL,即单链表中没有数据结点。对应算法如下:intStackEmpty(ListStack*L){ return(L->next==NULL);}

(5)进栈Push(&L,e)

将新数据结点插入到头结点之后。对应算法如下:voidPush(ListStack*&L,ElemTypee){ ListStack*p; p=(ListStack*)malloc(sizeof(ListStack)); p->data=e; p->next=L->next; /*插入*p结点作为第一个数据结点*/ L->next=p;}

(6)出栈Pop(&L,&e)

在栈不为空的条件下,将头结点后继数据结点的数据域赋给e,然后将其删除。对应算法如下:intPop(ListStack*&L,ElemType&e){ ListStack*p; if(L->next==NULL)return0;/*栈空的情况*/ p=L->next; /*p指向第一个数据结点*/ e=p->data; L->next=p->next; free(p); return1;}

(7)取栈顶元素GetTop(L)

在栈不为空的条件下,将头结点后继数据结点的数据域赋给e。对应算法如下:

intGetTop(ListStack*L,ElemType&e){ if(L->next==NULL)return0; /*栈空的情况*/ e=L->next->data; return1;}

(8)显示栈中元素DispStack(L)

从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下:voidDispStack(ListStack*L){ ListStack*p=L->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}3.2栈的应用举例

由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。一、栈的应用举例-----数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)

例如(1348)10=(2504)8，其运算过程如下：

nndiv8nmod8134816841682102125202

voidconversion(){initstack(s);scanf(“%d”,&n);while(n){push(s,n%8);n=n/8;}while(!Stackempty(s)){pop(s,e);printf(“%d”,e);}}二、括号匹配的检验假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（（）］)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：

[([][])]12345678到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”

，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。Statusmatching(string&exp){

intstate=1;

while(i<=Length(exp)&&state){

switchofexp[i]{

case

”(”

:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...三、行编辑程序问题如何实现？“每接受一个字符即存入存储器”?

并不恰当！

设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。

在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。合理的作法是：假设从终端接受了这样两行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);则实际有效的是下列两行：

while(*s)

putchar(*s++);

while(ch!=EOF&&ch!='\n'){

switch(ch){

case'#':Pop(S,c);break;

case'@':ClearStack(S);break;//重置S为空栈

default

:Push(S,ch);break;

}ch=getchar();//从终端接收下一个字符

}ClearStack(S);//重置S为空栈if(ch!=EOF)ch=getchar();while(ch!=EOF){//EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；(这是栈应用的典型例子)

这里，表达式求值的算法是“算符优先法”。例如：3*（7–2）（1）要正确求值，首先了解算术四则运算的规则：

a.

从左算到右

b.先乘除，后加减

c.先括号内，后括号外由此，此表达式的计算顺序为：

3*（7–2）=3*5=15四、栈的应用举例－－表达式计算（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符

1和

2

，都要比较优先权关系。算符优先法所依据的算符间的优先关系见教材P53表3.1

（是提供给计算机用的表！）栈的应用（表达式求值）（3）算法思想：设定两栈：操作符栈OPTR，操作数栈OPND栈初始化：设操作数栈OPND为空；操作符栈OPTR的栈底元素为表达式起始符‘#’；依次读入字符：是操作数则入OPND栈，是操作符则要判断：

if操作符<栈顶元素，则退栈、计算，结果压入OPND栈；

操作符=栈顶元素且不为‘#’，脱括号（弹出左括号）；

操作符>栈顶元素，压入OPTR栈。OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)StatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(compare(c,GetTop(OPTR))){case‘>’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR);c=getchar();break;

case‘<’:op=Pop(OPTR);b=Pop();a=Pop();//退栈

result=Operate(a,op,b);Push(OPND,result);c=getchar();break;}//switch}//whileresult=GetTop(OPND);}//EvaluateExpression此函数在哪里？五、实现递归将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，

需先完成三项任务：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回！例如：voidmain(){voida(){voidb(){……