一章栈和队列.ppt

第三章第三章 栈和队列栈和队列n本章内容本章内容3.1 栈栈3.1.1 栈的定义及基本运算栈的定义及基本运算3.1.2 栈的存储结构和实现栈的存储结构和实现3.1.3 栈的应用栈的应用3.2 队列队列3.2.1 队列的定义及基本运算队列的定义及基本运算3.2.2 队列的存储结构和实现队列的存储结构和实现3.2.3 队列的应用队列的应用3.1.1 栈的定义及基本运算栈的定义及基本运算n栈栈(Stack)的定义的定义– 栈栈(Stack)是限制在表的一端是限制在表的一端进行插入和删除运算的线性表，进行插入和删除运算的线性表，通常称插入、删除的这一端为通常称插入、删除的这一端为栈顶栈顶(top),另一端为栈底另一端为栈底(bottom)当表中没有元素当表中没有元素时称为空栈时称为空栈anan-1 ...a2a1栈底栈底栈顶栈顶入栈入栈出栈出栈¯栈的特点栈的特点　　　　栈的修改是按后进先出的原栈的修改是按后进先出的原则进行的因此，栈称为后进先则进行的因此，栈称为后进先出表（出表（LIFO）3.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演示栈的运算演示(1)A、、B、、C、、D四个元素依次进入一个栈，再依次出四个元素依次进入一个栈，再依次出栈，得到一个输出序列栈，得到一个输出序列DCBA。

DCBAABCDDCBA 3.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演示栈的运算演示(1)A、、B、、C、、D四个元素依次进入一个栈，再依次出四个元素依次进入一个栈，再依次出栈，得到一个输出序列栈，得到一个输出序列DCBA2)能否由入栈序列能否由入栈序列A、、B、、C、、D、、E得到出栈序列得到出栈序列CBDAE？？ABCDE操作序列：操作序列：出栈序列：出栈序列：①① 元素元素A入栈入栈A A②② 元素元素B入栈入栈B B③③ 元素元素C入栈入栈C C3.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演示栈的运算演示(1)A、、B、、C、、D四个元素依次进入一个栈，再依次出四个元素依次进入一个栈，再依次出栈，得到一个输出序列栈，得到一个输出序列DCBA2)能否由入栈序列能否由入栈序列A、、B、、C、、D、、E得到出栈序列得到出栈序列CBDAE？？ DE操作序列：操作序列：出栈序列：出栈序列：①① 元素元素A入栈入栈A②② 元素元素B入栈入栈B③③ 元素元素C入栈入栈④④ 元素元素C出栈出栈CC⑤⑤ 元素元素B出栈出栈B3.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演示栈的运算演示(1)A、、B、、C、、D四个元素依次进入一个栈，再依次出四个元素依次进入一个栈，再依次出栈，得到一个输出序列栈，得到一个输出序列DCBA。

2)能否由入栈序列能否由入栈序列A、、B、、C、、D、、E得到出栈序列得到出栈序列CBDAE？？ DE操作序列：操作序列：出栈序列：出栈序列：①① 元素元素A入栈入栈A②② 元素元素B入栈入栈③③ 元素元素C入栈入栈④④ 元素元素C出栈出栈C⑤⑤ 元素元素B出栈出栈B⑥⑥ 元素元素D入栈入栈D D⑦⑦ 元素元素D出栈出栈D⑧⑧ 元素元素A出栈出栈A3.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演示栈的运算演示(1)A、、B、、C、、D四个元素依次进入一个栈，再依次出四个元素依次进入一个栈，再依次出栈，得到一个输出序列栈，得到一个输出序列DCBA2)能否由入栈序列能否由入栈序列A、、B、、C、、D、、E得到出栈序列得到出栈序列CBDAE？？ E操作序列：操作序列：出栈序列：出栈序列：①① 元素元素A入栈入栈②② 元素元素B入栈入栈③③ 元素元素C入栈入栈④④ 元素元素C出栈出栈C⑤⑤ 元素元素B出栈出栈B⑥⑥ 元素元素D入栈入栈⑦⑦ 元素元素D出栈出栈D⑧⑧ 元素元素A出栈出栈A⑨⑨ 元素元素E入栈入栈EE ⑩⑩ 元素元素E出栈出栈En栈的基本运算栈的基本运算InitStack(&SInitStack(&S): ): 初始化栈初始化栈S SStackEmptyStackEmpty(): (): 判断栈是否为空判断栈是否为空Push(e): Push(e): 将元素将元素e e放入栈顶放入栈顶Pop(e): Pop(e): 移走栈顶的元素，同时由移走栈顶的元素，同时由e e带回该元带回该元素的值素的值GettopGettop(): (): 获取栈顶的元素，但不从栈中移走获取栈顶的元素，但不从栈中移走3.1.1 栈的定义及基本运算栈的定义及基本运算3.1.2 栈的存储结构和实现栈的存储结构和实现anan-1 ...a2a1栈栈basetop• • 栈的表示和实现栈的表示和实现栈的表示和实现栈的表示和实现 假设栈假设栈假设栈假设栈S=(aS=(a1 1，，，，a a2 2，，，，a a3 3，，，，……，，，，a an n) )，则，则，则，则a a1 1称为栈底元素称为栈底元素称为栈底元素称为栈底元素，，，，a an n为栈为栈为栈为栈顶元素顶元素顶元素顶元素。

栈中元素按栈中元素按栈中元素按栈中元素按a a1 1，，，，a a2 2，，，，a a3 3，，，，…,a…,an n的次序进栈，退栈的第一的次序进栈，退栈的第一的次序进栈，退栈的第一的次序进栈，退栈的第一个元素应为栈顶元素换句话说，个元素应为栈顶元素换句话说，个元素应为栈顶元素换句话说，个元素应为栈顶元素换句话说，栈的修改是按后进先出的原则进栈的修改是按后进先出的原则进栈的修改是按后进先出的原则进栈的修改是按后进先出的原则进行的因此，栈称为行的因此，栈称为行的因此，栈称为行的因此，栈称为后进先出表后进先出表后进先出表后进先出表(Last In First Out(Last In First Out，，，，LIFO)LIFO)3.1.2 栈的存储结构和实现栈的存储结构和实现• • 顺序栈顺序栈顺序栈顺序栈– – 由于栈是由于栈是由于栈是由于栈是运算受限的线性表运算受限的线性表运算受限的线性表运算受限的线性表，因此线性表的存，因此线性表的存，因此线性表的存，因此线性表的存储结构对栈也适应储结构对栈也适应储结构对栈也适应储结构对栈也适应栈的顺序存储结构简称为栈的顺序存储结构简称为栈的顺序存储结构简称为栈的顺序存储结构简称为顺序栈顺序栈顺序栈顺序栈，它是运算受限的线性表。

因此，可用，它是运算受限的线性表因此，可用，它是运算受限的线性表因此，可用，它是运算受限的线性表因此，可用数组来实现顺序栈数组来实现顺序栈数组来实现顺序栈数组来实现顺序栈3.1.2 栈的存储结构和实现栈的存储结构和实现n顺序栈的类型定义顺序栈的类型定义// -----栈的顺序存储表示栈的顺序存储表示-----# define STACK_INIT_SIZE 100;# define STACKINCREMENT 10;typedef struct { SElemType *base; //栈底指针，栈构造前和销毁后为空栈底指针，栈构造前和销毁后为空 SElemType *top; //栈顶指针，指向栈顶元素的下一位置栈顶指针，指向栈顶元素的下一位置 int stacksize; //当前分配的栈的存储空间数当前分配的栈的存储空间数}SqStack; • • 顺序栈顺序栈顺序栈顺序栈设设设设S S是是是是SqStackSqStack类型的指针变量类型的指针变量类型的指针变量类型的指针变量basebase是栈是栈是栈是栈底指针TopTop是栈顶指针是栈顶指针。

是栈顶指针是栈顶指针– – 栈不存在条件栈不存在条件栈不存在条件栈不存在条件S.baseS.base=NULL=NULL– – 栈空条件栈空条件栈空条件栈空条件S.topS.top==S.baseS.base– – 插入栈顶元素，栈顶指针插入栈顶元素，栈顶指针插入栈顶元素，栈顶指针插入栈顶元素，栈顶指针S.topS.top=S.top+1=S.top+1– – 删除栈顶元素，栈顶指针删除栈顶元素，栈顶指针删除栈顶元素，栈顶指针删除栈顶元素，栈顶指针S.topS.top=S.top-1=S.top-1– – 栈满条件栈满条件栈满条件栈满条件S.top-S.baseS.top-S.base>=>=S.stacksizeS.stacksize3.1.2 栈的存储结构和实现栈的存储结构和实现3.1.2 栈的存储结构和实现栈的存储结构和实现n n顺序栈的顺序栈的顺序栈的顺序栈的C C语言实现语言实现语言实现语言实现(1) (1) 初始化初始化初始化初始化Status Status InitStack(SqStackInitStack(SqStack &S){ &S){ // //构造一个空栈构造一个空栈构造一个空栈构造一个空栈 S.baseS.base = ( = (ElemTypeElemType *) *) malloc(STACK_INIT_SIZEmalloc(STACK_INIT_SIZE * *sizeof(SElemTypesizeof(SElemType)) ;)) ; if(!S.baseif(!S.base) exit (OVERFLOW);) exit (OVERFLOW); S.topS.top = S.base; = S.base; S.stacksizeS.stacksize = = STACK_INIT_SIZE ;STACK_INIT_SIZE ; return OK; return OK;}//}//InitStackInitStack(2)判断栈空判断栈空int StackEmpty(SqStack *S) { return(S.base==S.top);}(3)判断栈满判断栈满int StackFull(SqStack *S) { return(S.top-S.base>=S.stacksize);}3.1.2 栈的存储结构和实现栈的存储结构和实现3.1.2 栈的存储结构和实现栈的存储结构和实现( (4) 4) 元素入栈元素入栈元素入栈元素入栈Status Push(SqStack &S, SElemType e){//插入元素插入元素e为新的栈顶元素为新的栈顶元素if (S.top – S.base >= S.stacksize) return OVERFLOW; //栈满栈满*S.top = e;S.top++;return OK;}//Push (5) 出栈出栈void Pop(SqStack *S, SElemType &e){ if(S.top==s.base) return UNDERFLOW; // 栈空栈空 S.top--; e=*S.top; return;}3.1.2 栈的存储结构和实现栈的存储结构和实现3.1.2 栈的存储结构和实现栈的存储结构和实现• • 链栈链栈链栈链栈– – 栈的链式存储结构称为链栈栈的链式存储结构称为链栈栈的链式存储结构称为链栈栈的链式存储结构称为链栈，它是运算是受限的，它是运算是受限的，它是运算是受限的，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。

单链表，插入和删除操作仅限制在表头位置上进行单链表，插入和删除操作仅限制在表头位置上进行单链表，插入和删除操作仅限制在表头位置上进行由于只能在链表头部进行操作，故链表没有必要像由于只能在链表头部进行操作，故链表没有必要像由于只能在链表头部进行操作，故链表没有必要像由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点单链表那样附加头结点单链表那样附加头结点单链表那样附加头结点栈顶指针就是链表的头指栈顶指针就是链表的头指栈顶指针就是链表的头指栈顶指针就是链表的头指针针针针– – 链栈的类型说明如下：链栈的类型说明如下：链栈的类型说明如下：链栈的类型说明如下：typedeftypedef structstruct stacknodestacknode{ { SElemTypeSElemType data; data; structstruct stacknodestacknode *next; *next;} } stacknodestacknode,*,*linkstacklinkstack; ;3.1.2 栈的存储结构和实现栈的存储结构和实现n链栈链栈anan-1 ...a2a1栈栈栈底栈底栈顶栈顶…S栈的链式存储栈的链式存储an an-1 a1^a2 ¯思考思考①① 链栈是否需要另外设置头指针？链栈是否需要另外设置头指针？②② 建立链栈适合用哪种插入法？建立链栈适合用哪种插入法？③③ 链栈的基本操作的实现。

链栈的基本操作的实现• 链栈的基本操作链栈的基本操作– 置空栈置空栈void InitStack(linkStack &p){ p=NULL;}– 判断栈空判断栈空int StackEmpty(linkstack p){ return p==NULL;}3.1.2 栈的存储结构和实现栈的存储结构和实现• • 链栈的基本操作链栈的基本操作链栈的基本操作链栈的基本操作– – 进栈进栈进栈进栈void void Push(linkstackPush(linkstack &p, &p, SElemTypeSElemType e) e){ { stacknodestacknode *q; *q;q=(q=(stacknodestacknode*)*)malloc(sizeof(stacknodemalloc(sizeof(stacknode));));q–>data=e;q–>data=e;q–>next=p;q–>next=p;p=q; //p=q; //设置栈顶指针设置栈顶指针设置栈顶指针设置栈顶指针} }3.1.2 栈的存储结构和实现栈的存储结构和实现• • 链栈的基本操作链栈的基本操作链栈的基本操作链栈的基本操作– – 退栈退栈退栈退栈SElemTypeSElemType Pop(linkstackPop(linkstack &&p)p){ {SElemTypeSElemType x; x; // //临时变量，保存栈顶元素临时变量，保存栈顶元素临时变量，保存栈顶元素临时变量，保存栈顶元素linkstacklinkstack q=p;q=p;if(pif(p==NULL==NULL) ) error(“stackerror(“stack underflow.”); underflow.”);p=p=p p–>next;–>next; // //调整栈顶调整栈顶调整栈顶调整栈顶指针指针指针指针x=q–>data;x=q–>data;free(qfree(q);); // //删除栈顶元素删除栈顶元素删除栈顶元素删除栈顶元素return x;return x;} }3.1.2 栈的存储结构和实现栈的存储结构和实现• • 链栈的基本操作链栈的基本操作链栈的基本操作链栈的基本操作– – 取栈顶元素取栈顶元素取栈顶元素取栈顶元素SElemTypeSElemType GetTop(linkstackGetTop(linkstack p) p){ {if(pif(p==NULL)==NULL) error(“stackerror(“stack is empty.”); is empty.”);returnreturn p–>data; p–>data;} }3.1.2 栈的存储结构和实现栈的存储结构和实现3.2 栈的应用举例栈的应用举例　　根据栈的　　根据栈的　　根据栈的　　根据栈的FILOFILOFILOFILO特性，用作某些处理问题的工具。

特性，用作某些处理问题的工具特性，用作某些处理问题的工具特性，用作某些处理问题的工具3.2.1 数制转换数制转换例：例：例：例： 434310 10 = 101011= 1010112 2被除数被除数除数除数商商余数余数432211212101102505221221012010 输出输出void conversion( ) {InitStack(S); //构造空栈构造空栈scanf (“%d”,&n);while(n){Push(S,n%2);n=n/2; }while(! StackEmpty(S)){Pop(S,e);printf(“%d”,e); }}3.2 栈的应用举例栈的应用举例3.2.2 括号匹配括号匹配设一个表达式中可以包含三种括号：设一个表达式中可以包含三种括号：“(”和和“)”、、“[”和和“]”、、“{”和和“}”，并且这三种括号可以按照，并且这三种括号可以按照任意的次序任意的次序嵌套嵌套使用，考查表达式中的括号是否匹配使用，考查表达式中的括号是否匹配例如：例如： ...[...{...[...}...]...]...[...]...(...)...)...n例：例：a=b+(c-d)*(e-f));while (m<(a[8]+t) {m=m+1; t=t-1;}n实现方法－－利用栈进行表达式中的括号匹配实现方法－－利用栈进行表达式中的括号匹配自左至右扫描表达式，若遇左括号，则将左括号入栈，自左至右扫描表达式，若遇左括号，则将左括号入栈，若遇右括号，则将其与栈顶的左括号进行匹配，若配对，若遇右括号，则将其与栈顶的左括号进行匹配，若配对，则栈顶的左括号出栈，否则出现括号不匹配错误。

则栈顶的左括号出栈，否则出现括号不匹配错误思考：匹配的充要条件？思考：匹配的充要条件？3.2 栈的应用举例栈的应用举例3.2.3 迷宫问题迷宫问题寻找一条从入口到出口的通路寻找一条从入口到出口的通路81 2 3 4 5 6 781234567入口入口出口出口前进方向：前进方向： 上上(北北)、下、下(南南)、左、左(西西)、右、右(东东)东东南南北北西西n 走步规则：走步规则：　　首先从向下开始，按　　首先从向下开始，按照逆时针方向搜索下一步照逆时针方向搜索下一步可能前进的位置可能前进的位置3.2 栈的应用举例栈的应用举例栈栈n迷宫问题迷宫问题81 2 3 4 5 6 781234567(1,1)(1,1)i(2,1)(2,1)i(3,1)(3,1)i(4,1)(4,1)i(5,1)(5,1)i(6,1)(6,1)(7,1)(7,1)i3.2 栈的应用举例栈的应用举例栈栈n迷宫问题迷宫问题81 2 3 4 5 6 781234567(1,1)(1,1)i(2,1)(2,1)i(3,1)(3,1)i(4,1)(4,1)i(5,1)(5,1)i(6,1)(6,1)(7,1)(7,1)i@ @ (5,2)(5,2)i(5,3)(5,3)i(6,3)(6,3)i(6,4)(6,4)i……(8,8)(8,8)iiiiii3.2 栈的应用举例栈的应用举例n迷宫问题迷宫问题n迷宫的表示迷宫的表示const int N=8;struct PosType{ int x, y;};char maze[N][N]; //位置上的标识，是否可通过位置上的标识，是否可通过n迷宫初始化迷宫初始化用二层嵌套循环对迷宫赋值用二层嵌套循环对迷宫赋值n迷宫求解迷宫求解(见教材算法见教材算法)n输出栈中的路径输出栈中的路径3.2 栈的应用举例栈的应用举例Status MazePath(maze, start, end) {//若迷宫中存在一条从入口若迷宫中存在一条从入口start到出口到出口end的通道，则求出这样的一条通路的通道，则求出这样的一条通路 InitStack(S); curpos = start; curstep = 1; do { if (pass(curpos)) ｛｛ //当前位置可以通过当前位置可以通过 Mark(maze,curpos); //留下记号留下记号 e = (curstep,curpos,1); push(S,e); //加入路径加入路径 if (curpos==end) return true; //到达出口到达出口 curpos = NextPos(curpos,1) ;//下一个位置下一个位置 curstep++; } else {//当前位置不能通过当前位置不能通过 if (!StackEmpty(S)){ pop(S,e); //退回一步退回一步 while(e.di==4 && ! StackEmpty(S)) {//当前位置是死胡同当前位置是死胡同 Markdead(maze,e.seat)；；pop(S,e); //留下记号，沿来路返回留下记号，沿来路返回 } if (e.di<4) { //当前位置还有其他方向没有探索，继续试探当前位置还有其他方向没有探索，继续试探 e.di++; push(S,e); curpos =NextPos(e.seat, e.di); } } }while (!StackEmpty(S)); return false;}3.2.4 表达式求值表达式求值—算符优先法算符优先法 4+2×3-10/5– 先乘除先乘除,后加减后加减;– 从左算到右从左算到右– 先括号内先括号内,后括号外后括号外– 4+2×3-10/5=4+6-10/5=10-10/5=10-2=8• 表达式由表达式由操作数操作数(operand)、、运算符运算符(operator)和和界限符界限符(delimiter)组成的。

组成的• 将运算符和界限符统称为将运算符和界限符统称为算符算符它们构成的集合命名为它们构成的集合命名为OP3.2 栈的应用举例栈的应用举例• • 表达式求值表达式求值表达式求值表达式求值– – 算符优先算法算符优先算法算符优先算法算符优先算法: :用两个工作栈一个称作用两个工作栈一个称作用两个工作栈一个称作用两个工作栈一个称作OPTR,OPTR,用于用于用于用于存放运算符存放运算符存放运算符存放运算符; ;另一个称作另一个称作另一个称作另一个称作OPND,OPND,用以存放操作数或运用以存放操作数或运用以存放操作数或运用以存放操作数或运算结果– – 首先置操作数栈为空栈，表达式起始符首先置操作数栈为空栈，表达式起始符首先置操作数栈为空栈，表达式起始符首先置操作数栈为空栈，表达式起始符“ “#”#”为运算为运算为运算为运算符的栈底元素；符的栈底元素；符的栈底元素；符的栈底元素；– – 依次读入表达式中每个字符，若是操作数则进依次读入表达式中每个字符，若是操作数则进依次读入表达式中每个字符，若是操作数则进依次读入表达式中每个字符，若是操作数则进OPNDOPND栈，若是运算符，则和栈，若是运算符，则和栈，若是运算符，则和栈，若是运算符，则和OPTROPTR栈的栈顶运算符比较优栈的栈顶运算符比较优栈的栈顶运算符比较优栈的栈顶运算符比较优先权后作相应操作，直到整个表达式求值完毕先权后作相应操作，直到整个表达式求值完毕先权后作相应操作，直到整个表达式求值完毕先权后作相应操作，直到整个表达式求值完毕(OPTR(OPTR栈的栈顶元素和当前读入的字符均为栈的栈顶元素和当前读入的字符均为栈的栈顶元素和当前读入的字符均为栈的栈顶元素和当前读入的字符均为“ “#”)#”)3.2 栈的应用举例栈的应用举例• OperandType EvaluateExpression() { InitStack(OPTR); Push(OPTR,’#’); InitStack(OPND); c = getchar(); while(c != ‘#’||GetTop(OPTR)!=‘#’){ if(!In(c,OP)) {Push(OPND,c); c=getchar();} else //不是运算符则进栈不是运算符则进栈 switch(Precede(GetTop(OPTR),c)){ case ‘<’: //栈顶元素优先权低栈顶元素优先权低 Push(OPTR,c); c=getchar(); break; case ‘=’: //脱括号并接收下一字符脱括号并接收下一字符 Pop(OPTR,x); c=getchar(); break;3.2 栈的应用举例栈的应用举例 case ‘>’: //退栈并将运算结果入栈退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; } //switch}//while return GetTop(OPND);}//EvaluateExpression3.2 栈的应用举例栈的应用举例3.3 栈与递归的实现栈与递归的实现n栈与递归的实现栈与递归的实现用栈结构实现程序设计语言中函数的嵌套调用和递归用栈结构实现程序设计语言中函数的嵌套调用和递归调用调用例：例： long f(int n) { if (n>1) return n*f(n-1); else return 1; } void main( ) { int n=4; printf(“%ld”,f(n)); }栈与递归3.3 栈与递归的实现栈与递归的实现• n• n阶阶阶阶HanoiHanoi塔塔塔塔 问题问题问题问题假设有三个分别命名为假设有三个分别命名为假设有三个分别命名为假设有三个分别命名为X X、、、、Y Y和和和和Z Z的塔座，在塔座的塔座，在塔座的塔座，在塔座的塔座，在塔座X X上插有上插有上插有上插有n n个直径大小各不相同、依小到大编号个直径大小各不相同、依小到大编号个直径大小各不相同、依小到大编号个直径大小各不相同、依小到大编号为为为为1 1，，，，2 2，，，，…,n…,n的圆盘。

现要求将的圆盘现要求将的圆盘现要求将的圆盘现要求将X X轴上的轴上的轴上的轴上的n n个圆个圆个圆个圆盘移至塔座盘移至塔座盘移至塔座盘移至塔座Z Z上并仍按同样顺序叠排上并仍按同样顺序叠排上并仍按同样顺序叠排上并仍按同样顺序叠排– – 每次只能移动一个圆盘；每次只能移动一个圆盘；每次只能移动一个圆盘；每次只能移动一个圆盘；– – 圆盘可以插在圆盘可以插在圆盘可以插在圆盘可以插在X X、、、、Y Y和和和和Z Z中的任一塔座上；中的任一塔座上；中的任一塔座上；中的任一塔座上；– – 任何时刻都不能将一个较大的圆盘压在较小的圆盘任何时刻都不能将一个较大的圆盘压在较小的圆盘任何时刻都不能将一个较大的圆盘压在较小的圆盘任何时刻都不能将一个较大的圆盘压在较小的圆盘之上栈与递归3.3 栈与递归的实现栈与递归的实现• n阶阶Hanoi塔问题塔问题Base case: n = 1 X → Z栈与递归3.3 栈与递归的实现栈与递归的实现• n阶阶Hanoi塔问题塔问题Base case: n = 1 X → Z栈与递归3.3 栈与递归的实现栈与递归的实现• n阶阶Hanoi塔问题塔问题Recursion: n > 1 前前n-1 个盘个盘: X → Y栈与递归3.3 栈与递归的实现栈与递归的实现• n阶阶Hanoi塔问题塔问题Recursion: n > 1 前前n-1 个盘个盘: X → Y栈与递归3.3 栈与递归的实现栈与递归的实现• n阶阶Hanoi塔问题塔问题Recursion: n > 1 最大盘最大盘: X → Z栈与递归3.3 栈与递归的实现栈与递归的实现• n阶阶Hanoi塔问题塔问题Recursion: n > 1 最大盘最大盘: X → Z栈与递归3.3 栈与递归的实现栈与递归的实现• n阶阶Hanoi塔问题塔问题Recursion: n > 1 前前n-1个盘个盘: Y → Z栈与递归3.3 栈与递归的实现栈与递归的实现• n阶阶Hanoi塔问题塔问题Recursion: n > 1 前前n-1个盘个盘: Y → Z栈与递归3.4.1 队列的定义及基本运算队列的定义及基本运算n队列队列(Queue)的定义的定义队列是仅限定在表尾进行插入和表头进行删除操作的线性表。

队列是仅限定在表尾进行插入和表头进行删除操作的线性表n术语术语队头队头(front)－－－－队列的表头，即只允许删除的一端队列的表头，即只允许删除的一端队尾队尾(rear) －－－－队列的表尾队列的表尾，，即只允许插入的一端即只允许插入的一端入队入队(EnQueue) －－－－向队尾插入元素向队尾插入元素出队出队(DeQueue) －－－－从队头删除元素从队头删除元素¯队列的特点队列的特点　　　　队列的修改是按先进先出的原则进行的因此，队队列的修改是按先进先出的原则进行的因此，队列称为先进先出表（列称为先进先出表（FIFO）a1 a2 … ai … an队头队头front队尾队尾rear出队出队入队入队3.4.1 队列的定义及基本运算队列的定义及基本运算n队列的基本运算队列的基本运算InitQueue(&Q): 初始化队列初始化队列ueueEmpty(): 判断队列是否为空判断队列是否为空EnQueue(e): 将元素将元素e放入队尾放入队尾DeQueue(e): 移走队头元素，由移走队头元素，由e带回该元带回该元素的值素的值GetFront(): 获取队头元素的值，但不从队列获取队头元素的值，但不从队列中移走该元素中移走该元素Length(): 计算并返回队列中元素的个数计算并返回队列中元素的个数3.4.2 队列的存储结构和实现队列的存储结构和实现n链队列链队列－－队列的链式存储结构队列的链式存储结构… 队列的链式存储队列的链式存储a1 a2 an^ai Q.frontQ.rear…a1 a2 … ai … an队头队头front队尾队尾rear出队出队入队入队3.4.2 队列的存储结构和实现队列的存储结构和实现n链队列的链队列的C语言实现语言实现 //-----单链队列的存储结构单链队列的存储结构-----typedef struct QNode{ //链表结点类型链表结点类型 QElemType data; struct QNode *next;}QNode,*QueuePtr; typedef struct { //队列类型队列类型 QueuePtr front; //队头指针队头指针 QueuePtr rear; //队尾指针队尾指针}LinkQueue;data Q.frontQ.rearStatus InitQueue(LinkQueue &Q) {//构造一个空队列构造一个空队列.front= Q.rear = (QueuePtr)malloc(sizeof(QNode));if(!Q.front) exit(OVERFLOW);Q.front->next = NULL;return OK;}3.4.2 队列的存储结构和实现队列的存储结构和实现n链队列基本操作的实现链队列基本操作的实现(1) 初始化初始化 ^Q.frontQ.rear(2) 入队入队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;}3.4.2 队列的存储结构和实现队列的存储结构和实现Status DeQueue(LinkQueue &Q, QElemType &e){//若队列不空，则队头元素出队列，用若队列不空，则队头元素出队列，用e返回其值，返回其值， //返回返回OK，否则返回，否则返回ERROR if (Q.rear == Q.front) return ERROR; p = Q.front -> next; e = p -> data; Q.front->next = p -> next; if (Q.rear == p) Q.rear = Q.front; free(p); return OK;}3.4.2 队列的存储结构和实现队列的存储结构和实现 (3) 出队列出队列思考：思考：如果不设置头结点，如果不设置头结点，需要考虑那些特殊情需要考虑那些特殊情况？况？3.4.2 队列的存储结构和实现队列的存储结构和实现n循环队列－－队列的顺序存储结构循环队列－－队列的顺序存储结构a1 a2 … ai … an队头队头front队尾队尾rear出队出队入队入队6F36an…6F26ai ... ...6F02a26F00a1Q.frontQ.reara1a2a3……Q.frontanQ.rear012nn+1m-1循环队列循环队列n循环队列的循环队列的C语言实现语言实现//----循环队列的存储结构循环队列的存储结构----#define MAXSIZE 100typedef struct { QElemType *base; int front; int rear; }SqQueue;3.4.2 队列的存储结构和实现队列的存储结构和实现n循环队列基本操作的实现循环队列基本操作的实现(1) 初始化初始化Status InitQueue(SqQueue &Q){Q.base=(QElemType *) malloc(MAXSIZE*sizeof(QElemType));if (!Q.base) exit (OVERFLOW);Q.front = Q.rear = 0;return OK;} (base+Maxsize-1)→base→3.4.2 队列的存储结构和实现队列的存储结构和实现3.4.2 队列的存储结构和实现队列的存储结构和实现n循环队列基本操作的实现循环队列基本操作的实现(2) 入队入队Status EnQueue(SqQueue &Q,QElemType e) {//将元素将元素e插入队列插入队列Q的队尾的队尾if ((Q.rear+1) % MAXSIZE == Q.front) return ERROR;Q.base[Q.rear] = e;Q.rear = (Q.rear+1) % MAXSIZE;return OK;}n循环队列基本操作的实现循环队列基本操作的实现(3) 出队出队Status DeQueue(SqQueue &Q,QElemType &e) {//删除队列删除队列Q的队头元素并用的队头元素并用e带回带回if (Q.front == Q.rear) return ERROR;e = Q.base[Q.front];Q.front = (Q.front+1) % MAXSIZE;return OK;}3.4.2 队列的存储结构和实现队列的存储结构和实现双端队列双端队列§双端队列双端队列队头队头队尾队尾出队出队入队入队出队出队入队入队§输出受限的双端队列输出受限的双端队列队头队头队尾队尾出队出队入队入队入队入队双端队列双端队列§输入受限的双端队列输入受限的双端队列队头队头队尾队尾出队出队入队入队出队出队优先队列优先队列¯¯在许多情况下，简单的队列结构是不够的，需要在许多情况下，简单的队列结构是不够的，需要在许多情况下，简单的队列结构是不够的，需要在许多情况下，简单的队列结构是不够的，需要使用某些优先规则来完善先入先出机制，例如使用某些优先规则来完善先入先出机制，例如使用某些优先规则来完善先入先出机制，例如使用某些优先规则来完善先入先出机制，例如……¯¯优先队列的问题是如何找到一种实现优先的方法，使优先队列的问题是如何找到一种实现优先的方法，使优先队列的问题是如何找到一种实现优先的方法，使优先队列的问题是如何找到一种实现优先的方法，使得入队和出队列操作得以相对容易实现。

得入队和出队列操作得以相对容易实现得入队和出队列操作得以相对容易实现得入队和出队列操作得以相对容易实现¯¯优先队列可以通过两种修正的链表结构来实现优先队列可以通过两种修正的链表结构来实现优先队列可以通过两种修正的链表结构来实现优先队列可以通过两种修正的链表结构来实现ØØ一种结构是元素仍然依次进入（即加入元素时，一种结构是元素仍然依次进入（即加入元素时，一种结构是元素仍然依次进入（即加入元素时，一种结构是元素仍然依次进入（即加入元素时，时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(1)O(1)），而取出元素时则需遍历队），而取出元素时则需遍历队），而取出元素时则需遍历队），而取出元素时则需遍历队列（即出队时的时间复杂度为列（即出队时的时间复杂度为列（即出队时的时间复杂度为列（即出队时的时间复杂度为O(nO(n) )），），），），ØØ另一种是根据元素的优先级决定其插入的位置另一种是根据元素的优先级决定其插入的位置另一种是根据元素的优先级决定其插入的位置另一种是根据元素的优先级决定其插入的位置（即入队时的时间复杂度为（即入队时的时间复杂度为（即入队时的时间复杂度为（即入队时的时间复杂度为O(nO(n) )，出队时的时间，出队时的时间，出队时的时间，出队时的时间复杂度为复杂度为复杂度为复杂度为O(1)O(1)）。

3.4.3 队列的应用队列的应用　　同栈一样，队列也是一种应用广泛的　　同栈一样，队列也是一种应用广泛的线性表，在日常生活和计算机科学中很常线性表，在日常生活和计算机科学中很常见：见：Ø离散事件模拟离散事件模拟Ø排队问题排队问题Ø作业控制作业控制Ø广度优先搜索广度优先搜索Ø...本章小结本章小结n本章应掌握的内容本章应掌握的内容n栈的定义、运算栈的定义、运算n顺序栈、链栈顺序栈、链栈n队列的定义、运算及实现队列的定义、运算及实现n循环链队列、循环顺序队列循环链队列、循环顺序队列。