数据结构-栈和队列课件教学课件

1、 栈是一种特殊的线性表，它只能在表的一端（栈顶）栈是一种特殊的线性表，它只能在表的一端（栈顶） 进行插入和删除运算进行插入和删除运算 栈与一般线性表的区别：仅在于栈与一般线性表的区别：仅在于运算规则运算规则不同不同 一般线性表一般线性表 逻辑结构：一对一逻辑结构：一对一 存储结构：顺序表、链表存储结构：顺序表、链表 运算规则：随机运算规则：随机、顺序存取顺序存取 栈栈 逻辑结构：一对一逻辑结构：一对一 存储结构：顺序存储结构：顺序栈栈、链、链栈栈 运算规则：运算规则：后进先出后进先出 栈与一般线性表的区别栈与一般线性表的区别 “进进” 压入压入=PUSH=PUSH（) ) “出出” 弹出弹出=

2、POP( )=POP( ) a a1 1 a a2 2 a an n 顺序栈顺序栈S S a ai i 表头表头 表尾表尾 栈底栈底basebase 栈顶栈顶toptop 低地址低地址 高地址高地址 写入：写入：vi= vi= a ai i 读出：读出：x= vix= vi 压入：压入：PUSH (PUSH (a an+1n+1) ) 弹出：弹出：POP (x)POP (x) 前提：一定要预设栈顶指针前提：一定要预设栈顶指针toptop！ 低地址低地址 高地址高地址 vivi a a1 1 a a2 2 a ai i a an n 顺序表顺序表VnVn a an+1n+1 顺序栈与顺序表顺序栈

3、与顺序表 顺序栈的表示顺序栈的表示 空栈空栈 base = topbase = top 是栈空标志是栈空标志 stacksize = 4stacksize = 4 top A basebase top A B A B C top base top base A B C D base top 3 1 2 0 top top 指示真正的指示真正的栈顶元素之上栈顶元素之上的下标地址的下标地址 栈满时的处理方法：栈满时的处理方法： 1 1、报错报错, ,返回操作系统。返回操作系统。 2 2、分配更大的空间分配更大的空间，作为栈的存储空，作为栈的存储空 间间, ,将原栈的内容移入新栈。将原栈的内容移入新

4、栈。 #define MAXSIZE 100 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 顺序栈的表示顺序栈的表示 构造一个空栈构造一个空栈 步骤：步骤： (1)(1)分配空间并检查空间分配空间并检查空间 是否分配失败，若失是否分配失败，若失 败则返回错误败则返回错误 顺序栈初始化顺序栈初始化 base stacksize top s (2)(2)设置栈底和栈顶指针设置栈底和栈顶指针 S.top = S.base; (3)(3)设置栈大小设置栈大小 Status InitStack( SqSta

5、ck S.top = S.base; S.stackSize = MAXSIZE; return OK; 顺序栈初始化顺序栈初始化 判断顺序栈是否为空判断顺序栈是否为空 bool StackEmpty( SqStack S ) if(S.top = S.base) return true; else return false; base top 3 1 2 0 求顺序栈的长度求顺序栈的长度 int StackLength( SqStack S ) return S.top S.base; base top A B Status ClearStack( SqStack S ) if( S.bas

6、e ) S.top = S.base; return OK; 清空顺序栈清空顺序栈 base top 3 1 2 0 Status DestroyStack( SqStack S.stacksize = 0; S.base = S.top = NULL; return OK; 销毁顺序栈销毁顺序栈 (1)(1)判断是否栈满，若满则出错判断是否栈满，若满则出错 (2)(2)元素元素e e压入栈顶压入栈顶 (3)(3)栈顶指针加栈顶指针加1 1 顺序栈进栈顺序栈进栈 Status Push( SqStack *S.top+=e; return OK; *S.top=e; S.top+; A B C

7、 top base (1)(1)判断是否栈空，若空则出错判断是否栈空，若空则出错 (2)(2)获取栈顶元素获取栈顶元素e e (3)(3)栈顶指针减栈顶指针减1 1 顺序栈出栈顺序栈出栈 Status Pop( SqStack e *-S.top; return OK; -S.top; e=*S.top; A B C top base 判断是否空栈，若空则返回错误判断是否空栈，若空则返回错误 否则通过栈顶指针获取栈顶元素否则通过栈顶指针获取栈顶元素 取顺序栈栈顶元素取顺序栈栈顶元素 Status GetTop( SqStack S, SElemType / 栈空栈空 e = *( S.top

8、1 ); return OK; e = *( S.top - ); ? A B C top base 435612435612中到了中到了1212顺序不能实现；顺序不能实现； 135426135426可以实现。可以实现。 1.1.如果一个栈的输入序列为如果一个栈的输入序列为123456123456，能否得到，能否得到 435612435612和和135426135426的出栈序列？的出栈序列？ 练习练习 练习练习 i n-i n-i+1 不确定不确定 2.2.若已知一个栈的入栈序列是若已知一个栈的入栈序列是1 1，2 2，3 3，n n，其，其 输出序列为输出序列为p1p1，p2p2，p3p3

9、，pnpn，若，若p1=np1=n，则，则pipi为为 练习练习 top不变不变 top=0 top+ top- D 3.3.在一个具有在一个具有n n个单元的顺序栈中，假设以地址高端作个单元的顺序栈中，假设以地址高端作 为栈底，以为栈底，以toptop作为栈顶指针，则当作进栈处理时，作为栈顶指针，则当作进栈处理时， toptop的变化为的变化为 b0 t0 t1 b1 0 m-1 V 双栈共享一个栈空间双栈共享一个栈空间 优点：互相调剂，灵活性强，减少溢出机会优点：互相调剂，灵活性强，减少溢出机会 将编号为将编号为0 0和和1 1的两个栈存放于一个数组空间的两个栈存放于一个数组空间VmVm

10、中，栈底分别处于数组的两端。当第中，栈底分别处于数组的两端。当第0 0号栈的栈顶号栈的栈顶 指针指针top0top0等于等于-1-1时该栈为空，当第时该栈为空，当第1 1号栈的栈顶号栈的栈顶 指针指针top1top1等于等于m m时该栈为空。两个栈均从两端向时该栈为空。两个栈均从两端向 中间增长（如下图所示）中间增长（如下图所示） 。 bot0 top0 top1 bot1 0 m-1 V typedef struct int top2, bot2; /栈顶和栈底指针栈顶和栈底指针 SElemType SElemType * *V; V; /栈数组栈数组 int m; int m; /栈最大可

11、容纳元素个数栈最大可容纳元素个数 DblStack;DblStack; 数据结构定义如下数据结构定义如下 void Dblpush(DblStack struct StackNode *next; StackNode, *LinkStack; LinkStack S; data next 栈顶栈顶 栈底栈底 S 链栈的初始化链栈的初始化 void InitStack(LinkStack S 判断链栈是否为空判断链栈是否为空 Status StackEmpty(LinkStack S) if (S=NULL) return TRUE; else return FALSE; 链栈进栈链栈进栈 St

12、atus Push(LinkStack /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 链栈出栈链栈出栈 Status Pop (LinkStack e = S- data; p = S; S = S- next; delete p; return OK; 取链栈栈顶元素取链栈栈顶元素 SElemType GetTop(LinkStack S) if (S=NULL) exit(1)； else return Sdata; 3.2 3.2 栈的应用栈的应用 例例1 1：数制转换（十转：数制转换（十

13、转N N） 用栈暂存低位值用栈暂存低位值 例例2 2：括号匹配的检验括号匹配的检验 用栈暂存左括号用栈暂存左括号 例例3 3：表达式求值表达式求值 用栈暂存运算符用栈暂存运算符 例例4 4：迷宫求解：迷宫求解 用栈实现递归调用用栈实现递归调用 简化了程序设计的问题简化了程序设计的问题 迷宫求解迷宫求解 从入口出发，按某一方向向未走过的前方探索从入口出发，按某一方向向未走过的前方探索 若能走通，则到达新点，否则试探下一方向若能走通，则到达新点，否则试探下一方向 ; ; 若所有的方向均没有通路，则沿原路返回前一点，若所有的方向均没有通路，则沿原路返回前一点， 换下一个方向再继续试探换下一个方向再继

14、续试探 直到所有可能的通路都探索到，或找到一条通路，直到所有可能的通路都探索到，或找到一条通路， 或无路可走又返回到入口点。或无路可走又返回到入口点。 求解思想：求解思想：回溯法回溯法 迷宫求解迷宫求解 需要解决的问题：需要解决的问题： 1、表示迷宫的数据结构、表示迷宫的数据结构 2、试探方向、试探方向 3、栈的设计、栈的设计 4、防止重复到达某点，避免发生死循环、防止重复到达某点，避免发生死循环 迷宫求解迷宫求解 1、表示迷宫的数据结构、表示迷宫的数据结构 表示一个表示一个m行行n列迷宫：列迷宫： 用用mazemn表示，表示，0im,0j x = x x 表表3.13.1算符间的优先关系算符

15、间的优先关系 【算法思想算法思想】 （1）初始化）初始化OPTR栈和栈和OPND栈，将栈，将 “#”压入压入OPTR （2）依次读入字符）依次读入字符ch，循环执行（，循环执行（3）至（）至（5） （3）取出）取出OPTR的栈顶元素，当的栈顶元素，当OPTR的栈顶元素和的栈顶元素和ch均为均为 “#”时，表达式求值完毕，时，表达式求值完毕，OPND栈顶元素为表达式的值栈顶元素为表达式的值 设定两栈设定两栈 ：OPND-OPND-操作数或运算结果操作数或运算结果OPTR-OPTR-运算符运算符 （4） if (ch是操作数是操作数) 则则ch进进OPND，读入下一字符，读入下一字符ch （5）

16、else 比较比较OPTR栈顶元素和栈顶元素和ch的优先级的优先级 case : 运算符运算符ch 进进OPTR，读入下一字符，读入下一字符ch case=: 脱括号（弹出左括号），读入下一字符脱括号（弹出左括号），读入下一字符ch case : 栈顶运算符退栈、计算，结果进栈顶运算符退栈、计算，结果进OPND OperandType EvaluateExpression( ) InitStack (OPND); ch = getchar( ); while (ch!= # | GetTop(OPTR)! = #) if (! In(ch,OP)Push(OPND,ch); ch = getc

17、har(); / ch不是运算符则进栈不是运算符则进栈 else switch (Precede(GetTop(OPTR),ch) /比较优先权比较优先权 case : /弹出弹出OPTR栈顶的运算符运算，并将运算结果入栈栈顶的运算符运算，并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; case = : /脱括号并接收下一字符脱括号并接收下一字符 Pop(OPTR,x); ch = getchar(); break; / switch / while r

18、eturn GetTop(OPND); / EvaluateExpression OPTROPNDINPUTOPERATE 3*(7-2)#Push(opnd,3) # *(7-2)#3#Push(optr,*) #,*3(7-2)#Push(optr,() #,*,(37-2)#Push(opnd,7) #,*,(3,7-2)#Push(optr,-) #,*,(,3,72)#Push(opnd,2) #,*,(,3,7,2)#Operate(7-2) #,*,(3,5)#Pop(optr) #,*3,5#Operate(3*5) #15#GetTop(opnd) 3.3 3.3 栈与递归栈

19、与递归 n递归的定义递归的定义 若一个对象部分地包含它若一个对象部分地包含它 自己自己, , 或用它自己给自己定义或用它自己给自己定义, , 则称这个对则称这个对 象是递归的；若一个过程象是递归的；若一个过程直接地或间接地调用直接地或间接地调用 自己自己, , 则称这个过程是递归的过程。则称这个过程是递归的过程。 当多个函数构成嵌套调用时当多个函数构成嵌套调用时, , 遵循遵循 后调用先返回后调用先返回 栈栈 n以下三种情况常常用到递归方法以下三种情况常常用到递归方法 递归定义的数学函数递归定义的数学函数 具有递归特性的数据结构具有递归特性的数据结构 可递归求解的问题可递归求解的问题 1. 递

20、归定义的数学函数递归定义的数学函数: 阶乘函数阶乘函数: 0n ) 1( 0n 1 )( 若 若 nFactn nFact 2阶阶Fibonaci数列数列: )2() 1( 1n 1 0n 0 )( 其它 若 若 nFibnFib nFib 树树 2. 2. 具有递归特性的数据结构具有递归特性的数据结构: : RootRoot LchildLchild RchildRchild 广义表广义表 A=(a,A)A=(a,A) 3. 3. 可递归求解的问题可递归求解的问题: : 迷宫问题迷宫问题HanoiHanoi塔问题塔问题 分治法：分治法：对于一个较为复杂的问题，能够分解成几对于一个较为复杂的问

21、题，能够分解成几 个相对简单的且解法相同或类似的子问题来求解个相对简单的且解法相同或类似的子问题来求解 1 1、能将一个问题转变成一个新问题，而新问题与、能将一个问题转变成一个新问题，而新问题与 原问题的解法相同或类同，不同的仅是处理的对象，原问题的解法相同或类同，不同的仅是处理的对象， 且这些处理对象是变化有规律的且这些处理对象是变化有规律的 2 2、可以通过上述转化而使问题简化、可以通过上述转化而使问题简化 3 3、必须有一个明确的递归出口，或称递归的边界、必须有一个明确的递归出口，或称递归的边界 用分治法求解递归问题用分治法求解递归问题 必备的三个条件必备的三个条件 分治法求解递归问题算

22、法的一般形式：分治法求解递归问题算法的一般形式： void p (参数表参数表) if （递归结束条件）可直接求解步骤；（递归结束条件）可直接求解步骤；-基本项基本项 else p（较小的参数）；（较小的参数）；-归纳项归纳项 long Fact ( long n ) if ( n = 0) return 1;/基本项基本项 else return n * Fact (n-1); /归纳项归纳项 返回返回 2参数参数 2 计算计算 2*Fact(1) 返回返回 1参数参数 1 计算计算 1*Fact(0) 返回返回 1参数参数 0 直接定值直接定值 = 1 if ( n = 0 ) retur

23、n 1; else return n * Fact (n-1); 求解阶乘求解阶乘 n! n! 的过程的过程 main : Fact(4) 返回返回 24 参数参数 4 计算计算 4*Fact(3) 返回返回 6参数参数 3 计算计算 3*Fact(2) 设有一个递归算法如下设有一个递归算法如下: int X(int n) if(n=3) return 1; else return X(n-2)+X(n-4)+1 则计算则计算X(X(8)时需要计算时需要计算X函数函数 次次.D 练习练习 A. 8 B.9 C.16 D.18 规则规则: : (1) (1) 每次只能移动一个圆盘每次只能移动一个

24、圆盘 (2) (2) 圆盘可以插在圆盘可以插在A,BA,B和和 C C中的任一塔座上中的任一塔座上 (3) (3) 任何时刻不可将较大任何时刻不可将较大 圆盘压在较小圆盘之上圆盘压在较小圆盘之上 Hanoi塔问题塔问题 ABC Hanoi塔问题塔问题 n = 1n = 1，则直接从，则直接从 A A 移到移到 C C。否则。否则 (1)用用 C 柱做过渡，将柱做过渡，将 A 的的(n-1)个移到个移到 B (2)将将 A 最后一个直接最后一个直接 移到移到 C (3)用用 A 做过渡，将做过渡，将 B 的的 (n-1) 个移到个移到 C #include int c=0; void move(

25、char x,int n,char z) cout+c,n,x,zc 调用前调用前, , 系统完成系统完成: : (1)(1)将将实参实参, ,返回地址返回地址等传递给被调用函数等传递给被调用函数 (2)(2)为被调用函数的为被调用函数的局部变量局部变量分配存储区分配存储区 (3)(3)将控制转移到被调用函数的将控制转移到被调用函数的入口入口 调用后调用后, , 系统完成系统完成: : (1)(1)保存被调用函数的计算保存被调用函数的计算结果结果 (2)(2)释放被调用函数的释放被调用函数的数据区数据区 (3)(3)依照被调用函数保存的依照被调用函数保存的返回地址返回地址将控制转移到将控制转移

26、到 调用函数调用函数 “层次层次” 主函数主函数 第第1 1次调用次调用 第第 i i 次调用次调用 0 0层层 1 1层层 i i 层层 “递归工作栈递归工作栈” “工作记录工作记录”实在参数实在参数, ,局部变量局部变量, ,返回地址返回地址 递归函数调用的实现递归函数调用的实现 空间效率空间效率 时间效率时间效率 O(2n) 与递归树的结点数成正比与递归树的结点数成正比 与递归树的深度成正比与递归树的深度成正比 O(n) 递归算法的效率分析递归算法的效率分析 1 2 3 4 f(1)=1 f(1)+1+f(1)=3 f(2)+1+f(2)=7 f(3)+1+f(3)=15 f(n) =

27、2f(n-1)+1 f(n-1) = 2f(n-2)+1 f(n-2) = 2f(n-3)+1 . f(3) = 2f(2)+1 f(2) = 2f(1)+1 20f(n) = 21f(n-1)+20 21f(n-1) = 22f(n-2)+21 22f(n-2) = 23f(n-3)+22 . 2n-3f(3) = 2n-2f(2)+ 2n-3 2n-2f(2) = 2n-1f(1)+ 2n-2 f(n) = 20+21+2n-2+ 2n-1f(1) = 2n-1 递归算法的效率分析递归算法的效率分析 6464片金片移动次数：片金片移动次数： 假如每秒钟一次，共需多长时间呢？假如每秒钟一次，

28、共需多长时间呢？ 一年大约有一年大约有31536926秒，移完这些金片需要秒，移完这些金片需要多亿年多亿年 世界、梵塔、庙宇和众生都已经灰飞烟灭世界、梵塔、庙宇和众生都已经灰飞烟灭 ! 优点：结构清晰，程序易读优点：结构清晰，程序易读 缺点：每次调用要生成工作记录，保存状缺点：每次调用要生成工作记录，保存状 态信息，入栈；返回时要出栈，恢复状态信息，入栈；返回时要出栈，恢复状 态信息。时间开销大。态信息。时间开销大。 递归的优缺点递归的优缺点 递归递归非递归非递归 3.4 3.4 队列队列 队列是一种先进先出队列是一种先进先出(FIFO) 的线性表的线性表. 它只允许在它只允许在 表的一端进行

29、插入表的一端进行插入,而在另一端删除元素而在另一端删除元素 ),( 21n aaaq a a1 1a a2 2a a3 3a an n . 入队列入队列 队头队头 队尾队尾 ),( 21n aaaq a a1 1a a2 2a a3 3a an n . 队头队头 队尾队尾 出队列出队列 ),( 21n aaaq a a1 1a a2 2a a3 3a an n . 队头队头 队尾队尾 出队列出队列 ),( 21n aaaq a a1 1a a2 2a a3 3a an n . 队头队头 队尾队尾 出队列出队列 设栈设栈S S和队列和队列Q Q的初始状态为空，元素的初始状态为空，元素e1e1、e

30、2e2、 e3e3、e4e4、e5e5和和e6e6依次通过依次通过S S，一个元素出栈后即，一个元素出栈后即 进入进入Q Q，若，若6 6个元素出队的序列是个元素出队的序列是e2e2、e4e4、e3e3、 e6e6、e5e5和和e1e1，则栈，则栈S S的容量至少应该是（）。的容量至少应该是（）。 （A）2 （B）3 （C）4 （D）6 练习练习 B 0n , 2 , 1,|niElemSetaaD ii 数据对象数据对象: 数据关系数据关系: 端为队列尾端为队列头约定 n1 111 a ,a , 2 , 1,| ,niDaaaaR iiii 基本操作基本操作: (1) InitQueue (

31、 /初始化的动态分配存储空间初始化的动态分配存储空间 int front; /头指针头指针 int rear; /尾指针尾指针 SqQueue; 队列的顺序表示用一维数组队列的顺序表示用一维数组baseM 队列的顺序表示用一维数组队列的顺序表示用一维数组baseM Q.frontQ.front0 0 1 1 2 2 3 3 4 4 5 5 Q.rearQ.rear Q.frontQ.front Q.rearQ.rear J J1 1 J J2 2 J J3 3 Q.frontQ.front Q.rearQ.rear J J3 3 Q.frontQ.front Q.rearQ.rear J J5

32、 5 J J6 6 front=rear=0空队标志：空队标志：front= =rear 入队：入队：baserear+=x; 出队：出队：x=basefront+; Q.frontQ.front Q.rearQ.rear J5J5 J6J6 Q.frontQ.front0 0 1 1 2 2 3 3 4 4 5 5 Q.rearQ.rear J5J5 J6J6 J1J1 J2J2 J3J3 J4J4 存在的问题存在的问题 设数组大小为设数组大小为M front=0 rear=M时时 再入队再入队真溢出真溢出 front 0 rear=M时时 再入队再入队假溢出假溢出 解决的方法循环队列解决的

33、方法循环队列 1 1 0 0 Q.rearQ.rear Q.frontQ.front . . base0接在接在baseM-1之之后后 若若rear+1=M 则令则令rear=0; 实现：利用实现：利用“模模”运算运算 入队：入队： baserear=x; rear=(rear+1)%M; 出队：出队： x=basefront; front=(front+1)%M; J4J4 J5J5 J6J6 0 0 1 1 2 2 3 3 4 4 5 5 rearrear frontfront J9J9 J8J8 J7J7 J7,J8,J9J7,J8,J9入队入队 队空：队空：front=rearfron

34、t=rear 队满：队满：front=rearfront=rear 解决方案：解决方案： 1.1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满 2 2. .少用一个元素空间少用一个元素空间： 队空：队空：front=rearfront=rear 队满：队满：( (rear+1)%M=frontrear+1)%M=front J4J4 J5J5 J6J6 0 0 1 1 2 2 3 3 4 4 5 5 rearrear frontfront 0 0 1 1 2 2 3 3 4 4 5 5 frontfront J4,J5,J6J4,J5,J6出队出队 rearrear 循环队列循

35、环队列 #define MAXQSIZE 100 /最大队列长度最大队列长度 Typedef struct QElemType *base; /初始化的动态分配存储空间初始化的动态分配存储空间 int front; /头指针头指针 int rear; /尾指针尾指针 SqQueue; Status InitQueue (SqQueue Q.front=Q.rear=0; return OK; 循环队列初始化循环队列初始化 求循环队列的长度求循环队列的长度 int QueueLength (SqQueue Q) return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;

36、 Status EnQueue(SqQueue Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; 循环队列入队循环队列入队 Status DeQueue (LinkQueue e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK; 循环队列出队循环队列出队 n aaa, 21 . . . . . . datadatanextnext 队头队头 队尾队尾 Q.frontQ.front Q.rearQ.rear 链队列链队列 typedef struct QNode QElemT

37、ype data; struct Qnode *next; Qnode, *QueuePtr; typedef struct QueuePtr front; /队队头指针头指针 QueuePtr rear; /队尾指针队尾指针 LinkQueue; 链队列链队列 Q.front Q.rear x Q.front Q.rear xy Q.front Q.rear xy (a) 空队列空队列 (b) 元素元素x入入队列队列 (d) 元素元素x出出队列队列 Q.front Q.rear (c) 元素元素y入入队列队列 链队列链队列 Status InitQueue (LinkQueue if(!Q.

38、front) exit(OVERFLOW); Q.front-next=NULL; return OK; 链队列初始化链队列初始化 Status DestroyQueue (LinkQueue free(Q.front); Q.front=Q.rear; return OK; 销毁链队列销毁链队列 Status QueueEmpty (LinkQueue Q) return (Q.front=Q.rear); 判断链队列是否为空判断链队列是否为空 Status GetHead (LinkQueue Q, QElemType e=Q.front-next-data; return OK; 求链队

39、列的队头元素求链队列的队头元素 Status EnQueue(LinkQueue if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; 链队列入队链队列入队 Q.front Q.rear xy p Status DeQueue (LinkQueue p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK; 链队列出队链队列出队 Q.front Q.rear xy p 【例例】汽车加油站汽车加油站 随着城市里汽车数量的急速增长，汽车加油站也渐随着城市里汽车数量的急速增长，汽车加油站也渐 渐多了起来。通常汽车加油站的结构基本上是：入渐多了起来。通常汽车加油站的结构基本上是：入 口和出口为单行道，加油车道可能有若干条。每辆口和出口为单行道，加油车道可能有若干条。每辆 车加油都要经过三段路程，第一段是在入口处排队车加油都要经过三段路程，第一段是在入口处排队 等候进入加油车道；第二段是在加油车道排队等候等候进入加油车道；第二段是在加油车道排队等候 加油；第三段是进入出口处排队等候离开。实际上加油；第三段是进入出口处排队等候离开。