数据结构第3章栈和队列课件

第3章栈和队列3.1栈的概念

3.2栈的存储结构3.3顺序栈的操作算法

3.4链栈的操作算法

3.5栈的应用举例---表达式求值第3章栈和队列3.6队列的概念

3.7队列的存储结构

3.8循环队列的操作算法

3.9链队的操作算法

第三章栈和队列

3.1栈的概念1.定义：栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表。2.栈的示意图P443.栈的抽象数据类型定义P451、顺序栈

顺序栈的类型定义：//------栈的顺序存储表示------

#defineSTACK_NINT_SIZE100;//存储空间初始分配量

#defineSTACKINCREMENT10;//存储空间分配增量

typedefstruct{

SElemType*base;//在栈构造之前和销毁之后，base的值为NULL

SElemType*top;//栈顶指针

intstacksize;//当前已分配的存储空间，以元素为单位

}SqStack顺序栈的结构举例2、链栈

链栈的类型定义：typedefstructLNode{//结点类型

ElemTypedata;

structLNode*next;

}Lnode,*Linkstack;

LinkstackS;

3.3顺序栈的操作算法1建立一个空栈

StatusInitStack(SqStack&S){

//构造一个空栈S

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(overflow);//存储分配失效

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}//InitStack3.压栈push

StatusPush(SqStack&S,SElemTypee){

//插入元素e为新的栈顶元素

if(S.top-S.base>=S.stacksize){//栈满，追加存储空间

S.base=(SElemType*)realloc(S.base,

(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;}//push

4.出栈pop

statusPop(SqStack&S,SElemType&e){

//若栈不为空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR

if(S.top==S.base)returnERROR;

e=*--S.top;

returnOK;

}//Pop5判断栈是否为空intEmpty(SqStackS)

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

if(s.top==s.base)return(0);

elsereturn(1);

}6判断栈是否为满intFull(SqStackS)

{//若栈为满，则返回0，否则返回1

if(s.top-s.base)>=s.stacksizereturn(0);

elsereturn(1);

}2.取栈顶元素StatusGettopLStack(Linkstack&S,SElemType&e){

//若栈不为空，则用e返回S的栈顶元素，并返回OK,否则返回ERROR.

if(S==NULL)returnERROR;

e=S->data;

return(OK);

}//GettopLStack3.压栈PushStatusPushLStack(Linkstack&S,SElemTypee){

//插入元素e为新的栈顶元素

Lnode*p;

p=(Lnode*)malloc(sizeof(Lnode));

p->data=e;

p->next=S;

S=p;

}//PushLStack4.出栈PopStatusPopLStack(Linkstack&S,SElemType&e){

//若栈不为空，则删除S的栈顶元素，

用e返回其值，并返回OK，否则返回ERROR

if(s==NULL)returnERROR;

e=S->data;

S=S->link;

returnOK;

}//PopLStack3.5栈的应用举例1---数制转换非负十进制整数转换为八进制数1348D＝2504ONNDIV8NMOD81348168416821021252023.5栈的应用举例2---表达式求值算法的基本思想是：

（1）首先置操作数栈为空栈，表达式起始符“#”为运算符的栈底元素；

（2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优符后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。算法描述：p53-54算法3.4表达式求值举例：计算3*(7-2)步骤OPTR栈OPND栈输入字符主要操作说明1＃

3*(7-2)#push(opnd,'3')＃<32＃3*(7-2)#push(optr,'*')3<*3＃*3(7-2)#push(optr,'(')*<(4＃*(37-2)#push(opnd,'7')7为操作数5＃*(37-2)#push(optr,'-')(<-6＃*(-372)#push(opnd,'2')2为操作数7＃*(-372)#operate('7','-','2')-'>')'8＃*(35)#pop(optr)(=)9＃*35#operate('3','*','5')*>#10＃15#返回15＃

＝

＃3、队列的抽象数据类型定义

队列的抽象数据类型定义：ADTQueue{

数据对象：D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定其中a1端为队列头,an为队列尾。

基本操作：

InitQueue(&Q)

操作结果：构造一个空队列Q。

DestroyQueue(&Q)……}ADTQueue4、双端队列

a定义：双端队列是限定插入和删除操作在表的两端进行的线性表。

b双端队列的示意图3.8循环队列的操作算法

1、循环队列的基本思想：

在顺序队列中，头指针front始终指向队列头元素，而尾指针rear始终指向队列尾元素的下一个位置，随着进队、出队操作的进行，有可能会出rear指针已到达队列存储空间的终点，而队列的实际可用空间并未占满现象。为了避免这种现象的发生，一个巧妙的办法是将顺序队列臆造为一个环状空间，称之为循环队列。如图所示：2、循环队列的队空队满条件

为了方便起见，约定：初始化建空队时，令

front=rear=0,

当队空时：front=rear

当队满时：front=rear亦成立

因此只凭等式front=rear无法判断队空还是队满。

有两种方法处理上述问题：

（1）另设一个标志位以区别队列是空还是满。

（2）少用一个元素空间，约定以“队列头指针

front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即：

队空时：front=rear

队满时：(rear+1)%maxsize=front3、循环队列的类型定义：

//------循环队列---队列的顺序存储结构----

#defineMAXQSIZE100//最大队列长度

typedefstruct{

QELemType*base;//初始化的动态分配存储空间

intfront;//头指针(下标)，若队列不空，

指向队列头元素

intrear;//尾指针(下标)，若队列不空，

指向队列尾元素的下一个位置

}SqQueue;4、建立空的循环队列的算法

StatusInitQueue(SqQueue&Q){

//构造一个空队列Q

Q.base=(QElemType*)malloc(MAXQSIZE

*sizeof(QElemType));

if(!Q.base)exit(OVERFLOW);//存储分配失败

Q.front=Q.rear=0;

returnOK;

}5、求循环队列中元素的个数

intQueueLength(SqQueueQ){

//返回Q的元素个数，即队列的长度

return

(Q.rear-Q.front+MAXQSIZE)

%MAXQSIZE;

}求循环队列中元素的个数举例(参考图3.14）Q.REARQ.FRONT队列长度MAXSIZE00063456152610166、进队算法

StatusEnQueue(SqQueue&Q,QElemTypee){

//插入元素为Q的新的队尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)return

ERROR;//队列满

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;

returnOK;

}

7、出队算法

StatusDeQueue(SqQueue&Q,QElemType&e){

//若队列不空，则删除Q的队头元素，

用e返回其值，并返回OK；否则返回ERROR

if(Q.front==Q.rear)returnERROR;

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

returnOK;

}3、9链队的操作算法

1、链队的类型定义

//-----单链队列---队列的链式存储结构----

typedefstructQNode{

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct{

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针

}LinkQueue;2、建立空的链队

StatusInitQueue(LinkQueue&Q){

//构造一个空队列Q

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);

Q.front->next=NULL;

returnOK;

}3、进队算法

StatusEnQueue(LinkQueue&Q,QElemTypee){

//插入元素e为Q的新的队尾元素

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)exit(OVERFLOW);

p->data=e;p->next=NULL;

Q.rear->next=p;

Q.rear=p;

r