第三章栈和队列

1、内容提要 1.栈和队列的概念 2.栈和队列的存储结构及它们的应用 3.栈和队列与线性表有着密切的联系,第三章 栈和队列,2,定义：栈(Stack) 是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先出的线性表，简称LIFO线性表 。 允许进行插入和删除的一端称为栈顶(top) 不允许插入和删除的一端称为栈底(bottom) 不含元素的空表称为空栈。 特点：线性结构 后进先出(LIFO)或先进后出（FILO）,栈的基本概念,3,栈的示例图,4,用除法把十进制数转换成二进制数 ，把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）,十进制数35转换成二进制数,例

2、：,5,栈的顺序存储结构(顺序栈),顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，通常用一维数组存放栈的元素。设“指针”top指示栈顶元素的当前位置的后一空位置(下标)。,6,top = 0,（初始，堆栈为空）,记录当前堆栈顶端元素的后一位置的索引值,elemtype elemmaxsize; int top = 0;,top,栈的顺序存储结构(顺序栈),7,顺序栈的类型说明： #define maxsize 100 typedef struct elemtype elemmaxsize; int top; sqstacktp;,栈的顺序存储结构(顺序栈),8,栈顶指针t

3、op,指向实际栈顶后的空位置.,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为maxsize s.top=0,栈空，此时出栈，则下溢 s.top= maxsize,栈满，此时入栈，则上溢,栈空,top,base,base,假设maxsize,顺序栈的几种情况,9,初始化（栈置空）操作 判栈空函数 进栈操作 出栈函数 求栈深函数 读栈顶元函数,顺序栈上实现的操作,10,初始化（栈置空）操作,顺序栈上实现的操作,void ini_sqstack(sqstacktp *s) s-top=0; ,11,判栈空函数,顺序栈上实现的操作,int empty_sqstack(sqstacktp *s

4、) if(s-top0) return(0) ； else return(1)； ,12,进栈操作,顺序栈上实现的操作,void push_sqstack(sqstacktp *s，elemtype x) if(s-top=maxsize) printf(“Overflow”); else s - elems - top=x; /*x进栈*/ s - top+; /*栈顶指针加1*/ ,13,出栈函数,顺序栈上实现的操作,elemtype pop_sqstack(sqstacktp *s) if(s - top=0) return(NULL); else s - top-; /* 栈顶指针减1

5、*/ return(s - elems - top); ,14,求栈深函数,顺序栈上实现的操作,int size_sqstack(sqstacktp *s) return(s - top); ,15,读栈顶元函数,顺序栈上实现的操作,elemtp top_sqstack(sqstacktp *s) if( s - top=0) return(NULL); else return(s - elems - top-1); ,16,栈的链式存储结构,定义：栈的链式存储结构，简称链栈，它的组织形式与单链表类似，链表的尾部结点是栈底，链表的头部结点是栈顶。,17,栈的链式存储结构,链栈的类型定义： ty

6、pedef struct stacknode elemtype data; struct stacknode *next;stacknode; typedef struct stacknode *top; /栈顶指针 linkstack;,18,初始化操作 进栈操作 出栈操作,链栈上实现的操作,19,初始化操作,void init_linkstack(linkstack *ls) /*建立一个空栈ls*/ ls-top=NULL; ,20,进栈操作,void push_linkstack(linkstack *ls,elemtp x) /*将元素x压入栈ls中*/ s=(stacknode*)

7、malloc(sizeof(stacknode); s-data=x; /*生成新结点*/ s - next=ls - top; /*链入新结点*/ ls - top =s; /*修改栈顶指针 ,21,出栈操作,elemtype pop_linkstack(linkstack *ls) stacknode *p; elemtype x; if(ls-top=NULL) return(NULL); else x=(ls - top)-data; p= ls - top; ls-top=p-next; free(p); /*删除栈顶元素*/ return(x); /*返回原栈顶元素值*/ ,22,

8、栈的应用实例表达式求值,对下面的算术表达式求值 1 + 2 * 4 - 9 / 3 必须遵循先乘除后加减、先左后右及先括号内 后括号外的四则运算法则，其计算顺序应为： 1 + 2 * 4 - 9 / 3 ,对表达式求值时，一般设立两个栈，一个称为运算符 栈(OPTR)。另一个称为操作数栈(OPND)，以便分别存 放表达式中的运算符和操作数,23,处理方法: 1、凡遇到操作数，一律进OPND栈 2、若遇到运算符，则比较OPTR栈的栈 顶元素的优先级，若它的优先级高，则进 栈，否则弹出OPTR栈顶的运算符，并从OPND栈连续弹出两个栈顶元素进行运算，并将运算结果压进OPND栈 3、连续1、2两步，

9、直到OPTR 栈为空，此时OPND栈的内容即为表达式的运算结果,24,步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # 1+2*4-9/3# PUSH(OPND,1) 2 # 1 +2*4-9/3# PUSH(OPTR,+) 3 # + 1 2*4-9/3# PUSH(OPND,2) 4 # + 1 2 *4-9/3# PUSH(OPTR,*) 5 # + * 1 2 4-9/3# PUSH(OPND,4) 6 # + * 1 2 4 -9/3# operate(2,*,4) 7 # + 1 8 -9/3# operate(1,+,8) 8 # 9 -9/3# PUSH(OPTR,-)

10、 9 # - 9 9/3# PUSH(OPND,9) 10 # - 9 9 /3# PUSH(OPTR,/) 11 # - / 9 9 3# PUSH(OPND,3) 12 # - / 9 9 3 # operate(9,/,3) 13 # - 9 3 # operate(9,-,3) 14 # 6 # RETURN(TOP(OPND) ,利用算法对算术表达式1+2*4-9/3求值的操作过程,25,栈的应用,函数调用和返回 递归调用,26,队列,27,定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)允许插入的一端 队头(front)允许删除的一端 队列特点

11、：先进先出(FIFO)或后进后出(LILO),队列,28,队列的顺序存储结构,定义：队列的顺序存储结构，简称顺序队列，它是由一个存放队列中元素的一维数组，及分别指示队头和队尾的“指针”所组成。,29,队列的顺序存储结构如下图所示：,-1 0 1 2 3 n-1,front：队头元素的前一个索引值,rear：队尾元素的索引值,队列的顺序存储结构,30,C,B,elem,尾指针 rear,头指针 front,顺序队列的类型定义： #define maxsize 100 typedef struct elemtype elemmaxsize; int rear,front; squeuetp;,队列

12、的顺序存储结构,31,J1,J2,J3,设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=-1,空队列条件：front=rear 入队列：sq+rear=x; 出队列：x=sq+front;,顺序队列的几种状态,32,顺序队列上实现的操作,初始化操作 进队操作 出队操作,33,初始化操作,void ini_squeue(squeuetp *sq) sq-front=-1; sq-rear=-1; ,34,入队函数,void add_squeue (squeue *sq,elemtype x) if(sq - rear=(m

13、axsize1) printf(“Overflow”); else sq- rear+; /* 队尾指针加1*/ sq-elemsq -rear= x; ,35,出队函数,elemtype del_squeue (squeue *sq) if(sq - front=sq-rear) return(NULL); else sq- front+; /* 队头指针加1*/ return(sq-elems -front); ,36,顺序队列存在的问题 设数组大小为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出真溢出 当front-1,rear=M-1时，再有元素入队发生溢出假溢

14、出,循环队列的引入,37,数组仿真队列中的“假溢出”,38,解决方案循环队列 基本思想：把队列设想成环形，让sq0接在sqmaxsize-1 之后，若rear+1=maxsize,则令rear=0;,循环队列的引入,39,按照逆时针方向循环,a5,a6,a8,a7,0,1,2,3,4,5,6,7,rear,front,40,实现：利用“模”运算 入队： rear=(rear+1)%M; sqrear=x; 出队： front=(front+1)%M; x=sqfront; 新问题：队满、队空判定条件,41,front,初始状态,队空：front=rear 队满：front=rear,解决方案：

15、 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front,42,循环队列的定义为： #define m #define maxsize m typedof struct elemtp elemmaxsize; int front,rear; cqueuetp；,43,在循环队列上实现的操作,队列的初始化操作 判队空函数 求队长度函数 读队头元素函数 入队列操作函数 出队列函数,44,队列的初始化操作,void init_cqueue(cqueuetp *cq) /设置cq为空的循环队列 cq-front=0; cq-rea

16、r=0; ,45,队列判空函数,int empty_cqueue(cqueuetp *cq) if (cq-rear=cq-front) return(1); else return(0); ,46,求队列长度,int size_cqueue(cqueuetp *cq) return(maxsize+cq-rear-cq-front) % maxsize); ,47,读队头元素,elemtp head_cqueue(cqueuetp *cq) /若循环队列cq不空，则返回队头元素值；否则返回空元素NULL if(cq-front=cq - rear) return(NULL); else re

17、turn(cq - elem(cq - front+1) % maxsize); ,48,入队列,void en_cqueue(cqueuetp *cq,elemtp x) /若循环队列cq未满，插入x为新的队尾元素；否则队列状态不变并给出错误信息 if (cq-rear+1)%maxsize=cq-front) printf(Overflow); else cq-rear=(cq-rear+1)%maxsize; cq-elemcq-rear=x; ,49,出队列,void dl_cqueue(cqueuetp *cq,elemtp x) /若循环队列cq未满，插入x为新的队尾元素；否则队列

18、状态不变并给出错误信息 if(cq-front=cq-rear) return(NULL); else cq-front=(cq-front+1)%maxsize; return(cq-elemcq-front); ,50,队列的链式存储结构,定义:队列的链式存储结构，简称链队列,它实际上是一个同时带有头指针和尾指针的单链表，头指针指向头结点，尾指针指向队尾结点,51,设队首、队尾指针front和rear, front指向头结点，rear指向队尾,52,typedef struct elemtp data; nodetype *next; nodetype;,链队列的类型定义,typedef

19、struct nodetype *front; nodetype *rear; lqueuetp;,53,在链队列上实现的操作,初始化操作的实现 判队空函数 求队长度函数 读队头元素函数 入队列操作 出队列操作,54,初始化操作,void init_lqueue( lqueuetp *lq) /设置一个空的链队列lq lq-front=( nodetype*) malloc(sizeof(nodetype); lq-front-next=NULL; lq-rear=lq-front; ,55,判空操作,int empty_lqueue(lqueuetp *lq) if (lq-front=lq

20、-rear) return(1); else return(0); ,56,求队长,int size_lqueue(lqueuetp *lq) /返回队列中元素个数 int i=0; nodetype *p; p=(lq-front)-next; while (p!=NULL) p=p-next; i=i+1; return(i); ,57,读队头元素,elemtp head_lqueue(lqueuetp *lq) /若链队列lq不空，则返回队头元素值；否则返回空元素NULL if( lq-front=lq-rear) return(NULL);/返回无效值 else return (lq-front-next-data); ,58,入队列,void en_lqueue(queuetp *lq;elemtp x) /在链队列lq中，插入x为新的队尾元素 nodetype *s; s=(nodetype*)malloc(sizeof(nodetype); s-data=x; s-n