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

1、 第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.栈的抽

2、象数据类型定义栈的抽象数据类型定义 P453.2 栈的存储结构栈的存储结构有两种存储结构有两种存储结构:顺序顺序栈（常用）；栈（常用）；链链栈栈1、顺序栈、顺序栈 顺序栈的类型定义：顺序栈的类型定义：/-栈的顺序存储表示栈的顺序存储表示-#define STACK_NINT_SIZE 100;/存储空间初始分配量存储空间初始分配量#define STACKINCREMENT 10;/存储空间分配增量存储空间分配增量typedef struct SElemType*base;/在栈构造之前和销毁之后，在栈构造之前和销毁之后，base的值为的值为NULL SElemType*top;/栈顶指针栈顶

3、指针 int stacksize;/当前已分配的存储空间，以元素为单位当前已分配的存储空间，以元素为单位SqStack顺序栈的结构举例顺序栈的结构举例/-基本操作的函数原型说明基本操作的函数原型说明-Status InitStack(SqStack&S);/构造一个空栈构造一个空栈SStatus GetTop(SqStack S,SElemType&e);/若栈不空，则用若栈不空，则用e返回返回S的栈顶元素，并返回的栈顶元素，并返回OK；否则返回；否则返回ERRORStatus Push(SqStack&S,SElemType e);/插入元素插入元素e为新的栈顶元素为新的栈顶元素Status

4、 Pop(SqStack&S,SElemType&e);/若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用e返回其值，并返回返回其值，并返回OK；否则返回否则返回ERROR 2、链栈、链栈 链栈的类型定义：链栈的类型定义：typedef struct LNode/typedef struct LNode/结点类型结点类型 ElemType data;ElemType data;struct LNode struct LNode*next;next;Lnode,Lnode,*Linkstack;Linkstack;Linkstack S;Linkstack S;3.3 顺序栈的操作

5、算法顺序栈的操作算法 1建立一个空栈建立一个空栈Status InitStack(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;return OK;/InitStack2.取栈顶元素取栈顶元素Status GetTop(SqStack S,SElemType&e)/若栈不空，则用若栈不空，则用e返回返回S的栈顶元

6、素，的栈顶元素，并返回并返回OK；否则返回；否则返回ERROR if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;/GetTop 3.压栈压栈pushStatus Push(SqStack&S,SElemType e)/插入元素插入元素e为新的栈顶元素为新的栈顶元素 if(S.top-S.base=S.stacksize)/栈满，追加存储空间栈满，追加存储空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base

7、)exit(OVERFLOW);/存储分配失败存储分配失败 S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/push 4.出栈出栈popstatus Pop(SqStack&S,SElemType&e)/若栈不为空，则删除若栈不为空，则删除S的栈顶元素，用的栈顶元素，用e返回其值，并返回其值，并返回返回OK；否则返回；否则返回ERROR if(S.top=S.base)return ERROR;e=*-S.top;return OK;/Pop 5 判断栈是否为空判断栈是否为空int Empty(

8、SqStack S)/若栈为空，则返回若栈为空，则返回0，否则返回，否则返回1 if(s.top=s.base)return(0);else return(1);6 判断栈是否为满判断栈是否为满int Full(SqStack S)/若栈为满，则返回若栈为满，则返回0，否则返回，否则返回1 if(s.top-s.base)=s.stacksize return(0);else return(1);3.4 链栈的操作算法链栈的操作算法（自学）（自学）1.建立一个空栈（不带头结点）建立一个空栈（不带头结点）Status InitLStack(Linkstack&S)S=NULL;return ok

9、;/InitLStack2.2.取栈顶元素取栈顶元素Status GettopLStack(Linkstack&S,SElemType&e)/若栈不为空，则用若栈不为空，则用e返回返回S的栈顶元素，并返回的栈顶元素，并返回OK,否则返回否则返回ERROR.if(S=NULL)return ERROR;e=S-data;return(OK);/GettopLStack 3.3.压栈压栈PushPushStatus PushLStack(Linkstack&S,SElemType e)Status PushLStack(Linkstack&S,SElemType e)/插入元素插入元素e e为新的

10、栈顶元素为新的栈顶元素Lnode Lnode*p;p;p=(Lnode p=(Lnode*)malloc(sizeof(Lnode);)malloc(sizeof(Lnode);p-data=e;p-data=e;p-next=S;p-next=S;S=p;S=p;/PushLStack/PushLStack 4.4.出栈出栈PopPopStatus PopLStack(Linkstack&S,SElemType&e)/若栈不为空，则删除若栈不为空，则删除S的栈顶元素，的栈顶元素，用用e返回其值，并返回返回其值，并返回OK，否则返回，否则返回ERROR if(s=NULL)return ERR

11、OR;e=S-data;S=S-link;return OK;/PopLStack 5.判断栈是否为空判断栈是否为空int link_empty(Linkstack&S)/若栈为空则返回若栈为空则返回1，否则返回，否则返回0 if(S=NULL)return(1);else retrun(0);3.5 3.5 栈的应用举例栈的应用举例1-1-数制转换数制转换非负十进制整数转换非负十进制整数转换为八进制数为八进制数 1348D 2504ON N DIV 8N MOD 81348168416821021252023.5 3.5 栈的应用举例栈的应用举例2-2-表达式求值表达式求值算法的基本思想是：

12、算法的基本思想是：（1 1）首先置操作数栈为空栈，表达式起始符）首先置操作数栈为空栈，表达式起始符“#”“#”为为运算符的栈底元素；运算符的栈底元素；（2 2）依次读入表达式中每个字符，若是操作数则进）依次读入表达式中每个字符，若是操作数则进OPNDOPND栈，若是运算符，则和栈，若是运算符，则和OPTROPTR栈的栈顶运算符比较优符栈的栈顶运算符比较优符后作相应操作，直至整个表达式求值完毕（即后作相应操作，直至整个表达式求值完毕（即OPTROPTR栈栈的栈顶元素和当前读入的字符均为的栈顶元素和当前读入的字符均为“#”“#”）。）。算法描述：算法描述：p53-54 p53-54 算法算法3.4

13、 3.4 表达式求值举例：计算表达式求值举例：计算3 3*(7-2)(7-2)步骤步骤OPTR栈栈OPND栈栈输入字符输入字符主要操作主要操作说明说明13*(7-2)#push(opnd,3)323*(7-2)#push(optr,*)3 *3*3 (7-2)#push(optr,()*(4*(3 7-2)#push(opnd,7)7为操作数为操作数5*(37 -2)#push(optr,-)()8*(35 )#pop(optr)(=)9*35#operate(3,*,5)*#1015#返回返回15 3.63.6队列的概念队列的概念1 1、定义定义：队列是一种先进先出：队列是一种先进先出（FI

14、FOFIFO：First In First Out)First In First Out)的的线性表。它只允许在表的一端进行插入，而在另一端删除元素。线性表。它只允许在表的一端进行插入，而在另一端删除元素。2、示意图示意图 3、队列的抽象数据类型定义队列的抽象数据类型定义 队列的抽象数据类型定义：队列的抽象数据类型定义：ADT Queue 数据对象：数据对象：D=ai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1=|ai-1,aiD,i=2,.,n 约定其中约定其中a1端为队列头端为队列头,an为队列尾。为队列尾。基本操作：基本操作：InitQueue(&Q)操作结果

15、：构造一个空队列操作结果：构造一个空队列Q。DestroyQueue(&Q)ADT Queue4、双端队列双端队列a 定义：双端队列是限定插入和删除操作在表的两端进行的线性表。b 双端队列的示意图3.7队列的存储结构队列的存储结构3.8循环队列的操作算法循环队列的操作算法 1、循环队列的基本思想、循环队列的基本思想：在顺序队列中，头指针在顺序队列中，头指针front始终指向队列头元始终指向队列头元素，而尾指针素，而尾指针rear始终指向队列尾元素的下一个位置，始终指向队列尾元素的下一个位置，随着进队、出队操作的进行，有可能会出随着进队、出队操作的进行，有可能会出rear指针已到指针已到达队列存

16、储空间的终点，而队列的实际可用空间并未占达队列存储空间的终点，而队列的实际可用空间并未占满现象。为了避免这种现象的发生，一个巧妙的办法是满现象。为了避免这种现象的发生，一个巧妙的办法是将顺序队列臆造为一个环状空间，称之为循环队列。将顺序队列臆造为一个环状空间，称之为循环队列。如图所示：如图所示：2、循环队列的队空队满条件、循环队列的队空队满条件 为了方便起见，约定：初始化建空队时，令为了方便起见，约定：初始化建空队时，令 front=rear=0,当队空时：当队空时：front=rear 当队满时：当队满时：front=rear 亦成立亦成立 因此只凭等式因此只凭等式front=rear无法判

17、断队空还是队满。无法判断队空还是队满。有两种方法处理上述问题：有两种方法处理上述问题：（1）另设一个标志位以区别队列是空还是满。）另设一个标志位以区别队列是空还是满。（2 2）少用一个元素空间，约定以）少用一个元素空间，约定以“队列头指针队列头指针 frontfront在队尾指针在队尾指针rearrear的下一个位置上的下一个位置上”作为队作为队列列“满满”状态的标志。状态的标志。即：即：队空时：队空时：front=rear 队满时：队满时：(rear+1)%maxsize=front 3、循环队列的类型定义：、循环队列的类型定义：/-循环队列循环队列-队列的顺序存储结构队列的顺序存储结构-#

18、define MAXQSIZE 100/最大队列长度最大队列长度typedef struct QELemType*base;/初始化的动态分配存储空初始化的动态分配存储空间间 int front;/头指针头指针(下标下标)，若队列不空，若队列不空，指向队列头元素指向队列头元素 int rear;/尾指针尾指针(下标下标)，若队列不空，若队列不空，指向队列尾元素的下一个位置指向队列尾元素的下一个位置SqQueue;4、建立空的循环队列的算法、建立空的循环队列的算法Status InitQueue(SqQueue&Q)/构造一个空队列构造一个空队列Q Q.base=(QElemType*)mall

19、oc(MAXQSIZE *sizeof(QElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败存储分配失败 Q.front=Q.rear=0;return OK;5、求循环队列中元素的个数、求循环队列中元素的个数int QueueLength(SqQueue Q)/返回返回Q的元素个数，即队列的长度的元素个数，即队列的长度 return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;求循环队列中元素的个数举例求循环队列中元素的个数举例(参考图参考图3.14）Q.REAR Q.FRONT队列长度队列长度MAXSIZE00063456152

20、610166、进队算法、进队算法Status EnQueue(SqQueue&Q,QElemType e)/插入元素为插入元素为Q的新的队尾元素的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/队列满队列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;7、出队算法、出队算法Status DeQueue(SqQueue&Q,QElemType&e)/若队列不空，则删除若队列不空，则删除Q的队头元素，的队头元素，用用e返回其值，并返回返回其值，并返回OK；否则返回；否则返回ERROR

21、if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;3、9 链队的操作算法链队的操作算法 1、链队的类型定义、链队的类型定义/-单链队列单链队列-队列的链式存储结构队列的链式存储结构-typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针队头指针 QueuePtr rear;/队尾指针队尾指针LinkQueue;2、建立空

22、的链队、建立空的链队Status InitQueue(LinkQueue&Q)/构造一个空队列构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK;3、进队算法、进队算法Status EnQueue(LinkQueue&Q,QElemType e)/插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;4、出队算法、出队算法Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除若队列不空，则删除Q的队头元素，的队头元素，用用e返回其值，并返回返回其值，并返回OK；否则返回；否则返回ERROR if(Q.front=Q.rear)return ERROR;p=Q.front-nxet;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;