第3章栈和队列 要求 1、掌握栈与队列的逻辑结构 2、栈和队列的顺序存储和链式存储表示,即顺序栈、链栈如何表示:链队列与循环队列如何 表示 3、不同存储方式下操作算法 教材习题参考解答 3.1(1)有5种:123、321、132、213、231 (2)能得到135426,不能得到435612 3.2A 、顺序栈 #define maXsize 100 typedef struct ElemType elem [MAXSIZE I SeqStack: int IsEmpty(SeqStack *pS) return (pS->top==-1 int IsFull(SeqStack *pS) return (pS->top = MAXSIZE-1? 1: 0) 、链栈 typedef struct next ElemType data struct node *k next I NODE, *LinkStack int IsEmpty (Link Stack S) return(S->next = NULL 1: 0) 3.4参考教材P59~60 3.5//此程序为判断一个字符串是否为回文。字符串以@结尾 //中间以&’分隔 //程序的实现通过一个栈和一个队列来实现,首先将’&以前的所有字符压入栈 /然后将’&后的字符加入队列,再分别进行出栈和出队处理,比较栈顶和队头的字符
第 3 章 栈和队列 要求： 1、掌握栈与队列的逻辑结构； 2、栈和队列的顺序存储和链式存储表示，即顺序栈、链栈如何表示；链队列与循环队列如何 表示； 3、不同存储方式下操作算法。 教材习题参考解答： 3.1 (1)有 5 种：123、321、132、213、231 (2)能得到 135426，不能得到 435612。 3.2 A 3.3 一、顺序栈 #define MAXSIZE 100 typedef struct { ElemType elem[MAXSIZE]; int top; }SeqStack; int IsEmpty(SeqStack *pS) { return (pS->top==-1 ? 1 : 0); } int IsFull(SeqStack *pS) { return (pS->top == MAXSIZE-1 ? 1 : 0); } 二、链栈 typedef struct next { ElemType data; struct node * next; }NODE, *LinkStack; int IsEmpty(LinkStack S) { return (S->next == NULL ? 1 : 0); } 3.4 参考教材 P59～60 3.5 //此程序为判断一个字符串是否为回文。字符串以'@'结尾， //中间以'&'分隔 //程序的实现通过一个栈和一个队列来实现，首先将'&'以前的所有字符压入栈 //然后将'&'后的字符加入队列，再分别进行出栈和出队处理，比较栈顶和队头的字符
#include next NULL: //入栈算法 int Push(LinkStack S, char e) LinkStack p p =(LinkStack)malloc(sizeof (NODE)) f(!p) //若创建结点不成功则返回0 return 0: //将新创建结点插入头结点之后 p->next S->next S->next =p retu //出栈算法 int Pop(LinkStack S, char *pe) LinkStack if(S->next==NULL)//若栈为空,则不能出栈,返回0 return 0 S->next p->next *pe p->data free(p) return /初始化队列算法 void InitQueue(LinkQueue *pQ)
#include #include //栈和队列均用链表实现，队列用循环队列 typedef struct node { char data; struct node *next; }NODE, *LinkStack, *LinkQueue; //初始化栈，创建一个头结点 void InitStack(LinkStack *pS) { LinkStack p; p = (LinkStack)malloc(sizeof(NODE)); p->next = NULL; *pS = p; } //入栈算法 int Push(LinkStack S, char e) { LinkStack p; p = (LinkStack)malloc(sizeof(NODE)); if(!p) //若创建结点不成功则返回 0 return 0; //将新创建结点插入头结点之后 p->data = e; p->next = S->next; S->next = p; return 1; } //出栈算法 int Pop(LinkStack S, char *pe) { LinkStack p; if(S->next == NULL) //若栈为空，则不能出栈，返回 0 return 0; p = S->next; S->next = p->next; *pe = p->data; free(p); return 1; } //初始化队列算法 void InitQueue(LinkQueue *pQ) {
LinkQueue p p=(LinkStack)malloc(sizeof (NODE)) //形成一个环形链表 /进队算法,pQ为指向队尾结点的指针的指针 int EnQueue(LinkQueue *pQ, char e) LinkQueue p, Q: Q=**pQ //让Q指向队尾 p=(LinkStack)malloc(sizeof (NODE)) if(p) //如果创建结点不成功 return 0 //将p结点插入pQ之后 ->data =e: *p Q=p retu //出队算法 int DeQueue(LinkQueue *pQ, char *pe) LinkQueue p, Q Q=*pQ Q=*pQ //让Q指向队尾 //让Q指向头结点 Q==*pQ)/如果仅有头结点,则说明队列为空 return //如果不为空队,则进行出队处理 /先让p指向头结点的后继结点,再将p结点删除 *pe p->data a->next = p->next fr //如果出队后为空队,则原队尾指针的值要改变,即指向头节点 f(Q->next = Q) return 1 id maino
LinkQueue p; p = (LinkStack)malloc(sizeof(NODE)); p->next = p; //形成一个环形链表 p->data = 0; *pQ = p; } //进队算法，pQ 为指向队尾结点的指针的指针 int EnQueue(LinkQueue *pQ, char e) { LinkQueue p, Q; Q = *pQ; //让 Q 指向队尾 p = (LinkStack)malloc(sizeof(NODE)); if(!p) //如果创建结点不成功 return 0; //将 p 结点插入 pQ 之后 p->data = e; p->next = Q->next; Q->next = p; *pQ = p; return 1; } //出队算法 int DeQueue(LinkQueue *pQ, char *pe) { LinkQueue p, Q; Q = *pQ; Q = *pQ; //让 Q 指向队尾 Q = Q->next; //让 Q 指向头结点 if( Q == *pQ ) //如果仅有头结点，则说明队列为空 return 0; //如果不为空队，则进行出队处理 //先让 p 指向头结点的后继结点，再将 p 结点删除 p = Q->next; *pe = p->data; Q->next = p->next; free(p); //如果出队后为空队，则原队尾指针的值要改变，即指向头节点 if( Q->next == Q) *pQ = Q; return 1; } void main() {
char str[80], chl, ch2,= LinkStack s InitStack(&S) InitQueue(&Q) printf("请输入一个待判断是否为回文的字符串,以@结尾,中间为&':\n") str /分别对”&’前面的字符入栈,对后面的字符进队 while(*p) if((z==0)&&(*p!='&)&&(*p!='g)) if((z==1)&&(*!='&)&&(*p!='@)) EnQueue(&Q, *p) while( pop s, &ch1)&& DeQueue(&Q, &ch2) if(ch1!= ch2) printf("不是回文!n") sf =0 if(sf==1 && Pop(s, &ch1)&&! DeQueue( &Q, &ch2)) printf("是回文!n") else printf("不是回文!n") 解法二://利用栈实现回文判断 #include #define max 80 //定义顺序栈结构 typedef struct
char str[80], ch1,ch2, *p; int z=0,sf=1; LinkStack S; LinkQueue Q; InitStack(&S); InitQueue(&Q); printf("请输入一个待判断是否为回文的字符串，以'@'结尾，中间为'&'：\n"); gets(str); p = str; //分别对'&'前面的字符入栈，对后面的字符进队 while(*p) { if( (z==0) && (*p != '&') && (*p !='@') ) Push(S, *p); if( (z==1) && (*p != '&') && (*p !='@') ) EnQueue(&Q, *p); if( *p == '&' ) z = 1; if( *p == '@') break; p++; } while( Pop(S, &ch1) && DeQueue(&Q, &ch2)) { if(ch1 != ch2) { printf("不是回文！\n"); sf = 0; break; } } if(sf==1 && !Pop(S, &ch1) && !DeQueue(&Q,&ch2)) printf("是回文！\n"); else if(sf==1) printf("不是回文！\n"); } 解法二：//利用栈实现回文判断 #include #include #define MAX 80 //定义顺序栈结构 typedef struct {
char elem[MAX int to ISTACK void Init Stack (STACK *pS pS-top=-1;//top为栈顶元素在数组elem中的下标,由于开始没有元素,则为-1 int Push(STACK *pS, char e) if(ps->top >= MAX-1) return 0 pS->top++;/(改变栈顶位置 pS->elem [pS->top]=e return 1 int Pop (stacK =ps, char *pe if(ps->top ==-1 return 0 *pe= pS->elem[ps->top pS->top- return 1 void maino char str[80, cl, c2, *p; STACK S: Init Stack(&S) printf("请输入一串以@结尾中间为’&’字符的字符串:") //将’&’前面的字符依次入栈 while(*p!=”&’&&*p!=’10’) if(! Push(&S, *p)) printf("栈空间溢出!") exit(o)
char elem[MAX]; int top; }STACK; void Init_Stack(STACK *pS) { pS->top = -1; //top 为栈顶元素在数组 elem 中的下标，由于开始没有元素，则为－1 } int Push(STACK *pS, char e) { if(pS->top >= MAX-1) return 0; pS->top++; //改变栈顶位置 pS->elem[pS->top] = e; return 1; } int Pop(STACK *pS, char *pe) { if(pS->top == -1) return 0; *pe = pS->elem[pS->top]; pS->top--; return 1; } void main() { char str[80], c1,c2,*p; STACK S; Init_Stack(&S); printf("请输入一串以'@'结尾中间为'&'字符的字符串："); gets(str); p = str; //将'&'前面的字符依次入栈 while(*p != '&' && *p != '\0') { if(!Push(&S, *p)) { printf("栈空间溢出！"); exit(0); } p++;
//跳过”&’字符 ∥/依次取出’&’后面的字符,每取一个字符就和从栈中弹出的一个字符比较,如果相等 //则继续取下一个。 le(*p!='g’&&*!=’10’) if(! Pop(&S, &c2)) printf("栈已为空,不是回文,’&’前面的字符少!n"); exit(o) if(c1!=c2) printf("对应字符不相等,不是回文!n") exit(o) if(Pop( &s, &c2)) printf("&'前的字符比后面多,栈内还有字符,不是回文!mn"); exit(o) els printf("是回文!\n") 3.6逆波兰式就是运算符在两个运算数后面的运算式,方法与表达式求值类似。 3.7//仅用队尾指针指向环行链表表示队列的三个算法 #include #include <stili typedef struct int data;//设队列的元素为整数类型 struct node * next INode typedef struct Node* front;//指向队头的指针 Node * real //指向队尾的指针 I LinkQueue void Init(LinkQueue *pQ)
} p++; //跳过'&'字符 //依次取出'&'后面的字符，每取一个字符就和从栈中弹出的一个字符比较，如果相等 //则继续取下一个。 while(*p != '@' && *p != '\0') { c1 = *p; if(!Pop(&S, &c2)) { printf("栈已为空，不是回文，'&'前面的字符少！\n"); exit(0); } if( c1 != c2) { printf("对应字符不相等，不是回文！\n"); exit(0); } p++; } if(Pop(&S, &c2)) { printf("'&'前的字符比后面多，栈内还有字符，不是回文！\n"); exit(0); } else printf("是回文！\n"); } 3.6 逆波兰式就是运算符在两个运算数后面的运算式，方法与表达式求值类似。 3.7 //仅用队尾指针指向环行链表表示队列的三个算法 #include #include typedef struct node { int data; //设队列的元素为整数类型 struct node *next; }Node; typedef struct { Node *front; //指向队头的指针 Node *rear; //指向队尾的指针 }LinkQueue; void Init(LinkQueue *pQ)
p=(Node *)malloc(sizeof (Node)) /形成一个环链 pQ->rear=p;//队尾指针指向环链 void EnQueue(LinkQueue *pQ, int e) Node *p, **q; p=(Node *)malloc(sizeof(Node)) q= pQ->rear;/让q指向队尾结点 p>next= g->next;//以下两个语句将p所指结点插到q所指结点的后面 q>next p->data =e: pQ->rear=p;//p所指结点成为新的队尾 int DeQueue(LinkQueue *pQ, int *pe q= pQ->rear->next;//让q指向链的头结点 q)//队为空则不能出队 return(O) //p指向队头结点 g->next p-> //将p所指结点从链中断开 if( pQ->rear=p)//若p所指结点又是队尾结点,则删除p后成为空队 free(p) return(1) void Print(LinkQueue *pQ) q= pQ->rear->next //q指向头结点 //p指向队头结点 printf( %d\t", p->data) p p->next printf( \n")
{ Node *p; p = (Node *)malloc(sizeof(Node)); p->next = p; //形成一个环链 pQ->rear = p; //队尾指针指向环链 } void EnQueue(LinkQueue *pQ, int e) { Node *p, *q; p = (Node *)malloc(sizeof(Node)); q = pQ->rear; //让 q 指向队尾结点 p->next = q->next;//以下两个语句将 p 所指结点插到 q 所指结点的后面 q->next = p; p->data = e; pQ->rear = p; //p 所指结点成为新的队尾 } int DeQueue(LinkQueue *pQ, int *pe) { Node *p, *q; q = pQ->rear->next; //让 q 指向链的头结点 if(q->next == q) //队为空则不能出队 return (0); p = q->next; //p 指向队头结点 q->next = p->next; //将 p 所指结点从链中断开 if(pQ->rear == p) //若 p 所指结点又是队尾结点，则删除 p 后成为空队 pQ->rear = q; free(p); return(1); } void Print(LinkQueue *pQ) { Node *p, *q; q = pQ->rear->next; //q 指向头结点 p = q->next; //p 指向队头结点 while(p != q) { printf("%d\t",p->data); p = p->next; } printf("\n"); }
void maino EnQueue(&Q, 10) EnQueue(&Q, 20) Print(&Q) EnQueue(&Q, 30) DeQueue(&Q, &1) Print(&Q) 3.8//p77习题3.8 #include #define maXsize 20 typedef struct int element [mAXSIZEI int front int rear int flag;/flag为0表示队列不满,为1表示队列满 void Init(seqQueue *pQ) pQ->flag =0: pQ->rear =0 pQ->front int EnQueue(SeqQueue *pQ, int e) if(pQ->flag = 0) pQ->element [pQ->rear]=e pQ->rear =(pQ->rear + 1)% MAXSIZE if(pQ〉rear==pQ-) front)//若进队后rear与 front相等,则队列满 pQ->flag =1 return(1) 1 return(O)
void main() { int i; LinkQueue Q; Init(&Q); EnQueue(&Q,10); EnQueue(&Q,20); Print(&Q); EnQueue(&Q,30); DeQueue(&Q,&i); Print(&Q); } 3.8 //p77 习题 3.8 #include #define MAXSIZE 20 typedef struct { int element[MAXSIZE]; int front; int rear; int flag; //flag 为 0 表示队列不满，为 1 表示队列满 }SeqQueue; void Init(SeqQueue *pQ) { pQ->flag = 0; pQ->rear = 0; pQ->front = 0; } int EnQueue(SeqQueue *pQ, int e) { if(pQ->flag == 0) { pQ->element[pQ->rear] = e; pQ->rear = (pQ->rear + 1) % MAXSIZE; if(pQ->rear == pQ->front) //若进队后 rear 与 front 相等，则队列满 pQ->flag = 1; return(1); } else return(0);
int DeQueue(SeqQueue *pQ, int *pe) 0)&&(pQ->front = pQ->rear)) return(0) *pe= pQ->element [pQ->front] pQ->front =(pQ->front +1)% MAXSIZE if(pQ->flag=1)//若原来是满队列,则出队一个后变为不满 pQ->fl void maino Seqqueue Q int e Init(&Q EnQueue(&Q, 10) EnQueue( &Q, 20) DeQueue(&Q, &e) printf("出队的元素是:%d\n",e) printf("队列中剩下的的元素是:") for(i =Qfront Q rear (i 1)%MAXSIZE) printf(%d\t",Q element [il) 3.9(1)将栈S中元素逆置 (2)将栈S中元素e删除 (3)将队列Q中元素逆置 补充练习: 1、在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指 针,则当做出栈处理时,top变化为 A)top不变 B)top= C)top-- D)top++ 2、在具有n个单元的顺序存储的循环队列中,假定 front和rear分别为队头指针和队尾指针, 则判断队满的条件为 A) rear%n=front B)front%n+1=rear C)rear%n=front D)rear%n+1=front 3、一个中缀算术表达式为1+(3-x)*y,则其对应的后缀算术表达式为 A)13+x-y* B)13x+y*C)13x-y*+D)13xy-+ 4、在一个链队列中,假定 front和rear分别为队首和队尾指针,则插入*s结点的操作应执 行 A)front->next=s: front=s B)s->next=rear: rear=s
} int DeQueue(SeqQueue *pQ, int *pe) { if((pQ->flag == 0)&&(pQ->front == pQ->rear)) return (0); *pe = pQ->element[pQ->front]; pQ->front = (pQ->front + 1) % MAXSIZE; if(pQ->flag == 1) //若原来是满队列，则出队一个后变为不满 pQ->flag = 0; return(1); } void main() { SeqQueue Q; int e, i; Init(&Q); EnQueue(&Q,10); EnQueue(&Q,20); EnQueue(&Q,30); DeQueue(&Q,&e); printf("出队的元素是：%d \n",e); printf("队列中剩下的的元素是："); for(i = Q.front; i != Q.rear; i = (i + 1)%MAXSIZE) printf("%d\t",Q.element[i]); } 3.9 (1)将栈 S 中元素逆置 (2)将栈 S 中元素 e 删除 (3)将队列 Q 中元素逆置 补充练习： 1、在一个具有 n 个单元的顺序栈中，假定以地址低端（即 0 单元）作为栈底，以 top 作为栈顶指 针，则当做出栈处理时，top 变化为 。 A) top 不变 B) top=0 C) top-- D) top++ 2、在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头指针和队尾指针， 则判断队满的条件为 。 A) rear%n=front B) front%n+1=rear C) rear%n=front D)rear%n+1=front 3、一个中缀算术表达式为 1+(3-x)*y，则其对应的后缀算术表达式为 。 A) 1 3 +x –y* B) 1 3 x +-y * C)1 3 x –y *+ D) 1 3 x y -+* 4、在一个链队列中，假定 front 和 rear 分别为队首和队尾指针，则插入*s 结点的操作应执 行 。 A) front->next=s; front=s; B)s->next=rear; rear=s;
C) rear->next=s: rear=s D)s->next=front: front=s 5、在一个链队列中,假定 front和rear分别为队首和队尾指针,则删除一个结点的操作应执 行 A)front=front->next Brear=rear->next C) rear=front->next D)front=rear->next 6、写出下列程序段的输出结果(其中栈的元素类型 SElemType为char) void i Stack S; char x, y: InitStack(S Push(s, x): Push(S, ,a'): Push(S, y): Pop(s, x) Push(s, 't'): Push(S, x): Pop (S, x ): Push(S, 's") while(! StackEmpty(S))[Pop(s, y): printf(y); printf(x) 7、写出以下程序段的输出结果(队列中的元素类型 QElemType为char)。 void maino i Queue Q: char x='e InitQueue(Q) EnQueue( Q, 'h): EnQueue(Q, r"): EnQueue(, y): De Queue(Q, x) EnQueue(Q, x): De Queue(Q, x): En Queue(Q, ' a') while(! QueueEmpty( Q))I DeQueue( Q, y): printf(y): 1 printf(x) 8、若栈用顺序存储表示,其栈的元素类型为整型,类型定义如下 #define maXsize 1000 typedef struct I int elem[ MAXSIZE];/用来存放栈元素的数组,下标从0开始 int top //指向栈顶位置的域,栈底为位置0 请补全以下栈操作函数:(用C语言) (1)判断栈S是否为空栈:若为空,则返回1,不为空则返回0 nt StackEmpty (Stack S) return(1) (2)入栈操作:若栈满,则返回0,不满,则入栈,返回1 int push( Stack*p,inte){//p为指向栈的指针,e为待入栈的元素 if( ) return(O);/栈满,则返回0 =e;//入栈 p->top+=l /栈顶位置变化 return(1)
C) rear->next=s; rear=s; D)s->next=front; front=s; 5、在一个链队列中，假定 front 和 rear 分别为队首和队尾指针，则删除一个结点的操作应执 行 。 A) front=front->next; B)rear=rear->next; C) rear=front->next; D)front=rear->next; 6、写出下列程序段的输出结果（其中栈的元素类型 SElemType 为 char） void main() { Stack S; char x,y; InitStack(S); x=’c’; y=’k’; Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x); Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’); while(!StackEmpty(S)){Pop(S,y); printf(y); }; printf(x); } 7、写出以下程序段的输出结果（队列中的元素类型 QElemType 为 char）。 void main() { Queue Q; char x=’e’,y=’c’; InitQueue(Q); EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a’); while(!QueueEmpty(Q)){ DeQueue(Q,y); printf(y);} printf(x); } 8、若栈用顺序存储表示，其栈的元素类型为整型，类型定义如下： #define MAXSIZE 1000 typedef struct{ int elem[MAXSIZE]; //用来存放栈元素的数组，下标从 0 开始 int top; //指向栈顶位置的域，栈底为位置 0 }Stack; 请补全以下栈操作函数：（用 C 语言） （1）判断栈 S 是否为空栈：若为空，则返回 1，不为空则返回 0 int StackEmpty(Stack S){ if( )return (1); else ; } （2）入栈操作：若栈满，则返回 0，不满，则入栈，返回 1 int Push(Stack *p,int e){ //p 为指向栈的指针，e 为待入栈的元素 if( )return(0);//栈满，则返回 0 =e; //入栈 p->top+=1; //栈顶位置变化 return(1); }
