第三章 堆栈和队列

1、3.1 堆栈堆栈（Stack） 3.2 队列队列（Queue）1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式本章内容3.1 堆栈一、堆栈的基本概念一、堆栈的基本概念 定义定义 堆栈是限定只能在表的堆栈是限定只能在表的一端进行插入和删除的一端进行插入和删除的线性表。在表中允许插线性表。在表中允许插入和删除的一端叫做入和删除的一端叫做栈栈顶顶(top)(top)；表的另一端；表的另一端则叫做则叫做栈底栈底(base)(base)。 出栈或出栈

2、或退栈退栈入栈或入栈或进栈进栈a0a1an-2an-1basetopLast In First Out一般线性表一般线性表逻辑结构：逻辑结构：一对一一对一存储结构：存储结构：顺序表、链表顺序表、链表运算规则：运算规则：随机存取随机存取堆栈堆栈逻辑结构：逻辑结构：一对一一对一存储结构：存储结构：顺序栈、链栈顺序栈、链栈运算规则：运算规则：后进先出后进先出(LIFO)*堆栈与一般线性表的比较*例例 一个栈的输入序列为一个栈的输入序列为123，若在入栈的过程中，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？允许出栈，则可能得到的出栈序列是什么？答：答： 可以通过穷举所有可能性来求解：可以通过

3、穷举所有可能性来求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出，1 1出出 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合计有合计有5 5种可能性。种可能性。* * 不可能产生的输出序列：不可能产生的输出序列：3123121、初始化、初始化2、

4、进栈、进栈3、退栈、退栈4、取栈顶元素、取栈顶元素5、判栈是否非空、判栈是否非空二、堆栈的操作二、堆栈的操作三、栈的顺序表示和实现三、栈的顺序表示和实现顺序堆栈顺序堆栈1. 顺序栈的存储结构顺序栈的存储结构出栈或出栈或退栈退栈入栈或入栈或进栈进栈basetopa0a1a3a4a5maxlen-1543210顺序栈的定义顺序栈的定义typedef int DataType;#define maxlen 100 / /* *顺序堆栈数组最大存储单元个数顺序堆栈数组最大存储单元个数* */ /typedef struct / /* *顺序栈定义顺序栈定义* */ / DataType stackma

5、xlen;/ /* *顺序堆栈存放数据元素的数组顺序堆栈存放数据元素的数组* */ / int top; / /* *顺序堆栈的当前栈顶位置顺序堆栈的当前栈顶位置* */ / seqstack; / /* *结构类型名结构类型名* */ /2. 顺序堆栈的操作实现顺序堆栈的操作实现toptopa0a1a2toptopmaxlen个空栈a0进栈a1进栈a2进栈a2出栈top 初始化参数：S是指向结构变量的指针；功能：建一个空栈S；void inistack(seqstack *s) s-top=-1;/ /* *顺序堆栈数组的当前栈顶位置顺序堆栈数组的当前栈顶位置* */ / 判栈空操作参数：S

6、是存放结构体变量的数组；功能：判断S是否为空，为空返回1，否则返回0；int empty(seqstack s) if(s.top=-1) return 1; else return 0; 入栈入栈功能：将数据元素x压入顺序堆栈S，入栈 成功返回1，否则返回0int push(seqstack *s, DataType x) if (s-top=maxlen-1) printf(“nStack is full”); return 0; s-top+; s-stacks-top=x; return 1;判栈满？判栈满？栈顶下标栈顶下标加加1 1入入栈栈s-stack+s-top=x; 出栈出栈功

7、能：弹出顺序堆栈s的栈顶数据元素值到参数 d，出栈成功返回1，否则返回0判栈空？判栈空？元素出元素出栈栈栈顶下标减栈顶下标减1else *d= s-stacks-top; (s-top)- -; return 1; int pop(seqstack *s,DataType *d) if(s-top=-1) printf(n Stack is empty!); return 0; *d=s-stacks-top-; 取栈顶元素取栈顶元素功能：取顺序堆栈s的当前栈顶数据元素值到 参数d，成功返回1，否则返回0 int gettop(seqstack s,DataType *d) if(s.top=

8、-1) printf(“nStack is empty!”); return 0; else *d=s.stacks.top; return 1; 堆栈算法练习堆栈算法练习顺序栈的顺序栈的C C语言描述：语言描述：typedef int elemtype;#define maxlen 10typedef struct elemtype stackmaxlen; int top;SeqStack;写出堆栈的入栈和出栈算法写出堆栈的入栈和出栈算法两个堆栈共享空间目的：两个堆栈共享空间目的：节省空间节省空间堆栈共用问题堆栈共用问题两个堆栈共享空间的运算：初始化两个堆栈共享空间的运算：初始化 进栈进栈

9、 出栈出栈a0aiajam0maxlen-1LeftTopRightTop 数据结构定义：数据结构定义：typedef struct DataType stackmaxlen; int LeftTop; int RightTop; dqstack; 初始化算法初始化算法void InitiDqstack(dqstack*s); s-LeftTop=-1; s-RightTop=maxlen; int PushDqstack(dqstack*s,char WhichStack,DataType x) if (s-LeftTop= s-RightTop-1) printf(“栈满栈满”); ret

10、urn 0; if (WhichStack!=L& WhichStack !=R) printf(“出错出错”); return 0; if (WhichStack=L) s-stack+s-LeftTop=x; else s-stack-s-RightTop=x; return 1; 进栈算法进栈算法判断是否栈判断是否栈满满判断输判断输入是否入是否错错X X入左栈入左栈X X入右栈入右栈共用堆栈的出共用堆栈的出栈算法栈算法:自编。自编。共用堆栈的算法练习共用堆栈的算法练习已知：已知：一个双向堆栈一个双向堆栈stackMstackM(M(M自己定义自己定义) )，编写一个算法：要求从键

11、盘输入数据，若输编写一个算法：要求从键盘输入数据，若输入的是奇数，则存入左栈；若输入的是偶数，入的是奇数，则存入左栈；若输入的是偶数，则存入右栈，直到栈满为止。则存入右栈，直到栈满为止。 12EFhead130A12EFa21475130Aa110CB1475a010CB四、栈的链式存储结构四、栈的链式存储结构栈顶栈顶链栈的结点定义链栈的结点定义typedeftypedef intint DataTypeDataType; ;typedeftypedef structstruct snodesnode DataTypeDataType data; data; structstruct snod

12、esnode * *next;next; LSNodeLSNode; ; int PushStack(LSNode *head, DataType x) LSNode *p; if (p=(LSNode*) malloc(sizeof(LSNode)=NULL) printf(“n失败失败”)； return 0； p-data=x; p-next=head-next; head-next=p; return 1; 链栈的进栈算法链栈的进栈算法申请一个申请一个新结点新结点进栈进栈headpxint PopStack(LSNode *head,DataType *d) LSNode *p; p=

13、head-next; if (p=NULL) printf(“under flown”); return 0; *d=p-data; head-next=p-next; free(p); return 1; 链栈的出栈算法链栈的出栈算法判栈空判栈空出栈出栈headp*d1：括号匹配问题括号匹配问题 设计思路：用栈暂存左括号设计思路：用栈暂存左括号2：数制转换（十转数制转换（十转N） 设计思路：用栈暂存低位值设计思路：用栈暂存低位值3：汉诺（汉诺（Hanoi）塔）塔 设计思路：用栈实现递归调用设计思路：用栈实现递归调用4：表达式求值表达式求值 设计思路：用栈暂存运算符设计思路：用栈暂存运算符堆栈

14、的应用数制转换数制转换N = (N div d)d + N mod d 例如：（例如：（1348)10 = (2504)8 ，其运算过程如下：，其运算过程如下：输出顺序输出顺序计算顺序计算顺序将余数依次进栈，再出栈 N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2汉诺（汉诺（ Hanoi）塔）塔传说在创世纪时，在一个叫传说在创世纪时，在一个叫BrahmaBrahma的寺庙里，有三个柱子，的寺庙里，有三个柱子，其中一柱上有其中一柱上有6464个盘子从小到大依次叠放，僧侣的工作是个盘子从小到大依次叠放，僧侣的工作是将这将这6464个盘子从一根柱子移

15、到另一个柱子上。当工作做完个盘子从一根柱子移到另一个柱子上。当工作做完之后，就标志着世界末日到来。之后，就标志着世界末日到来。 移动时的规则：移动时的规则： 每次只能移动一个盘子；每次只能移动一个盘子； 只能小盘子在大盘子上面；只能小盘子在大盘子上面； 可以使用任一柱子。可以使用任一柱子。x y zx y znn 1分析：分析： 设三根柱子分别为设三根柱子分别为x x，y y，z z，盘子在，盘子在x x柱上，要移到柱上，要移到z z柱上。柱上。 1 1、当、当n=1n=1时，盘子直接从时，盘子直接从x x柱移到柱移到z z柱上；柱上； 2 2、当、当n1n1时，则时，则设法将前设法将前n n

16、1 1个盘子借助个盘子借助z z，从，从x x移移到到y y柱上，把盘子柱上，把盘子n n移到移到z z柱上；柱上； 把把n n1 1个盘子从个盘子从y y移到移到z z柱上。柱上。abc321 11213121Y YX XZ Z表达式计算表达式计算中缀表达式：中缀表达式：A + ( B A + ( B C / D) C / D) E E后缀表达式：后缀表达式：ABCD/ABCD/E E+ +后缀表达式特点后缀表达式特点1 1、与相应的中缀表达式中的操作数次序相同、与相应的中缀表达式中的操作数次序相同2 2、没有括号、没有括号编译系统中表达式的计算分为两个步骤：编译系统中表达式的计算分为两个步

17、骤： （1）把中缀表达式变换为相应的后缀表达式；）把中缀表达式变换为相应的后缀表达式； （2）根据后缀表达式计算表达式的值。）根据后缀表达式计算表达式的值。中缀表达式转换为后缀表达式的处理规则中缀表达式转换为后缀表达式的处理规则1 1、如为、如为操作数操作数，直接输出到队列；，直接输出到队列；2 2、如当前、如当前运算符运算符高于高于栈顶运算符，入栈；栈顶运算符，入栈；3 3、如当前、如当前运算符运算符低于低于栈顶运算符，栈顶运算符退栈，并栈顶运算符，栈顶运算符退栈，并输出到队列，当前运算符再与栈顶运算符比较；输出到队列，当前运算符再与栈顶运算符比较；4 4、如当前、如当前运算符运算符等于等于

18、栈顶运算符，且栈顶运算符为栈顶运算符，且栈顶运算符为“（”，当前运算符为，当前运算符为“）”，则栈顶运算符退栈，继续，则栈顶运算符退栈，继续读下一符号；读下一符号；5 5、如当前、如当前运算符运算符等于等于栈顶运算符，且栈顶运算符为栈顶运算符，且栈顶运算符为“#”“#”，当前运算符也为，当前运算符也为“#”“#”，则栈顶运算符退栈，则栈顶运算符退栈，表示运算结束；表示运算结束；()#(#front=0; sq-front=0; sq-rear=0; sq-rear=0; 循环队列的初始化循环队列的初始化/*队头指针*/*队尾指针*/intint addqueue(sequeueaddqueue

19、(sequeue * *sq,DataTypesq,DataType x) x) if (sq-front=(sq-rear+1)%maxlen) if (sq-front=(sq-rear+1)%maxlen) printf(“nQueueprintf(“nQueue is full”); is full”); return 0; return 0; sq- sq-queuesqqueuesq-rear=x;-rear=x; sq-rear=(sq-rear+1)%maxlen; sq-rear=(sq-rear+1)%maxlen; return 1; return 1; 循环队列的入队列

20、循环队列的入队列判断是否队满判断是否队满队尾指针后移队尾指针后移元素入队元素入队intint delqueue(sequeuedelqueue(sequeue * *sq, sq, DataTypeDataType * *d)d) if (sq-front=sq-rear) if (sq-front=sq-rear) printf(nprintf(n Queue is empty!); Queue is empty!); return 0; return 0; * *d=sq-d=sq-queuesqqueuesq-front;-front; sq-front=(sq-front+1)%max

21、len; sq-front=(sq-front+1)%maxlen; return 1; return 1; 循环队列的出队列循环队列的出队列队头指针后移队头指针后移元素出队元素出队判断是否队空判断是否队空四、队列的链式存储结构四、队列的链式存储结构 队列的链式存储结构队列的链式存储结构12EFfront130A12EFa01475130Aa110CB1475a210CB10CBrear链队列的结构体定义链队列的结构体定义typedef struct slnode DataType data; struct slnode *next; LQNode; typedef struct LQNode

22、 *front; LQNode *rear; LQueue;结点的结结点的结构体类型构体类型front rear队头指针队头指针队尾指针队尾指针初始化初始化int InitiateSLQueue(LQueue *q) if(q-front=(LQNode*)malloc(sizeof(LQNode) =NULL) printf(“n申请空间失败！申请空间失败！”); return 0; q-rear=q-front; q-front-next=NULL; return 1; 12EFfrontNULL12EFrearn链队列的入队示意链队列的入队示意12EFfront*p130ApNULL13

23、0A*p1475px1NULLx0NULL147512EFrear130Arear1475reara0fronta1 rearrear链队列的入队算法链队列的入队算法pX intint addqaddq ( (LQueueLQueue * *q,DataTypeq,DataType x) x) LQNodeLQNode * *p;p; if if (p=(p=(LQNodeLQNode* * ) ) malloc(sizeof(LQNodemalloc(sizeof(LQNode)=NULL)=NULL) printfprintf (“n (“n申请空间失败申请空间失败!”); return 0;!”); return 0; p-data=x; p-data=x; p-next=NULL; p-next=NULL; q-rear-next=p; q-rear-next=p; q-rear=p; q-rear=p; return 1; return 1; y1475p12EFfronta1NULL1475a0130A1