第三章栈和队列

1、 第三章 栈和队列3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现3.2 栈的应用举例3.3 队列 3.3.1 抽象数据类型队列的定义 3.3.2 队列的表示和实现栈的定义栈栈是只能在表尾插入和删除的线性表。入栈出栈anan-1a1栈顶栈底后进先出后进先出练习一个栈的入栈序列是ABCDE，则其输出序列不可能是（ ）A,EDCBAB,DECBAC,DCEABD,ABCDEC顺序栈-存储结构以顺序存储方式存储的栈叫做顺序栈顺序栈。basetopbasetopABCDEbasetopAB顺序栈-存储结构类型说明：#define MAXSIZE 100typedef struc

2、tSElemType *base;SElemType *top;int stacksize;SqStack栈的运算初始化栈：InitStack(S)取栈顶元素：GetTop(S,x)入栈：Push(S,x)出栈：Pop (S)初始化栈：void InitStack(SqStack &S) S.base=(SElemType *)malloc(MAXSIZE*sizeof(SElemType); if(!S.base)exit(-1); S.top=S.base; S.stacksize=MAXSIZE; 取栈顶元素：SElemType GetTop(SqStack S) if(S.to

3、p=S.base)exit(-1); else return *(S.top-1); 入栈：void Push (SqStack &S, SElemType x) if (S.top-S.base=S.stacksize) error(“溢出”); else *S.top+=x; n出栈：void Pop (SqStack &S, SElemType &x) if(S.top=S.base)error(“栈空，不能删除”);else x= *-S.top; 链栈用动态方式来存储栈可节省空间采用链表存储的栈为链栈链栈由于栈的操作是线性表操作的特例，所以不作详细讨论。a1a

4、2a3an top3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 迷宫求解 3.2.4 表达式求解 3.2.2 括号匹配问题算法的设计思想：（1）若是“左括号”，则入栈；（2）若是“右括号”，则有两种情况： a) 若栈空，则表明“右括号”多了，匹配失败； b) 否则，与栈顶元素比较： 若相匹配，则“左括号”出栈； 否则匹配失败。（3）当表达式检验结束时： 若栈空，匹配成功； 否则表明“左括号”多了，匹配失败。算法如下：Status matching(string &exp) int state=1; while(ifront=0; Q-rear=0;

5、n判断队列是否为空：BOOL queue_empty(seqqueue Q) if (Q.front=Q.rear) return TRUE; else return FALSE; n判断队列是否为满：BOOL queue_full(seqqueue Q) if (1+Q.rear) % maxsize=Q.front) return TRUE; else return FALSE; 尾指针的下一个位置是头指针所指位置时为满n入队void Enqueue(seqqueue * Q,elementtype x)if (full(Q) error(“溢出”); else Q-rear=(1+Q-r

6、ear) % maxsize; Q-dataQ-rear=x； 循环队列的运算取队头元素：elementtype queue_front(seqqueue Q,elementtype *x) if (queue_empty(Q) )error(“队空”);else *x=Q.data(Q.front+1)% maxsize); n出队void Outqueue(seqqueue * Q, elementtype *x)if (empty(*Q) )error(“队空，不能出队”); else Q-front=(Q-front+1) % maxsize; *x= Q-dataQ-front; 链

7、队列-存储结构头指针始终指向表头，尾指针始终指向表尾；采用带头节点的链表形式。a1a2anfrontrearlinkqueue类型说明typedef struct node *front,*rear； /仅需要头尾指针即可 linkqueue链队列的运算初始化队列：void init_queue(linkqueue *Q) Q-front=(node *)malloc(sizeof(node); Q-rear=Q-front; Q-front-next=NULL; n取队头元素：void queue_front(linkqueue * Q, elementtype * x); if (empt

8、y(*Q) ) error(“队空，不能取元素”); else *x=Q-front-next-data; n判断队为空：BOOL queue_empty(linkqueue Q) return Q.front=Q.rear;链队列的运算入队：void Enqueue(linkqueue * Q, elementtype x) node *P=(node *)malloc(sizeof(node); P-data=x; P-next=NULL; Q-rear-next=P; Q-rear=P; n出队：void Outqueue(linkqueue * Q, elementtype * x); if (empty(*Q) )error(“队空，不能出队”); else *x=Q-front-next-data; node * u=Q-fron