堆栈堆栈的应用队列队列的应用

堆栈堆栈的应用队列队列的应用第三章堆栈和队列6/8/202613.1栈(Stack)只允许在一端插入和删除的顺序表允许插入和删除的一端称为栈顶

(top)，另一端称为栈底(bottom)特点后进先出(LIFO)退栈进栈6/8/20262进栈示例

6/8/20263退栈示例6/8/20264栈的基本操作1、初始化2、进栈3、退栈4、取栈顶元素5、判栈是否非空6、置栈空6/8/20265进栈seqstack*PUSH(seqstack*s,datatypex){if(s->top==maxsize-1){printf(“overflow\n”);returnNULL;}else{s->top++;s->data[s->top]＝x;}returns;}6/8/20268退栈datatypePOP(seqstack*s){if(EMPTY(s)){printf(“underflow\n”);returnNULL;}else{s->top--;return(s->data[s->top+1]);}}6/8/20269取栈顶datatypeTOP(seqstack*s){if(EMPTY(s)){printf(“underflow\n”);returnNULL;}elsereturn(s->data[s->top]);}6/8/202610两个堆栈共享空间0maxsize-1lefttoprighttop6/8/202611栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作6/8/202612栈的链接存储结构链栈的结点定义typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linkstack;

6/8/202613链栈的进栈算法linkstack*PUSHLSTACK(linkstack*top,datatypex){linkstack*p;p＝malloc(sizeof(linkstack));p->data＝x;p->next＝top;returnp;}6/8/202614链栈的出栈算法linkstack*POPLSTACK(linkstack*top,datatype*datap){linkstack*p;if(top==NULL){printf(“underflow\n”);returnNULL;}else{*datap＝top->data;p＝top;top＝top->next;free(p);returntop;}}6/8/202615例：对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB6/8/202616栈的应用举例－－文字编辑器seqstacks;EDIT(){charc;SETNULL(&s);c＝getchar();while(c!=‘*’){if(c==‘#’)POP(&s);elseif(c==‘@’)SETNULL(&s);elsePUSH(&s,c);c＝getchar();}}6/8/202617栈的应用－－递归函数intFACT(intn){if(n==1)return(1);elsereturn(n*FACT(n-1));}

6/8/202618栈的应用－－表达式计算中缀表达式：A+(B–C/D)×E后缀表达式：ABCD/－E×+（逆波兰表达式）后缀表达式特点1、与相应的中缀表达式中的操作数次序相同2、没有括号6/8/202619后缀表达式的处理过程操作顺序后缀表达式ABCD/－E×+T1←C/DABT1－E×+T2←B–T1AT2E×+T3←T2×EAT3+T4←A+T3T46/8/202620ABCDE＋×－／ABCT1＋×－ABT2＋×AT3＋6/8/202621中缀表达式转换为后缀表达式＋－×／()#＋>><<<>>－>><<<>>×>>>><>>／>>>><>>(<<<<<=)>>>>>>#<<<<<=当前运算符栈顶运算符6/8/202622中缀表达式转换为后缀表达式的处理规则1、如为操作数，直接输出到队列；2、若当前运算符为“（”，则直接入栈；2、如当前运算符高于栈顶运算符，入栈；3、如当前运算符低于栈顶运算符，栈顶运算符退栈，并输出到队列，当前运算符再与栈顶运算符比较；4、如当前运算符为“）”，则将栈中“（”以后的字符依次弹出存入输出到队列，然后将“）”弹出退栈。继续读下一符号；5、如当前运算符等于栈顶运算符，且栈顶运算符为“#”，当前运算符也为“#”，则栈顶运算符退栈，处理结束；6/8/202623步骤中缀表达式STACK输出1A＋(B－C／D)×E##2＋(B－C／D)×E##A3(B－C／D)×E##＋A4B－C／D)×E##＋(A5－C／D)×E##＋(AB6C／D)×E##＋(－AB7／D)×E##＋(－ABC8D)×E##＋(－/ABC9)×E##＋(－/ABCD6/8/202624步骤中缀表达式STACK输出10×E##＋(－ABCD/11×E##＋(ABCD/－12×E##＋ABCD/－13E##＋×ABCD/－14##＋×ABCD/－E15##＋ABCD/－E×16##ABCD/－E×＋6/8/202625队列(

Queue)定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)6/8/202626队列的进队和出队

进队时队尾指针先进一rear=rear+1，再将新元素按

rear

指示位置加入。出队时队头指针先进一front=front+1，再将下标为front的元素取出。

队满时再进队将溢出出错；队空时再出队将队空处理。6/8/202627顺序队列的指针说明typedefstruc{datatypedata[maxsize];intfront,rear;}sequeue;6/8/202628队列的基本操作1、置空队列2、判定队列是否为空3、取队列头元素4、将新元素插入队尾5、队列头元素出队6/8/202629顺序队列置队空SETNULL(sequeue*sq){sq->front＝maxsize-1;sq->rear＝maxsize-1;}6/8/202630顺序队列判队空intEMPTY(sequeue*sq){if(sq->rear==sq->front)return(TRUE);elsereturn(FALSE);}

6/8/202631顺序队列取队头元素datatypeFRONT(sequeue*sq){if(EMPTY(sq)){printf(“queueisempty\n”);returnNULL;}elsereturn((sq->front+1)%maxsize);}6/8/202632顺序队列入队intENQUEUE(sequeue*sq,datatypex){if(sq->front==(sq->rear+1)%maxsize){printf(“sequeueisfull\n”;returnNULL);}else{sq->rear＝(sq->rear+1)%maxsize;sq->data[sq->rear]＝x;return(TRUE);}}6/8/202633顺序队列出队datetypeDEQUEUE(sequeue*sq){if(EMPTY(sq)){printf(“queueisempty\n”);returnNULL;}else{sq->front＝(sq->front+1)%maxsize;return(sq->data[sq->front]);}}6/8/202634存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize

-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:

front=(front+1)%maxSize;

队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%maxSize==front

循环队列(CircularQueue)6/8/202635循环队列的进队和出队6/8/202636队列的链接表示—链式队列队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为front==NULL6/8/202637链队列结点类型定义typedefstructnode{datatypedata;structnode*next;}linklist;typedefstruct{linklist*front,*rear;}linkqueue;6/8/202638链队列置队空SETNULL(linkqueue*q){q->front＝malloc(sizeof(linklist));q->front->next＝NULL;q->rear＝q->front;}

6/8/202639链队列判队空intEMPTY(linkqueue*q){ifq->front==q->rear)return(TRUE);elsereturn(FALSE);}

6/8/202640链队列取队头结点datatypeFRONT(linkqueue*q){if(EMPTY(q)){printf(“queueisempty\n”);returnNULL;}elsereturn(q->front->next->data);}

6/8/202641链队列入队ENQUEUE(linkqueue*q,datatypex){q->rear->next＝(linklist*)malloc(sizeof(linklist));q->rear＝q->rear->next;q->rear->data＝x;q->rear->next＝NULL;}

6/8/202642链队列出队datatypeDEQUEUE(linkqueue*q){linklist*s;if(EMPTY(q)){printf(“queueisempty\n”);returnNULL;}else{s＝q->front;q->front＝q->front->next;free(s);return(q->front->data);}}

6/8/20264301110111101010100100111101110011100110000110011012345678123456队列的应用举例－－求迷宫的最短路径6/8/202644zxzy1-102-1+130+14+1+15+106+1-170-18-1-1需要解决的问题1：如何从某一坐标点出发搜索其四周的邻点6/8/202645需要解决的问题2：如何存储搜索路径需要解决的问题3：如何防止重复到达某坐标点步xypre1110222133324343…………6/8/202646需要解决的问题4：如何输出搜索路径1…121314151617181920x1…525656656…y1…663175488…pre0…8910101112141616…队列6/8/202647#definem10#definen15

typedefstruct{