河北大学：《数据结构》课程教学资源（习题解答）第三章 栈和队列

1栈和队列数据结构各有什么特点,什么情况下用到栈,什么情况下用到队列? 栈的特点是先进后出,所以在解决实际问题涉及到后进先出的情况 时,可以考虑使用栈。例如表达式地括号匹配问题等。 队列的特点是先进先出,所以在解决实际问题涉及到先进先出的情 况时,可以考虑使用队列。例如操作系统中的作业排队等 2设有编号为1,2,3,4的四辆车,顺序进入一个栈式结构的站台,试写出这四辆车开出车站的所 有可能的顺序(每辆车可能入站,可能不入站,时间也可能不等)。 所有可能得出栈顺序 4321,3421,3241,3214,2431,2341,2314,2143,2134, 1432,1342,1324,1243,1234。 所有不可能得出栈顺序 4312,4231,4213,4132,4123,3412,3142,3124,2413, 1423 3试证明:若借助栈由输入序列1,2,…,n得到输出序列为pp2pn(它是输入序列的一个排列) 则在输出序列中不可能出现这样的情形:存在着i>c while(cl=@) push stack(s, c ) in queue(Q, c) cIn>>C while (empty stack(s))

⒈栈和队列数据结构各有什么特点，什么情况下用到栈，什么情况下用到队列？ 栈的特点是先进后出，所以在解决实际问题涉及到后进先出的情况 时，可以考虑使用栈。例如表达式地括号匹配问题等。 队列的特点是先进先出，所以在解决实际问题涉及到先进先出的情 况时，可以考虑使用队列。例如操作系统中的作业排队等。 ⒉设有编号为 1，2，3，4 的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所 有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。 所有可能得出栈顺序： 4321，3421，3241，3214，2431，2341，2314，2143，2134， 1432，1342，1324，1243，1234。 所有不可能得出栈顺序： 4312，4231，4213，4132，4123，3412，3142，3124，2413， 1423 ⒊试证明：若借助栈由输入序列 1，2，… ，n 得到输出序列为 p1p2…pn (它是输入序列的一个排列)， 则在输出序列中不可能出现这样的情形：存在着 i>c; while (c!='@') { push_stack(s,c); in_queue(Q,c); cin>>c; } while (!empty_stack(s)) {

pop stack(s, &a) out queue( Q, &b) return(0); if(empty stack(s) return(1); 5设以数组sem]存放循环队列的元素,同时设变量rear和 front分别作为队头队尾指针,且队 头指针指向队头前一个位置,写出这样设计的循环队列入队出队的算法 (1)循环队列入队算法 int in queue(datatype se[m], int rear, int front, datatype e) if((rear+1)%=-front rear(rear+1)%m; selrear]=e: return(1) (2)循环队列出队算法 int out queue( dataty pe se[m],int rear, int front, datatype *e) if (rear-front return(-1); front=(front+1%m; e=sefton t]; return(1) 6假设以数组se[m存放循环队列的元素,同时设变量rear和num分别作为队尾指针和队中元素 个数记录,试给出判别此循环队列的队满条件,并写出相应入队和出队的算法 (1)入队算法 int in queue(datatype se[m],int rear, int num, datatype e) if(num==m) return(-1) rear(rear+1)%m

pop_stack(s,&a); out_queue(Q,&b); if (a!=b) return(0); } if (empty_stack(s)) return(1); } ⒌设以数组 se[m]存放循环队列的元素，同时设变量 rear 和 front 分别作为队头队尾指针，且队 头指针指向队头前一个位置，写出这样设计的循环队列入队出队的算法。 ⑴循环队列入队算法 int in_queue(datatype se[m],int rear,int front,datatype e) { if ((rear+1)%m==front) return(-1); rear=(rear+1)%m; se[rear]=e; return(1); } ⑵循环队列出队算法 int out_queue(datatype se[m],int rear,int front,datatype *e) { if (rear==front) return(-1); front=(front+1)%m; *e=se[front]; return(1); } ⒍假设以数组 se[m]存放循环队列的元素，同时设变量 rear 和 num 分别作为队尾指针和队中元素 个数记录，试给出判别此循环队列的队满条件，并写出相应入队和出队的算法。 ⑴入队算法 int in_queue(datatype se[m],int rear,int num,datatype e) { if(num==m) return(-1); rear=(rear+1)%m;

num++ return(1) (2)出队算法 int out queue( datatype se[m]int rear, int num, datatype*e) if (num==0) return (-1) *e=se[(rear-num+1)%m num-, return(1) 7假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指 针),试写出相应的置空队、入队、出队的算法 (1)队列初始化算法 linklist init queue() rear new ino rear→>next=rear return (rear) (2)入队算法 linklist in queue(linklist rear, datatype x) snew Inode s->data=x S->next-rear->next rear->next=s rears return(rear (3)出队算法 linklist out queue linklist rear, dataty pe*x) if (rear->next==rear)

se[rear]=e; num++; return(1); } ⑵出队算法 int out_queue(datatype se[m],int rear,int num,datatype *e) { if (num==0) return(-1); *e=se[(rear-num+1)%m]; num--; return(1); } ⒎假设以带头结点的循环链表表示一个队列，并且只设一个队尾指针指向尾元素结点（注意不设头指 针），试写出相应的置空队、入队、出队的算法。 ⑴队列初始化算法 linklist init_queue( ) { rear= new lnode; rear->next=rear; return(rear); } ⑵入队算法 linklist in_queue(linklist rear,datatype x) { s=new lnode; s->data=x; s->next=rear->next; rear->next=s; rear=s; return(rear ); } ⑶出队算法 linklist out_queue(linklist rear,datatype *x) { if (rear->next==rear)

return NULL) q-rear->next->next if(q==rear) rearrear->next rear->next-rear else rear->next->nextq->next *x=q->data delete q return(rear) 8.设计一个算法判别一个算术表达式的圆括号是否正确配对 Int process( init stack(s) cin>>c while(cl=@) push stack(s, c) if (empty stack(s)) pop stack(s, &a) else return (-1) cin>>c if(empty_ stack(s) return else return (-1)

return(NULL); q=rear->next->next; if (q==rear) { rear=rear->next; rear->next=rear; } else { rear->next->next=q->next; } *x=q->data; delete q; return(rear); } ⒏设计一个算法判别一个算术表达式的圆括号是否正确配对。 int process( ) { init_stack(s); cin>>c; while (c!='@') { if (c=='(') push_stack(s,c); if (c==')') { if (!empty_stack(s)) pop_stack(s,&a); else return(-1); } cin>>c; } if (empty_stack(s)) return(1); else return(-1);

9写一个算法,借助于栈将一个单链表置逆 linklist process(linklist a) p=A->next A->nextNULL init stack(s) while(p) push stack(s,p) p-p->next while(empty stack(s) pop stack(s, &q) q->next=A->next A->next=q return(A) 10两个栈共享向量空间vm],它们的栈底分别设在向量的两端,每个元素占一个分量,试写出两个栈 公用的栈操作算法:push(,x)、pop(1)和top(i),i=0和1,用以指示栈号 (1)压栈操作算法 int push stack( datatype v[m], int i, datatype x) if(top+1>=top1) return (-1) if(i==0) [++topO=x; v[--topl]= return(1) (2)出栈操作算法 datatype pop stack(dataty pe v[m] int i)

} ⒐写一个算法，借助于栈将一个单链表置逆。 linklist process(linklist a) { p=A->next; A->next=NULL; init_stack(s); while (p) { push_stack(s,p); p=p->next; } while (!empty_stack(s)) { pop_stack(s,&q); q->next=A->next; A->next=q; } return(A); } ⒑两个栈共享向量空间 v[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈 公用的栈操作算法：push(i,x)、pop(i)和 top(i)，i=0 和 1 ,用以指示栈号。 ⑴压栈操作算法 int push_stack(datatype v[m],int i,datatype x) { if (top0+1>=top1) return(-1); if (i==0) v[++top0]=x; else v[--top1]=x; return(1); } ⑵出栈操作算法 datatype pop_stack(datatype v[m],int i)

if(i==0) if(topOm-1) return( else return(v[top1++]; (3读栈顶元素操作 dataty pe top stack( datatype v[ml, int i) if(i==0) if(topm-1 return (-1) else return(v[topl);

{ if (i==0) if (top0m-1) return(-1); else return(v[top1++]); } ⑶读栈顶元素操作 datatype top_stack(datatype v[m],int i) { if (i==0) if (top0m-1) return(-1); else return(v[top1]); }