第三章 栈和队列

1、内容提要内容提要1.栈和队列的概念栈和队列的概念 2.栈和队列的存储结构及它们的应用栈和队列的存储结构及它们的应用 3.栈和队列与线性表有着密切的联系栈和队列与线性表有着密切的联系 第三章第三章 栈和队列栈和队列 2定义：定义：栈栈(stack) 是限制仅在表的一端进行插是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先入和删除操作的线性表。栈又称为后进先出的线性表，简称出的线性表，简称lifo线性表线性表 。 允许进行插入和删除的一端称为栈顶允许进行插入和删除的一端称为栈顶(top) 不允许插入和删除的一端称为栈底不允许插入和删除的一端称为栈底(bottom) 不含元素的空表称为空

2、栈。不含元素的空表称为空栈。特点：特点：线性结构线性结构 后进先出后进先出(lifo)或或先进后出先进后出（filo）栈的基本概念栈的基本概念3栈的示例图栈的示例图12345进出a5a2a1a4a3栈底栈顶进栈出栈4用除法把十进制数转换成二进制数用除法把十进制数转换成二进制数 ，把所有的，把所有的余数按出现的逆序排列起来（余数按出现的逆序排列起来（先出现的余数排先出现的余数排在后面，后出现的余数排在前面在后面，后出现的余数排在前面）,十进制数十进制数35转换成二进制数转换成二进制数 35178421011001余数余数结果：结果：10011例：例：5 栈的顺序存储结构栈的顺序存储结构(顺序栈顺

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

4、顺序栈的类型说明：#define maxsize 100typedef struct elemtype elemmaxsize; int top; sqstacktp;栈的顺序存储结构栈的顺序存储结构(顺序栈顺序栈)8base123450栈空栈空栈顶指针栈顶指针top,指向实际指向实际栈顶栈顶后的空位置后的空位置.top123450进栈进栈atop出栈出栈栈满bcdef设数组维数为设数组维数为maxsizes.top=0,栈空，此时出栈，则栈空，此时出栈，则下溢下溢s.top= maxsize,栈满，此时入栈，则栈满，此时入栈，则上溢上溢toptoptoptoptop123450abcdeft

5、optoptoptoptoptop栈空topbasebase假设maxsize顺序栈的几种情况顺序栈的几种情况9u初始化（栈置空）操作初始化（栈置空）操作u判栈空函数判栈空函数 u进栈操作进栈操作u出栈函数出栈函数 u求栈深函数求栈深函数u读栈顶元函数读栈顶元函数顺序栈上实现的操作顺序栈上实现的操作10初始化（栈置空）操作初始化（栈置空）操作顺序栈上实现的操作顺序栈上实现的操作void ini_sqstack(sqstacktp *s) s-top=0; 11判栈空函数判栈空函数顺序栈上实现的操作顺序栈上实现的操作int empty_sqstack(sqstacktp *s) if(s-top

6、0) 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 -

7、top-; /* 栈顶指针减栈顶指针减1*/ 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栈的链式存储结构栈的链式存储结构定义：定义：栈的链式存储结构，简称链栈，它栈的链式存储结构，

8、简称链栈，它的组织形式与单链表类似，链表的尾部结的组织形式与单链表类似，链表的尾部结点是栈底，链表的头部结点是栈顶。点是栈底，链表的头部结点是栈顶。 17栈的链式存储结构栈的链式存储结构ftopdatanextedanull栈顶栈顶栈底栈底 链栈的类型定义：链栈的类型定义： typedef struct stacknode elemtype data; struct stacknode *next; stacknode;typedef struct stacknode *top; /栈顶指针栈顶指针 linkstack;18u初始化操作初始化操作u进栈操作进栈操作u出栈操作出栈操作链栈上实现的

9、操作链栈上实现的操作19初始化操作初始化操作void init_linkstack(linkstack *ls) /*建立一个空栈建立一个空栈ls*/ ls-top=null; 20进栈操作进栈操作void push_linkstack(linkstack *ls,elemtp x) /*将元素将元素x压入栈压入栈ls中中*/ s=(stacknode*)malloc(sizeof(stacknode); s-data=x; /*生成新结点生成新结点*/ s - next=ls - top; /*链入新结点链入新结点*/ ls - top =s; /*修改栈顶指针修改栈顶指针 21出栈操作出栈

10、操作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 对下面的算术表达式求值对下面的算术表达式求值 1 + 2 * 4 - 9 / 3 必须遵循先乘除后加减、先左后右及先括号内必须遵循先乘除后加减、先左后右及先括号内 后括号外的四则运算法

11、则，其计算顺序应为：后括号外的四则运算法则，其计算顺序应为： 1 + 2 * 4 - 9 / 3 对表达式求值时，一般设立两个栈，一个称为运算符对表达式求值时，一般设立两个栈，一个称为运算符栈栈(optr)。另一个称为操作数栈。另一个称为操作数栈(opnd)，以便分别存，以便分别存放表达式中的运算符和操作数放表达式中的运算符和操作数23处理方法处理方法: 1、凡遇到操作数，一律进、凡遇到操作数，一律进opnd栈栈 2、若遇到运算符，则比较、若遇到运算符，则比较optr栈的栈栈的栈 顶元素的优先级，若它的优先级高，则进顶元素的优先级，若它的优先级高，则进 栈，栈，否则弹出否则弹出optr栈顶的运

12、算符，并从栈顶的运算符，并从opnd栈连续弹出两个栈顶元素进行运算，并将运栈连续弹出两个栈顶元素进行运算，并将运算结果压进算结果压进opnd栈栈 3、连续、连续1、2两步，直到两步，直到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,*)

13、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,-) 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) 利用算法对算术表达式

14、利用算法对算术表达式1+2*4-9/3求值的操作过程求值的操作过程25l函数调用和返回函数调用和返回l递归调用递归调用26a1 a2 a3.an 入队入队出队出队frontrear队列队列q=(a1,a2,an)队列队列27l定义：定义：队列是限定只能在表的一端进行插入，队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表在表的另一端进行删除的线性表队尾队尾(rear)允许插入的一端允许插入的一端队头队头(front)允许删除的一端允许删除的一端l队列特点：队列特点：先进先出先进先出(fifo)或后进后出或后进后出(lilo)队列队列28队列的顺序存储结构队列的顺序存储结构 定义：定

15、义：队列的顺序存储结构，简称顺序队队列的顺序存储结构，简称顺序队列，它是由一个存放队列中元素的一维数组，列，它是由一个存放队列中元素的一维数组，及分别指示队头和队尾的及分别指示队头和队尾的“指针指针”所组成。所组成。 29l队列的顺序存储结构如下图所示：队列的顺序存储结构如下图所示：a1 a2 a3 a4 an -1 0 1 2 3 n-1front：队头元素的：队头元素的前一个前一个索索引值引值rear：队尾元素的索引值：队尾元素的索引值队列的顺序存储结构队列的顺序存储结构 30cbelem尾指针尾指针rear头指针头指针front 顺序队列的类型定义：顺序队列的类型定义： #define

16、maxsize 100typedef struct elemtype elemmaxsize; int rear,front; squeuetp;队列的顺序存储结构队列的顺序存储结构 31front=-1rear=-1123450队空队空123450frontj1,j1,j3入队入队j1j2j3rearrear123450j4,j5,j6入队入队j4j5j6front设两个指针设两个指针front,rear,约定约定：rear指示队尾元素；指示队尾元素；front指示指示队头元素前一位置队头元素前一位置初值初值front=rear=-1空队列条件：空队列条件：front=rear入队列：入队列

17、：sq+rear=x;出队列：出队列：x=sq+front;rearrearfrontrear123450j1,j2,j3出队出队j1j2j3frontfrontfront 顺序队列的几种状态顺序队列的几种状态 32顺序队列上实现的操作顺序队列上实现的操作u初始化操作初始化操作u进队操作进队操作u出队操作出队操作33初始化操作初始化操作void ini_squeue(squeuetp *sq) sq-front=-1; sq-rear=-1; 34入队函数入队函数void add_squeue (squeue *sq,elemtype x) if(sq - rear=(maxsize1) pr

18、intf(“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); 36l顺序队列存在的问题顺序队列存在的问题设数组大小为设数组大小为m m，则：，则：当当front=-1,rear=m-1front=-1,rear=m-1时，再有元素入时，再有元

19、素入队发生溢出队发生溢出真溢出真溢出当当frontfront -1,rear=m-1-1,rear=m-1时，再有元素入时，再有元素入队发生溢出队发生溢出假溢出假溢出循环队列的引入循环队列的引入37数组仿真队列中的数组仿真队列中的“假溢出假溢出”01234567a5a6a7a8frontrear38l解决方案循环队列 基本思想：把队列基本思想：把队列设想成环形设想成环形，让，让sq0sq0接在接在sqmaxsize-1 sqmaxsize-1 之后，若之后，若rear+1=maxsizerear+1=maxsize, ,则令则令rear=0;rear=0;循环队列的引入循环队列的引入39按照逆

20、时针方向循环按照逆时针方向循环a5a6a8a701234567rearfront40l实现：利用实现：利用“模模”运算运算l入队：入队： rear=(rear+1)%m; rear=(rear+1)%m; sqrearsqrear=x;=x;l出队：出队： front=(front+1)%m; front=(front+1)%m; x=sqfrontx=sqfront;l新问题：新问题：队满、队空判定条件队满、队空判定条件41front012345rearj4j5j6012345rearfrontj9j8j7j4j5j6012345rearfront初始状态j4,j5,j6出队出队j7,j8,

21、j9入队入队队空：队空：front=rear队满：队满：front=rear解决方案：解决方案：1.另外设一个标志以区别队空、队满另外设一个标志以区别队空、队满2.少用一个元素空间少用一个元素空间： 队空：队空：front=rear 队满：队满：(rear+1)%m=front42循环队列的定义为：循环队列的定义为： #define m #define maxsize m typedof struct elemtp elemmaxsize; int front,rear; cqueuetp； 43在循环队列上实现的操作在循环队列上实现的操作 u队列的初始化操作队列的初始化操作u判队空函数判队空

22、函数u求队长度函数求队长度函数u读队头元素函数读队头元素函数u入队列操作函数入队列操作函数u出队列函数出队列函数44队列的初始化操作队列的初始化操作void init_cqueue(cqueuetp *cq) /设置设置cq为空的循环队列为空的循环队列 cq-front=0; cq-rear=0; 45队列判空函数队列判空函数int empty_cqueue(cqueuetp *cq) if (cq-rear=cq-front) return(1);elsereturn(0); 46求队列长度求队列长度int size_cqueue(cqueuetp *cq)return(maxsize+cq

23、-rear-cq-front) % maxsize); 47读队头元素读队头元素elemtp head_cqueue(cqueuetp *cq) /若循环队列若循环队列cq不空，则返回队头元素值；不空，则返回队头元素值；否则返回空元素否则返回空元素null if(cq-front=cq - rear) return(null); else return(cq - elem(cq - front+1) % maxsize); 48入队列入队列void en_cqueue(cqueuetp *cq,elemtp x) /若循环队列若循环队列cq未满，插入未满，插入x为新的队尾为新的队尾元素；否则队

24、列状态不变并给出错误信息元素；否则队列状态不变并给出错误信息 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为新的队尾为新的队尾元素；否则队列状态不变并给出错误信息元素；否则队列状态不变并给出错误信息 if(cq-front=cq-rear) return(null); else cq-front=

25、(cq-front+1)%maxsize; return(cq-elemcq-front); 50队列的链式存储结构队列的链式存储结构 定义定义: :队列的链式存储结构，简队列的链式存储结构，简称链队列称链队列, ,它实际上是一个同时它实际上是一个同时带有头指针和尾指针的单链表，带有头指针和尾指针的单链表，头指针指向头结点，尾指针指头指针指向头结点，尾指针指向队尾结点向队尾结点51头结点头结点 .front队头队头队尾队尾rear设队首、队尾指针设队首、队尾指针front和和rear,front指向头结点，指向头结点，rear指向队尾指向队尾52typedef structelemtp dat

26、a; nodetype *next;nodetype;链队列的类型定义链队列的类型定义typedef structnodetype *front;nodetype *rear;lqueuetp;53在链队列上实现的操作在链队列上实现的操作 u初始化操作的实现初始化操作的实现u判队空函数判队空函数u求队长度函数求队长度函数u读队头元素函数读队头元素函数u入队列操作入队列操作u出队列操作出队列操作54初始化操作初始化操作void init_lqueue( lqueuetp *lq) /设置一个空的链队列设置一个空的链队列lq lq-front=( nodetype*) malloc(sizeof(

27、nodetype); lq-front-next=null; lq-rear=lq-front; 55判空操作判空操作int empty_lqueue(lqueuetp *lq) if (lq-front=lq-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

28、 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-next=null; lq-rear-next=s; lq-rear=s; 59elemtp dl_lqueue(lqueuetp *lq) /若链队列若链队列lq不空，则删去队头元素并返回元素值；不空，则删去队头元素并返回元素值；否则返回空元素否则返回空元素null if(lq-fro