2023年栈的操作实验报告

实验三栈和队列实验目的：（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。实验规定：复习课本中有关栈和队列的知识；（2）用C语言完毕算法和程序设计并上机调试通过；（3）撰写实验报告，给出算法思绪或流程图和具体实现（源程序）、算法分析结果（涉及时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运营结果（必要时给出多种也许的输入数据和运营结果）。3.3基础实验［实验11栈的顺序表达和实现实验内容与规定：编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完毕如下功能：（1）初始化顺序栈（2）插入元素（3）删除栈顶元素（4）取栈顶元素（5）遍历顺序栈（6）置空顺序栈分析:

voidmain()｛叩rintf("=================链栈操作=================\n\n");LinkStack*s;0s=(LinkStack*)malloc(sizeof(LinkStack));。«intcord•次使用必须初始化!•次使用必须初始化!\n"）；•次使用必须初始化!\n"）；ado｛oprintf•次使用必须初始化!\n"）；oprin(f("\n")«printf("\ngprintf("\n1叩oprin(f("\n")«printf("\ngprintf("\n1叩rintf("\n§printf("\ngprintf("\n叩rintf("\n叩rintf("\n主菜单初始化链栈人栈出栈4取栈顶元素置空链栈结束程序运营\n°);\n")；\n")\n")；\n");\n");\n");O®printf("\n-——————-————————\n")；叩rintf("请输入您的选择(1,2,3,4,5,6)”);wscanf("%d"»&cord);O®printf("\n-—————O®printf("\n-——————-————————\n")；叩rintf("请输入您的选择(1,2,3,4,5,6)”);wscanf("%d"»&cord);sprintf("\nn);aswitch(cord)00000000Disp(s);｝break0000Disp(s);｝break；｝break｝break；acase2:g。{printf("输入将要压入链栈的数据的个数:n=")；scanf("%d"，&n)；printf("依次将％d个数据压入链栈：\n",n);gfor(i=l;i<=n;i++)aHscanf("%d",&a);a叩ushLstack(s,a);000|gDisp(s);g}break;8®case3：。{printf(”\n出栈操作开始!\n")；的printf("输入将要出栈的数据个数：m=");scanf("%d",&m);°ofor(i=1；i<=m;i++)皿{printf("\n第％d次出栈的数据是：%d",i,popLstack(s));}。Disp(s);。。)break;scase4：。{printf("\n\n链栈的栈顶元素为:％d\n",StackTop(s))；3«oprintf("\n");。}break;case5:g{osetEmpty(s);。。<>Disp(s);break；<>case6：aexit(0);ajwhile(cord<=6);［实验3］队列的顺序表达和实现实验内容与规定编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完毕如下功能:(1)初始化队列(2)建立顺序队列(3)入队(4)出队(5)判断队列是否为空(6)取队头元素(7)遍历队列分析：队列的顺序存储结构称为顺序队列，顺序队列事实上是运算受限的顺序表。入队时，将新元素插入rear所指的位置,然后将rear加1。出队时，删去front所指的元素,然后将front加1并返回被删元素。顺序队列中的溢出现象：(1)“下溢"现象。当队列为空时，做出队运算产生的溢出现象。"下溢''是正常现象，常用作程序控制转移的条件。“真上溢”现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种犯错状态,应设法避免。“假上溢"现象。由于入队和出队操作中，头尾指针只增长不减小，致使被删元素的空间永远无法重新运用。当队列中实际的元素个数远远小于向量空间的规模时,也也许由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为“假上溢”现象。注意：(1)当头尾指针相等时，队列为空。(2)在非空队列里，队头指针始终指向队头元素,尾指针始终指向队尾元素的卜一位置。参考程序：inc1ude<sldio.h>#include<malloc.h>defineMAXNUM100defineElemtypeint#defineTRUEI#defineFALSE0typcdefstruct{Elemtypequeue[MAXNUM];intfront;»intrear;}sqqueue；/*队列初始化*/intinitQueue(sqqueue*q){if(!q)returnFALSE;q->front=—1;«q->rcar=—1;»returnTRUE;/*入队*/intappend(sqqueue*q,Elemtypex){if(q->rear>=MAXNUM-l)returnFALSE;«*q->rear++;«q->queue[q->rear]=x;«returnTRUE;I/*出队*/ElemlypeDelete(sqqueue*q){oElemtypex：if(q->front==q->rear)return0；ax=q->queue[++q->front];oreturnx;}/*判断队列是否为空水/intEmpty(sqqueue*q){«if(q->front==q->rear)returnTRUE;returnFALSE;}/火取队头元素*/intgethead(sqqueue*q){if(q->front==q—>rcar)rcturn0;return(q->queue[q->front+l])；/火遍历队列*/voiddisplay(sqqueue*q){«ints;s=q->front;。if(q->front==q->rear)oprintf("队列空！\n");else{printf(”\n顺序队列依次为:");while(s<q->rear){s=s+l;gprintf(u%d<-",q->queue[s]);9)oprintf("Xn'1);Printf("顺序队列的队尾元素所在位置：rear=%d\n",q->rear);printf("顺序队列的队头元素所在位置：front=%d\nM,q->tront);o}}/*建立顺序队列*/voidSetsqqueue(sqqucue*q){intn,i,m；printf(”\n请输入将要入顺序队列的长度：”)；scanf("％d”,&n);printf("\ii请依次输入入顺序队列的元素值:\n");ofor(i=0;i<n;i++){scanf("%d".&m);append(q,m);}。main(){sqqueue*head;intx,y,z,select;head=(sqqueue*)ma1Ioc(sizeof(sqqueue));gdo{printf("\n第一次使用请初始化!'n")：。printf("\n请选择操作(1一一7):\n");°printf(M===================================5");-printf("1初始化\n”);叩rintf("2建立顺序队列\n")；8Printf("3入队\n”)；gprintf("4出队\n");printf("5判断队列是否为空\n”)；。printf("6取队头元素\n")：gprintf("7遍历队列\n");gprintf("===================================\n");wscanf("%d",&select);oswitch(select){case1:{initQueue(head)；printf("已经初始化顺序队列！\n");gbreak;00Icase2：g{Setsqqueue(head);printf(°\n已经建立队列!\n");display(head)；break;0}«case3:。{printf(”请输入队的值:\n");。«®scanf("%d",&x)；。。append(head,x);§。disp1ay(head);°»break;00)acase4:{«z=Delete(head);。gprintf("\n队头元素%(1已经出队!\n",z);。disp1ay(head);break；ao}。。case5:。Empty(head))o。。叩rintf("队列空\n”)；sooe1se。Printf("队列非空\n")；break;0)»«case6：8*{»y=gethead(head);oprintf("队头元素为:％d\n",y);break;00。«case7:g。{Misplay(head)；a^»break;00}00|«}while(sclcct<=7);0)［实验4］队列的链式表达和实现实验内容与规定：编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完毕如下功能：(1)初始化并建立链队列(2)入链队列(3)出链队列(4)遍历链队列分析：队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。注意：(1)和链枝类似，无须考虑判队满的运算及上溢。(2)在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。(3)和单链表类似，为了简化边界条件的解决,在队头结点前可附加一个头结点。参考程序：include<stdio.h>inc1ude<stdlib.h>defineEIemTypeinttypedefstructQnode{E1emTypedata;structQnode*next；}Qnodetypc;typedefstruct{»Qnodetype*front；Qnodetype*rear;}Lqueue:/*入链队列*/voidLappend(Lqueue*q,intx){oQnodetype*s；*s=(Qnodetype*)malloc(sizeof(Qnodetype));s->data=x；s->next=NULL;q->rear->next=s;。q->rear=s;)/*初始化并建立链队列大/voidcreat(Lqueuc*q){sQnodetype*h;ainti,n,x;叩rinlf("输入将建立链队列元素的个数:n=");栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。对于顺序栈，入栈时，一方面判断栈是否为满，栈满的条件为：p->top==MAXNUM・1,栈满时，不能入栈；否则出现空间溢出，引起错误,这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。注意：(1)顺序栈中元素用向量存放(2)栈底位置是固定不变的,可设立在向量两端的任意一个端点(3)栈顶位置是随着进校和退栈操作而变化的，用•个整型量top(通常称top为栈顶指针)来指示当前栈顶位置参考程序：#inckide<stdio.h>#include<stdlib.h>#defineMAXNUM20#dcfineElemTypeint/*定义顺序栈的存储结构*/typedefstruct{E1emTypestack[MAXNUM];“nttop；}SqStack：/*初始化顺序栈可voidInitStack(SqStack*p)"if(!p)叩rintf("Eorror'*)；oscanf("%d",&n)；3h=(Qnodetype*)malloc(sizeof(Qnodetype))；oh->next=NULL；»q->front=h:®q->rear=h；fbr(i=l;i<=n;i++)。{叩rintf("锥队列第％d个元素的值为：",i)；-scanfC'%d",&x);。Lappend(q,x)；})/*出链队列*/ElemTypeLdelete(Lqueue*q){Qnodetype*p;oElemTypcx;<>if(q->front==q->rear){叩rintf("队列为空！\n")；x=0；Ielsea{«p=q->front->next;q->front—>next=p->next;if(p->next==NULL)gq—>rear=q->front;*x=p->data；

free(p)；return(x);}/*遍历链队列文/voiddisplay(Lqueue*q){Qnodetypc*p;p=q->front->next;/*指向第一个数据元素节点*/printf("\n链队列元素依次为：")；whi1e(p!=NULL){printf(',%d->".p->data);叩=p->next：)printf("\n\n遍历链队列结束！\n")；}main(){Lqueue*p;»intx,cord；叩rintf("\n*****第一次操作请选择初始化并建立链队列！*****\n");Hl。。{printf("\n链队列的基本操作\n")；TOC\o"1-5"\h\zprintf("主菜单\n");cScf("-———')•[J]lll^j\\ygprintff1初始化并建立链队列\n")；printf(printf(printf(入链队列\n")；

printf(入链队列\n")；出链队列出链队列wprin(f("TOC\o"1-5"\h\zprintf("4遍历链队列\n");出链队列叩rintf(”5结束程序运营\n“)；00pmilH\iiascanf("%d",&cord)；«switch(cord)。{ocase1:g{p=(Lqueue*)mal1oc(sizeof(Lqueue))；。ocreat(p)；38display(p);。}break；，case2：8g{叩rintf("请输入队列元素的值:x=");a。scanf("%d",&x);。。oLappend(p,x)；3°display(p)；3g}break；。«case3:a。{printf("出链队列元素：x=%d\n",Ldelete(p));。。display(p);。。}break;case4：。{disp1ay(p);}break;{exit(0);){exit(0);){exit(0);)scase5：00000{exit(0);)“whiIe(cord<=5)；3.4提高实验［实验11迷宫的求解实验内容与规定：迷宫只有两个门，一个叫做人口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设立很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的途径。分析：迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有也许的通路都探索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能对的返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所可以到达的每一点的下标及从该点前进的方向,栈中保存的就是一条迷宫的通路。为了保证程序可以终止，调整时，必须保证曾被放弃过的填数序列不被再次实验，即规定按某种有序模型生成填数序列。给解的候选者设定一个被检查的顺序，按这个顺序逐个生成候选者并检查。参考程序::include<sldio.h>include<stdlib.h>definenI10#definen210typedefstructnode(intx;//存x坐标inty;〃存丫坐标intc;//存该点也许的下点所在的方向.1表达向右,2向上，3向左,4向右}linkstack;Iinkstacktop[100];〃迷宫矩阵intmaze[n1][n2]={1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,1,1J,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1JJ,0,0,0,0,1,1,0,0,01，0,0,0,0。1,0J,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,b1,1,1,1,1,1,1,1,1,};inti,j,k,m=0;main(){//初始化top口，置所有方向数为左for(i=0;i<nI*n2；i++){top[i],c=l;)printf(nthemazeis:\n");〃打印原始迷宫矩阵for(i=0;i<nl;i++){for(j=0;j<n2;j++)printf(maze[i][j]?"*");printf(''\n");}i=0;toP[ij.x=l;top[i].y=0;maze[1][0]=2;/*回溯算法*/do{if(top[i].c<5)”还可以向前试探{if(top[i].x==5&&top[i].y==9)〃已找到一个组合(〃打印途径prinIf("Theway%dis:\n",m++);for(j=0；j<=i：j++){printf("(%d,%d)—>",topfj].x,top[j].y);|printf("\n")；〃打印选出途径的迷宫for(j=0;j<n1;j++){for(k=0；k<n2;k++){if(maze[j][k]==0)printf("")；elseif(maze[j][k]==2)printf("O");elseprintfC*")；}printf('*\n");}maze[iop[i].x][top[i].y]=0;top[i],c=1;i-top[i].c+=I;continue；}switch(top[i].c)〃向前试探(case1：{if(maze[top[i].x][top[i].y+1]==0){i++；top[i].x=top[i—1].x;top[i].y=top[i-l].y+1;maze[top[i].x][top[i].y]=2；}e1se{top[i].c+=1;}break;}case2:{if(maze[top[i].x-1][lop[i].y]==0){i++；top[i].x=lop[i-l].x-1；top[i].y=top[i-l].y；maze[top[iJ.xj[top[iJ.y]=2;)eIse{top[i].c+=1：}break;}case3:{if(maze[top[i].x][top[i].y-l]==0){i++;top[i].x=top[i-1].x：top[i].y=top[i-1].y—I;maze[top[i].x][top[i].y]=2;}else{topfi].c+=1；}break；}case4:{if(maze[top[i].x+1][top[i].y]==0){i++；top[i].x=top[i—I].x+1;top[i].y=topLi-1].y;maze[top[i].x][top[i].yl=2;}else{top[i].c+=1;}break;}))eIse//回溯{if(i==0)return：〃已找完所有解maze[top[i].x][top[i].y]=0;top[i].c=1;i--;top[i].c+=1;}}while(l)；【实验21停车场管理实验内容与规定：设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第一辆车停放在车场的最北端)，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候,一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原顺序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述规定进行管理的模拟程序。分析：综合运用栈和队列模拟停车场管理，学习运用栈和队列解决实际问题。以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每•组输入数据涉及三个数据项：汽车“到达”或“拜别”信息、汽车牌照号码及到达或拜别的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车拜别;则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要拜别的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或拜别的时刻有序。栈中每个元素表达一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。设n=2,输入数据为：(火,1,5),CAS2,10),(D,1,15),「A',3,20),CA、,4,25),CA;5,30),(D,2,35),(D,4,40),(EQ,0)。每一组输入数据涉及三个数据项:汽车“到达”或“拜别”信息、汽车牌照号码及到达或拜别的时刻，其中「A，表达成达；"，表达拜别，下，表达输入结束。参考程序:。#include<stdio.h>inc1ude<stdlib.h>inc1ude<string.h>defineMAX2/*车库容量刃#defineprice0.05/*每车每分钟费用*/typedefstruettime{inthour;intmin;}Time;/*时间结点*/typedefstructnode{charnum[10];Timereach;Time1eave;}CarNode;/*车辆信息结点*/typedefstructNODE{CarNode*stack[MAX+1];inttop;}SeqStackCar；/*模拟车站号typedefstruc(car(CarNode*data；structcar*next;}QueueNode；typedefstructNodc{QueueNode*head;QueueNode*rcar;}LinkQueueCar;/*模拟通道*/)/*入栈*/voidPush(SqStack*p,ElemTypex){aif(p->top<MAXNUM-1)。{叩一>1。p=p->top+1;。叩->stack[p->topl=x;°)oelseprintf("Overflow!\n")；)/*出栈*/EIemTypePoP(SqStack*p){。E1emTypex;if(p->top!=0){x=p->stack[p->top];叩rintf("以前的栈顶数据元素％d已经被删除!\n",p->stack[p->top])；p->top=p->top-1;return(x);1。e1se{printf(uUnderf1ow!\n");retum(0);0))/*获取栈顶元素*/E1emTypeGetTop(SqStack*p)voidInitStack(SeqStackCar*);/*初始化栈*/intInitQueue(LinkQueueCar*);/*初始化便道*/intArrival(SeqStackCar*,LinkQueueCar*)；/*车辆到达*/voidLeave(SeqStackCar*,SeqStackCar*,LinkQueueCar*);/*车辆离开*/voidList(SeqStackCar,LinkQueueCar);/*显示存车信息*/voidmain(){ScqStackCarEnter,Temp；LinkQueueCarWait;intch;InitStack(&Enter);/*初始化车站*/InitStack(&Temp);/*初始化让路的临时栈*/InitQueue(&Wait);/*初始化通道*/while(l){printf("\n1.车辆到达")；Printf("2.车辆离开)printf("3.列表显示");printf("4.退出系统\n”)；while(l){scanf("%d",&ch);if(ch>=I&&ch<=4)break；elseprintf("\n请选择:1I2|3|4.");Iswitch(ch){case1：Arrival(&Enter,&Wait);break;/*车辆到达*/case2:Lcave(&Entcr,&Temp,&Wait);brcak;/*车辆离开*/case3:List(Enter,Wait);break;/*列表打印信息*/case4：exit(O);/*退出主程序*/defauIt:break;}})voidInitStack(SeqStackCar*s)/*初始化栈*/{inti;s->top=0;for(i=0;i<=MAX;i++)s—>stack[s->top]=NULL;}intInitQueue(LinkQueueCar*Q)/*初始化便道火/{Q->head=(QueueNode*)ma1loc(sizeof(QueueNode));if(Q->head!=NULL){Q—>head—>next=NULL；Q->rear=Q->head;return(l);)e1sereturn(-i);}voidPRINT(CarNode火p,introom)/*打印出站车的信息*/{intAI,A2,B1,B2；printf("\n请输入离开的时间：/**：**/");scanf("%d：%d(p->leave.hour),&(p—>leave,min));printf("\n离开车辆的车牌号为:“)；puts(p->num);printf("\n其到达时间为:%d:%d".p->reach.hour,p->reach.min);prinif("离开时间为：%d：%d",p->leave.hour,p—>lcave.min)；A1=p->reach.hour;A2=p->reach,min；B1=p->1eave,hour;B2=p->1eave.min;printf("\n应交费用为:％2.If元”，((B1-A1)*6O+(B2—A2))*price);free(p);}intArrival(SeqStackCar*Enter,LinkQueueCar*W)/*车辆到达*/{CarNode*p;QueueNode*t；P=(CarNode*)malloc(sizeof(CarNode));flushall();printf("\n请输入车牌号(例:陕A1234):")；gets(p->num);if(Enter—>top<MAX)/*车场未满，车进车场*/{Enter->top++;printf("\n车辆在车场第％d位置二Enter->top);printf("\n请输入到达时间:/**:**/")；scanf("%d:%d",&(p->reach.hour),&(p->reach.min))；Enter->stack[Enter->top]=p;return(1);}else/*车场已满，车进便道*/{printf("\n该车须在便道等待!”)；t=(QueueNode*)malloc(sizeof(QueueNode));t->da(a=p;t—>next=NULL;W->rear->next=t;W->rear=t;retum(l);}}voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W){/*车辆离开*/inti,room;CarNode*p,*t;QueueNode*q；/*判断车场内是否有车可if(Enter->top>0)/*有车*/{while(l)/*输入离开车辆的信息*/{printf("\n请输入车在车场的位置”,Enter・>top);scanf("％d”,&room)；if(room>=1&&rooni<=Enter—>top)break:}while(Enter->top>room)/*车辆离开*/{Temp->top++;Temp->stack[Temp->top]=Entcr->stack[Entcr->top]：Enter—>stack[Enter->top]=NULL；Enter->top-;)p=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top-;while(Temp->top>=1){Enter->top++;Enter->stack[Entcr—>top]=Tcmp—>stack[Tcmp->top];Temp->stack[Temp->top]=NULL;Temp->top-;}PRINT(p,room);/*判断通道上是否有车及车站是否-满*/if((W->head!=W->rear)&&Enter—>top<MAX)/*便道的车辆进入车场火/{q=W->head->next;t=q—>data;Enter->top+4-；printf("\n便道的％s号车进入车场第％d位置t->num,Enter->top);printf("\n请输入现在的时间/**：**/h;scanf("%d:%d",&(t->reach.hour),&(t->reach.min));W->head—>next=q->next;if(q==W->rear)W->rear=W—>head;Enter->stack[Enter->top]=t;free(q);}elseprintf("\n便道里没有车An")；}clscprintf("\n车场里没有车.”)；/*没车*/}voidListl(SeqStackCar*S)/*列表显示车场信息*/{inti;if(S->top>0)/*判断车站内是否有车*/{printf("\n车场)printf("\n位置到达时间车牌号\n”);for(i=l；i<=S—>top;i++){printf("%d",i);printf("%d:%d"»S—>stack[il->reach.hour,S->stack[i]->reach.min)；puts(S->stack[i]—>num);}}elseprintf("\n车场里没有车”)；}voidList2(LinkQucucCar*W)/*列表显示便道信息*/{QueueNode*p；p=W->head->next；if(W->head!=W->rear)产判断通道上是否有车*/{Printf("\n等待车辆的号码为巧；while(p!=NULL){puts(p->data->num);p=p->next;}}elseprintf("\n便道里没有车.");}voidList(SeqStackCarS,LinkQueueCarW){intflag,tag;flag=1;while(flag){printf("\n请选择1I2|3:");printf("\nl.车场\n2.便道\n3.返回\n")；whiic(l){scanf("%d”,&tag)；if(tag>=1I|tag<=3)break;elseprinif("\n请选择1|2|3:");}switch(tag){caseI：ListI(&S);break;/*列表显示车场信息*/case2：List2(&W)；break：芦列表显示便道信息*/case3:flag=O;break;default：break;}}}3.5思考题：(1)读栈顶元素的算法与退栈顶元素的算法有何区别？(2)假如一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分派一个足够大的存储空间。若每个栈都预分派过大的存储空间.势必会导致系统空间紧张。如何解决这个问题？(3)栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？(4)在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现,能否通过链栈来方便地实现?如何实现？(5)简述栈和队列的共同点和不同点。它们为什么属于线性表？(6)在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，但事实上队列中也许尚有空位置。此时若有元素入列，就会发生“假溢出”。如何解决这个问题？(7)链枝只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？(8)一个程序中假如要用到两个栈时，可通过两个栈共享一维数组来实现。即双向栈共享邻接空间。假如一个程序中要用到两个队列，能否实现？如何实现？假设以带头结点的循环链表表达队列，并且只设一个指针指向队尾元素结点(注意:不设头指针),试编写相应的队列初始化、入队列和出队列算法。(9)设计算法实现括弧配对的检查。(10)设计算法求解迷宫的一条最短途径。(11)求解“背包问题”。“背包问题''的基本描述是：有一个背包，能盛放的物品总重量为S,设有N件物品，其重量分别为w1,w2,....wn,希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。{◎ElemTypex;if(p->top!=0){x=p->stack[p->top];return(x);°)elseo{oprintf("Undcrflow!\n");^return(O)；°))/*遍历顺序栈*/voidOutSlack(SqSlack*p){«inti;oprintf("\n")；aif(p->tOp<0)oprintf(“这是一个空栈!”)；prinlf("\n");for(i=p->top;i>=0;i-)叩rinif("第％d个数据元素是：%6d\nH,i,p—>stack[i])；)/*置空顺序栈*/voidsetEmpty(SqStack*p)(p->top=-1;/*主函数*/

main(){SqStack*q;iniy,cord;E1emTypea;ado(printf（"第一次使用必须初始化！\n"）;printf("\n”);printf("\n主菜单\n")；»printf("\n1初始化顺序板\n");Sprintf("\n插入一个元素\n");printf("\n删除栈顶元素\n");叩rintf("\n取栈顶元素\n");printf("\n置空顺序栈\n");printf("\n结束程序运营aoprintf(**\n----------\n");8Printf("请输入您的选择(1,2,3,4,5,6)”);scanf("%dcord)；叩rintf('*\n");3sw