03停车场管理与堆栈的应用

1、第3章 栈和队列栈的定义及其运算栈的顺序存储结构 栈的链式存储结构 栈的应用举例 队列的定义及运算 队列的顺序存储结构队列的链式存储结构栈和队列的应用实例13.1 栈(Stack)栈: 只允许在表的一端进行插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)进栈插入: 将一个数据元素存放在栈顶出栈删除：将栈顶元素取出并删除特点:后进先出(LIFO )2出栈anan-1a2a1栈底 bottom栈顶 top进栈栈(Stack)3栈的根本操作 InitStack(S) 初始化操作,建立一个空栈S StackEmpty(S) 判空栈操作,假设S为空栈,返回一个真值

2、Push(S，x) 进栈操作,在栈S顶插入一个元素XPop(S,*y) 出栈操作,假设栈S不空, 删除栈顶元素并保存在*y中。GetTop(S, *y) 取栈顶元素操作,假设栈S不空那么取栈顶元素保存在*y中4 栈的顺序存储结构(顺序栈)栈的存储结构描述typedef struct ElemType elemMAXSIZE; int top; /*栈顶指针*/ SqStack; 利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设一个栈顶指针top 指向栈顶元素在顺序栈中的位置5进栈例如 4 3 2 1top0空栈a 进栈b 进栈 4 3 2top 1 0a 4 3 top 2 1

3、b 0ae 进栈 4e 3 d 2c 1b 0af 进栈上溢 4e 3 d 2c 1b 0atoptop6出栈例如b出栈c出栈 4 3 2 top1b 0a 4 3 top 2c 1b 0ae 出栈 top4e 3 d 2c 1b 0a 4top 3 d 2c 1b 0ad 出栈a出栈，栈空 4 3 2 1 top0a7栈空 top=O 时栈满 top=MAXSIZE时进栈 先进一个元素，指针top加1出栈 先指针top减1，出一个元素，栈顶指针top 始终指向栈顶元素的下一个位置上溢 栈满时如还有元素要进栈,它可能使有用信息丧失，因此要尽量防止下溢 栈空时还要出栈,下溢常常用来作为控制转移的

4、条件或算法结束的标志有关说明8栈的主要算法 /* (1)初始化建立一个空栈S */void InitStack_Sq( SqStack *S) S-top=0; /* InitStack_Sq*/ /* 2判栈S是否为空 , 空那么返回1 */int Empty_Sq( SqStack *S) return ( S-top=0) ; /*Empty_Sq */9 /* (3)进栈操作，假设栈S未满，将元素x进栈 */int Push_Sq(SqStack *S, ElemType x) if( S-top=MAXSIZE ) return 0; /* 栈满 */ S-elemS-top=x;

5、S-top+; return 1; /*Push_Sq */ /*(4)出栈操作,假设栈S非空,删除栈顶元素并保存在*y中*/ int Pop_Sq(SqStack *S , ElemType *y) if(S-top=0) return 0; /* 栈空 */ -S-top; *y=S-elemS-top; return 1; /*Pop_Sq */10思考：设计GetTop算法int GetTop _Sq(SqStack *S , ElemType *y) if(S-top=0) return 0; /* 栈空 */ *y=S-elemS-top; return 1; /* GetTop

6、_ Sq */113.1.3 栈的链式存储结构(链栈)链栈采用带表头结点的单链表结构，将尾结点定为栈底，首元结点定为栈顶链栈由它的栈顶指针top唯一确定插入与删除仅在栈顶处执行链栈无栈满问题，空间可扩充适合于多栈操作栈顶栈底top BC Adata next 12说明 使用带表头结点的单链表，是因为这样在入栈和出栈操作时改变的都是指针top所指头结点的指针域的值，而不是指针top 的值链栈的存储结构描述typedef struct node ElemType data; Struct node *next; SNode; 13链栈的主要算法/*建立一个空链栈 */ SNode *InitSta

7、ck_L(void) top=new SNode; top-next=NULL; return top; /* InitStack_L*/ top14 /* 元素x进链栈 */ void Push_L(SNode *top , ElemType x) p=new SNode; p-data=x; p-next=top-next; top-next=p; /* Push_L*/x ptop 15 /* 假设链栈非空，栈顶元素出栈并保存在*y中*/int Pop_L(SNode *top , ElemType *y) if(top-next=NULL) return 0; /*链栈已空*/ p=t

8、op-next; *y=p-data; top-next=p-next; delete p; return 1;/* Pop_L*/ptop16多个链栈的操作 在程序中需要同时使用两个以上的栈时，可用多个链栈，操作极为方便。我们可将多个链栈的栈顶指针放在一个一维数组之中，即可设： SNode *topn； 让top0，top1，topn-1 指向n个不同的链栈。操作时只需确定栈号i ，然后以topi 栈顶指针进行栈操作。此时每个链栈不需带表头结点。17top0 topi topn-1栈顶多个链栈18算法如下： /* 元素x进第 i号链栈*/void Pushn(SNode *top ,int

9、i, ElemType x) pnew SNode； p-data=x; p-next=topi； topiP; 19/* 假设第i号链栈非空，栈顶元素出栈并保存在*y中*/int Popn(SNode *top,int i, ElemType *y) if(topi=NULL) return 0; /* 栈空 */ p=topi; topi=p-next; *y=p-data; free(p); return 1; 在上面的两个算法中，当指定栈号 i(0in-1)时，那么只对第 i 个链栈操作，不会影响其它链栈。20栈的应用举例 栈的应用非常广泛，在计算机程序设计很重要。比方，在编译和运行计

10、算机语言程序的过程中，就需要利用栈进行语法检查、计算表达式的值、函数的调用和实现递归等。下面讨论栈在这些方面的几个应用例子21检验表达式中的左右圆括号是否匹配 假设表达式存储在字符数组str 中，设置一个元素为字符类型的栈S ，用它来存储表达式中从左到右顺序扫描到的左括号,栈的最大深度不会超过表达式中左括号的个数。算法实现顺序扫描字符数组str 中的每一个字符凡遇到( ，那么令其进栈；假设遇到的是),那么栈顶元素应出栈,此时假设栈S 发生下溢,那么说明缺少与之匹配的(括号；当表达式处理完毕时, 栈S 应空，否那么说明缺少)。22/*算法3.1 检验str中的表达式的左右圆括号是否匹配*/int

11、 Pair(char *str )InitStack(S)；/*置S栈为空 */ for ( ; *str; str+ ) switch (*str) case ( : Push(S,*str);break; case ) : if(StackEmpty(S) return 0;/* 缺少相配的左括号 */ else Pop(S,y); break; if(StackEmpty(S) return 1; return 0; /* 缺少相配的右括号 */*Pair*/思考 1如采用对左右括号分别计数的方法，如何实现匹配算法，并与算法3.1比较;2当表达式中出现多种括号对,如( 和) 、和、和时，

12、如何用算法3.1的思路来实现?23#include #include #define MAXSIZE 20 typedef char ElemType ; typedef struct ElemType elemMAXSIZE; int top; SqStack; SqStack stack; void InitStack_Sq( SqStack *S) S-top=0; int Empty_Sq( SqStack S) return ( S.top=0) ; 24int Push_Sq(SqStack *S, ElemType x) if( S-top=MAXSIZE ) return 0;

13、 S-elemS-top=x; S-top+; return 1; int Pop_Sq(SqStack *S ) if(S-top=0) return 0; -S-top; return 1; 25int Pair(char *str ) InitStack(&stack)； for ( ; *str; str+ ) switch (*str) case ( : Push(&stack,*str);break; case ) : if(StackEmpty(stack) return 0; else Pop(&stack); break; if(StackEmpty(stack) retur

14、n 1; return 0; 26main() char exp1 =(a+b)*(c-d)/n-x/y); char exp2 =(a+b)*(c-d)/n-x/y); int tag; /clrscr(); tag=Pair(exp1); if(tag=1) printf(%s is Pair!n,exp1); else printf(%s is not Pair!n,exp1); tag=Pair(exp2); if(tag=1) printf(%s is Pair!n,exp2); else printf(%s is not Pair!n,exp2); getch();27 表达式求值

15、是程序设计语言编译中的一个根本问题。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。 任何一个表达式都是由操作数(operand)、和算符(operator)组成的。操作数可以是常量或变量；算符包括运算符+,-,*,/和界限符(,),#)，它们构成的集合命名为OP。在算符集合中的特殊符号#，作为表达式的起始符和结束符，构成整个表达式的一对括号。 算术表达式的求值28表达式的算符是有优先级的，其规那么是： 先乘除，后加减； 同一个优先级，先左后右； 先括号内，后括号外。 根据上述三条运算规那么，在运算的每一步中，任意两个相继出现的算符1和2之间的优

16、先关系至多是下面三种关系之一： 12，1的优先级低于2； 12，1的优先级等于2， 12，1的优先级高于2。29表3-1-1 算符间的优先关系 + - * / ( ) # + - * / ( # = 2 1 30设两个工作栈OPTR栈：用以存放运算符OPND栈：用以存放操作数或运算结果首先置操作数栈为空，表达式起始符#为运算符栈的栈底元素；依次读入表达式中每一个字符，假设是操作数那么进OPND栈，假设是运算符(设为2)，那么和OPTR的栈顶算符(设为1)按表3-1-1比较优先权,再进行下面相应的操作: 假设12，2进栈 假设12，1出栈 假设12，1出栈参加运算直至整个表达式求值完毕( OPT

17、R栈的栈顶元素和当前读入的字符均为#)算法的根本思想31算法3.2 描述了求解算术表达式过程算法中还调用了三个函数:函数Inc,OP:判定字符c是否属于运算符集OP；函数Precede1，2:判定运算符栈的栈顶算符1与读入的算符2之间优先关系；函数Operatea，b:进行二元运算a b例3-1 利用算法Eval_Exp对算术表达式2*(7-4)+3求值，操作过程如表3-1-2所示32OperandType Eval_Exp( void) InitStack(OPTR);Push(OPTR,#); InitStack(OPND)；c=getchar()； while (c!=#| GetTop

18、(OPTR)!=#) if(!In(c,OP) /* c是一个运算数 */ Push(OPND,c); cgetchar()； else /* c是一个算符*/ r=Precede(GetTop(OPTR),c);/*比较两个算符的优先权 */ switch( r) case ： Pop(OPTR,op)； Pop(OPND,b)；Pop(OPND,a)； value=Operate(a,op,b)； Push(OPND,value); break； /* 退栈并将运算结果入栈 */ /* switch */ /*else*/ /*while */ return(GetToP(OPND)；33

19、步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # 2*(7-4)+3# PUSH(OPND,2) 2 # 2 *(7-4)+3# PUSH(OPTR,*) 3 # * 2 (7-4)+3# PUSH(OPTR,() 4 # *( 2 7-4)+3# PUSH(OPND,7) 5 # *( 2 7 -4)+3# PUSH(OPTR,-) 6 # *( - 2 7 4)+3# PUSH(OPND,4) 7 # *( - 2 7 4 )+3# Operate(7,-,4) 8 # *( 2 3 )+3# POP(OPTR) 9 # * 2 3 +3# PUSH(OPTR,+)10 # 6 +

20、3# Operate(2,*,3) 11 # + 6 3# PUSH(OPND,3)12 # + 6 3 # OPERATR(6,+,3)13 # 9# RETURN(GETTOP(OPND)34设栈st和队列q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈st，一个元素出栈后即进入队列q。假设出队顺序为e2、e4、e3、e6、e5、e1，那么栈st的容量至少应该为多少？35一个直接或间接地调用自身的函数称为递归函数递归是程序设计中一个非常重要的方法优点是逻辑性强，结构清晰，且算法的正确性易于证明递归设计先要确定求解问题的递归模型，了解递归的执行过程，在此根底上进行递归程序设

21、计，同时还要掌握从递归算法到非递归算法的转换过程栈与递归36 递归模型反映一个递归问题的递归结构，例如， n！的递归模型为: f1=1 假设 n=1 /*递归出口*/ fn=n*fn-1 假设 n1 /*递归体*/ 一般地，一个递归模型是由递归出口和递归体两局部组成，前者确定递归到何时为止，后者确定递归的方式。求 n！的递归函数如下：37main() fact(4); 第1层fact n=4 p=4*fact(3); 第2层fact n=3 p=3*fact(2); 第1层fact n=1 p=1; 返回1 返回2 返回6 返回24 递归调用示意 第3层fact n=2 p=2*fact(1)

22、; long fact (int n) if(n=1) p=1; else p=n*fact(n-1); return p; /*fact*/38计算机在执行递归算法时，是通过栈来实现的。在一层层递归调用时，系统自动将其返回地址和处在每一调用层的变量数据一一记下进栈。返回时，它们一一出栈并且被采用。从执行语句fact(4);所展示的递归调用的情况，可以看到fact函数共被调用4次，即fact(4)、fact(3)、fact(2)、fact(1)。其中fact(4) 是在main函数中调用的，其余3次是在fact 函数中调用的。在某一层递归调用时，并末立即得到结果，而是进一步向深度递归调用，直到

23、最内层函数执行n=1 时，fact(n) 才有结果。然后在一一返回时，不断得到中间结果，直到回到主程序就可得到 n !的最终结果。39 实际上，递归是把一个不能或不好直接求解的“大问题转化成一个或几个“小问题来解决，再把这些“小问题进一步分解成更小的“小问题来解决，如此分解，直至每个“小问题都可以直接解决此时分解到递归出口。当然，被分解的“小问题和“大问题必须具有相同的特征属性。下面介绍的Hanoi 塔问题将有助于对递归更进一步的理解40 x y z例3-2 n阶Hanoi 塔问题 假设有3个分别命名为x、y 和z 的塔座，在塔座x上插有n 个直径大小各不相同、从小到大编号为l，2，n 的圆盘

24、，如图3-1-5所示。现要求将x 座上的n 个圆盘移至z座上并仍按同样顺序叠排，圆盘移动时必须遵循以下规那么：(1)每次只能移动一个圆盘；(2)圆盘可以插在 x、y 和 z 中的任一塔座上；(3)任何时刻都不能将一个较大的圆盘压在较小圆盘之上。41如何实现移动圆盘的操作呢?当n=1 时，问题比较简单，将编号为1 的圆盘从塔座x直接移至塔座 z 上；当n1 时，利用塔座z 作辅助塔座，设法将压在编号为n 的圆盘之上的n-1 个圆盘从塔座x (依照上述法那么)移至塔座y 上，那么可将编号为n 的圆盘从塔座x 移至塔座z上;再将塔座y 上的n-1 个圆盘(依照上述法那么)移至塔座z上将n-1 个圆盘

25、从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模变小，因此可以用同样的方法求解。算法3.3所示求解n 阶Hanoi塔问题的递归函数42 /*算法3.3 将塔座x上按直径由小到大且自上而下编号为l至n的n个圆盘按规那么移到塔座z上，y可以用作辅助塔座函数move(x,n,z)实现把编号为n的圆盘从x座移到z座的操作*/void Hanoi(int n，char x，char y，char z) if(n=1) move(x,1,z)；/* 编号为l的圆盘从x移到z */ else /*将x上编号为1到n-1的圆盘移到y上，z作辅助塔座*/ Hanoi(n-l,x

26、,z,y)； /*将编号为n的圆盘从x移到z 上 */ move(x,n,z)； /*将y上编号为l至n-l的圆盘移到z上，x作辅助塔座*/ Hanoi(n-l,y,x,z)； /* Hanoi */43 下面用语句：Hanoi(3,a,b,c)；来展示递归执行的过程Hanoi(3,a,b,c)；Hanoi(2,a,c,b)；move(a,3,c)； /*3号盘从a移到c*/Hanoi(2,b,a,c)；Hanoi(1,a,b,c)；/*1号盘从a移到c*/move(a,2,b)；/*2号盘从a移到b*/Hanoi(1,c,a,b)；/*1号盘从c移到b*/Hanoi(1,b,c,a)；/*1

27、号盘从b移到a*/move(b,2,c)； /*2号盘从b移到c*/Hanoi(1,a,b,c)；/*1号盘从a移到c*/441 32 a b c 初始状态移动后的状态 32 a b c 1移动后的状态 32 a b c 1移动后的状态 3 a b c 12移动后的状态 3 a b c 12移动后的状态 3 a b c 12移动后的状态 3 a b c 12移动后的状态 3 a b c 12 3阶Hanoi塔 递归过程图示45 虽然递归算法简明精练，但运行效率较低，时空开销较大，并且某些高级语言(如FORTRAN语言)没有提供递归调用的语句及功能。因此，在实际应用中往往会使用非递归方法。为了提

28、高程序设计的能力，有必要进行由递归方法到非递归方法的根本训练。通过前面对递归算法执行的分析，我们已经知道，系统内部是借助于栈来实现递归的。因此，在设计相应的非递归算法时也需要人为地设置一个栈来实现。具体如何实现将在后面的有关章节中详细介绍。46 32 队列(Queue)队列：只允许在表的一端进行插入，在另一端进行删除的，操作受限制的线性表允许插入的一端称之为队尾(rear)允许删除的一端称之为队头(front)入队插入: 将一个数据元素存放在队尾出队删除：将队头元素取出并删除特点:先进先出(LIFO )47a1 a2 a3 a n队头队尾出队入队队列示意 在日常生活中，队列的例子到处皆是，如等

29、待购物的顾客总是按先来后到的次序排成队，先得到效劳的顾客是站在队头的先来者，而后到的人总是排在队的末尾。 在程序设计中，一个典型的例子就是操作系统中的作业排队。48队列的根本操作InitQueue(Q) 初始化一个空队列QEnQueue(Q，x) 在队列Q的尾部插入一个新的元素XDelQueue(Q，*y) 删除队列Q的队头的元素，并存人*y中QueueEmpty(Q) 判队列Q是否为空,假设为空返回一个真值，否那么返回一个假值GetFront(Q，*y) 取得队列Q的队头元素49队列的顺序存储结构顺序存储结构定义typedef struct ElemType elemMAXSIZE; int

30、 front,rear; /*队头、队尾指针*/ SqQueue;50空队列q1 入队543 210rear front543 210q1rear front543 21q20q1rear frontq2 入队初始置空队列:头、尾指针均置为0，即 front=rear=0入队操作:先在尾指针rear位置插入一个 元素，然后尾指针增1注意:尾指针始终指向队尾元素的下一个位置入队示意51543 21q20q1rear frontq1 出队543 21q20q1rear frontq2 出队,队空543 21q20q1rear front出队操作:先在头指针front 位置取出一个 元素，然后头指针

31、增1注意:头指针始终指向队头元素的当前位置队空条件:头指针rear =尾指针 front出队示意52q3入队543 2q31q20q1rear frontq6入队,队满？5q64q53 q42q31q20q1rear front假溢出 队列的实际可用空间并没有占满，但队尾却无法插入元素队满如何判断53循环队列(Circular Queue)解决假溢出的方法是把顺序队列所使用的存储空间构造成一个逻辑上的环状空间，即把elem0 接在elemMAXSIZE-1 之后。发生假溢出时，将新元素插入到第一个位置上，这样虽然物理上队尾在队头之前，但逻辑上队头仍然在前，入队和出队仍按“先进先出的原那么进行5

32、34120Sq.frontSq.rearq3q4循环队列sq54534120Sq.frontSq.rearq3q4 此时假设q5要入队, 队尾指针Sq.rear再进一个位置就应自动到0,这可以利用对MAXSIZE取模%运算来实现,即： Sq.rear = (Sq.rear+1)% MAXSIZE534120Sq.frontSq.rearq3q4q5 同理,出队时对队头指针Sq.front的修改也是： Sq.front = (Sq.front+1% MAXSIZE入队和出队时队头尾指针的修改55队空条件讨论假设q3、q4和q5相继出队列534120Sq.frontSq.rearq3q4q5534

33、120Sq.frontSq.rearq3q4q5此时队列已空，得到队空条件为: Sq.front = Sq.rear56假设q6、q7和q8相继入队列此时队列已满，得到队满条件为: Sq.rear = Sq.front 与队空条件相同，任何区分？534120Sq.frontSq.rearq3q4q5Sq.rearSq.front534120q3q4q5q7q8q6队满条件讨论57课堂思考：如何判断顺序循环队列是空还是满？ 结论：当循环队列满时有front=rear ，而当循环队列空时也有front=rear。rear0 1 2 34 5 6 7BACfrontrear0 1 2 34 5 6

34、7BACfrontrear0 1 2 34 5 6 7front队列中有五个元素A、B、C、D、EDEDEXYZ又有三个元素X、Y、Z入队后队列满所有元素出队后队列空58另设一个标志位以区别队列是空还是满；约定 队空条件: Sq.front = Sq.rear 队满条件:队尾指针加1等于队头指针,即 (Sq.rear+1 ) %MAXSIZE= Sq.front即一个大小为MAXSIZE的循环队列最多有MAXSIZE-1个元素Sq.rearSq.front534120q3q4q5q7q6处理的方法59循环队列的主要算法实现 /*将循环队列Sq初始化置为空循环队列 */ void InitQue

35、ue(SqQueue *Sq) Sq-front=Sq-rear=0; /* InitQueue*/ 60/* 在循环队列Sq的尾部入队一个新元素x */ int EnQueue(SqQueue *Sq，ElemType x) if(Sq-rear+1) % MAXSIZE = Sq-front) return 0; /*队列已满*/ Sq-elemSq-rear=x; Sq-rear=(Sq-rear+1) % MAXSIZE; return 1; /* EnQueue*/61/*循环队列Sq出队一个元素，并存人*y中*/int DelQueue(SqQueue *Sq，ElemType *

36、y) if(Sq-front=Sq-rear) return 0; /*队列已空*/ *y=Sq-elemSq-front; Sq-front=(Sq-front+1) % MAXSIZE ; return 1; /* DelQueue*/62 队列的链式存储结构链式队列用带表头结点单链表表示，简称链队列一个链队列用两个指针分别指示队头和队尾，队头指针front在链表链头，队尾指针rear在链表链尾链队列在入队时无队满问题，但有队空问题 队空条件为:front = rear队头队尾 rear frontdata next 63链队列存储结构的定义typedef struct node /*结点

37、结构*/ ElemType data; struct node *next; QNode;typedef struct QNode *front; /*队头指针*/ QNone *rear; /*队尾指针*/ LQueue;64链队列主要算法实现/* 初始化链队列Lq，生成链队列的表头结点，并令头指针和尾指针指向该结点*/void InitQueue_L(LQueue *Lq) p=( QNone *)malloc(sizeof(QNone); p-next=NULL； Lq-front=Lq-rear=p; /* InitQueue_L*/pLq-frontLq-rear65入队图示Lq-f

38、rontLq-rearab入队前pxLq-frontLq-rearab入队后66/* 在链队列Lq的尾部插入一个新的元素x */ void EnQueue_L(LQueue *Lq，ElemType x) p=(QNone *)malloc(sizeof(QNone); p-data=x; p-next=NULL ; Lq-rear-next=p；Lq-rear=p; /* EnQueue_L*/算法67cLq-frontLq-rearab出队前pcLq-frontLq-rearab出队后出队图示68算法 /*删除队列Lq的队头元素，并存入*y中*/ int DelQueue-L(LQueue

39、 *Lq，ElemType *y) if(Lq-front=Lq-rear) return 0; /*队列已空*/ p=Lq-front-next; /*p指向队头结点*/ *y=p-data; Lq-front-next=p-next; if (Lq-rear=p ) Lq-rearLq-front；/*尾指针指向头结点*/ free(p); return 1; /* DelQueue-L*/注意 防止队尾指针丧失6933 栈和队列的应用实例停车场管理 设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后次序从停车场最里面向门口处停放(最先到达的第一

40、辆车停在停车场的最里面)。如果停车场已放满n辆车，那么后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走,那么排在便道上的第一辆车就可进入停车场。停车场内如有某辆车要开走,在它之后进入停车场的车辆都必须先退出停车场为它让路,待其开出停车扬后,这些车辆再依原来的次序进入。每辆车在离开停车场时,根据它在停车场内停留时间的长短交费。如果停在便道上的车辆未进停车场就要离去，允许其离去时不收停车费,并且仍然保持在便道上等待的车辆的次序。 现在编制一个程序来模拟停车场的管理。70 首先确定模拟程序中需要的数据结构及其操作。 由于停车场只有一个大门,因此可用一个栈来模拟;根据便道停车的特点，先排

41、队的车辆先离开便道进入停车场,可以用一个队列来模拟；又因为排在停车场中间的车辆可以提前离开，因此还需要有一个地方(车辆躲避所)保存为了让路离开停车场的车辆,很显然这也应该用一个栈来模拟。所以在程序中设置了两个顺序栈s1和s2分别表示停车场和躲避所;设置了一个链队列q表示便道。它们的数据类型定义在下面的源程序中，为了操作方便，链队列表头结点中的num域中存放便道上的车辆数量。71 程序执行时，当输入数据表示有车辆到达时，判断栈s1是否满，假设未满就将新数据进栈s1；假设栈已满,就将数据入队列q，表示车辆在便道上等待进入停车场。该操作过程由函数Arrive完成。 当输入数据表示有车辆要离去时,就在

42、栈s1中寻找此车牌号的车辆,如寻找到就让其离开停车场,并根据停车时间计费，同时将队列q的队头元素进栈s1；如没有找到,就到队列q中去寻找此车牌号的车辆。如在队列q中找到就允许其离开队列,并不收费；如找不到就显示出错信息。 当离开停车场的车辆位于栈s1的中间时,必须先将此位置到栈顶之间的所有数据倒到栈s2中去,然后安排车辆出栈s1,最后将栈s2中的数据倒回到栈s1中来。该操作过程由函数Delive完成。显然，以上两个主要操作需要利用栈和队列的两个根本操作入栈队列和出栈队列来实现。 源程序中的函数Display那么可以随时显示停车场的状况。72 下面是模拟停车场管理的源程序。其模拟过程中栈和队列的

43、变化过程可以见本书附带的光盘。#include stdio.h#define N 2 /*停车场容量*/#define M 5 /*停车单价*/#define True 1#define False 0typedef struct int num; /*车牌号*/ int arrtime; /*到达/离开时间*/ ElemType; /*顺序栈的数据元素类型*/typedef struct ElemType elemN; int top; SqStack; /*顺序栈类型*/73typedef struct node int num; /*车牌号/便道上的车辆数量*/ struct node

44、*next; QNode; /*链队列的数据元素类型*/typedef struct QNode *front, *rear; LQueue; /*链队列类型*/74/*函数声明*/void InitStack_Sq (SqStack *s); /*初始化栈*/int Push_Sq(SqStack *s,ElemType x); /*入栈*/ElemType Pop_Sq(SqStack *s); /*出栈*/void InitQueue_L(LQueue *q); /*初始化队列*/void EnQueue_L (L LQueue *q,int num1); /*入队列*/int DelQ

45、ueue_L(LQueue *q); /*出队列*/*以上函数定义在本书附带的光盘中*/75/*车辆x进入停车场*/void Arrive (SqStack *s1, LQueue *q,ElemType x) int f; f=Push_Sq(s1,x); if (f=False) /*停车场栈s1已满入便道q */ EnQueue_L(q,x.num); printf(第%d号车停在便道第%d车位上n, x.num,q-front-num); else printf(第%d号车停在停车场第%d车位上n, x.num,s1-top); /* Arrive */76void Delive (S

46、qStack *s1,SqStack *s2, LQueue *q,ElemType x) /*车辆x离开停车场*/ int n,f=False; ElemType y; QNode *p; while (s1-top0) & (f!=True) /*在栈s1中寻找车辆x */ y=Pop_Sq(s1); if (y.num!=x.num) n=Push_Sq(s2,y); else f=True; if (y.num=x.num) /*寻找到车辆x*/ printf(第%d号车应收费%d元n, )*M); while (s2-top0) /*将栈s2中的车辆倒回到栈s1中*/ y=Pop_Sq(s2); f=Push_