2009-7-25 1
第四章 栈和队列栈和队列都是操作受限的线性表，应用十分广泛。
4.1 栈（ Stack）
定义：栈是限制插入和删除操作只能在某一端进行的线性表，并按先进后出（ F I L O )或后进先出（Ｌ IＦＯ）的原则进行操作入栈顺序：
e0 e1 e2 … en-2 en-1
出栈顺序：
en-1 en-2 … e2 e1 e0
栈可以对序列实现求逆
en-1
e0
e1
en-2
…
进栈（ Push） 出栈（ Pop）
栈顶 top
栈底
2009-7-25 2
栈的基本操作,（参见 P104）
（ 1）栈初始化 Stack ( int = 10 );//构造函数
（ 2）进栈 Push void Push( const Type & item );
（ 3）出栈 Pop Type Pop( );
（ 4）判栈空 IsEmpty int IsEmpty( ) { return top==-1;}
（ 5）读取栈顶元素 GetTop Type GetTop ( );
（ 6）置空栈 MakeEmpty void MakeEmpty( ) { top=-1;}
（ 7）判栈满 IsFull int IsFull( ) const { return top==maxSize;}
栈的封闭性及其抽象数据类型：
在一个栈中，出入口处称为栈顶，栈内最深处称为栈底。除了栈顶元素外，其他元素不会被改变，因而栈的封闭性非常好，
使用起来非常安全。另外，在下面的栈的类定义中，体现了栈的抽象数据类型，在此定义中，所有栈的成员函数都是共有的，其他类的成员函数都可以使用这些函数，但是，栈的存储表示和成员函数的实现对其他类的成员来说都是隐蔽的。
2009-7-25 3
4.1.1 顺序栈－－在顺序存储结构上实现的栈
# include < assert.h > //C＋＋断言功能
template <class Type > class Stack //顺序栈的类定义
{ public:
Stack ( int=10 );//栈初始化，建立一个空栈，缺省大小为 10
~Stack ( ) { delete [ ] elements ; }
void Push ( const Type & item ); //将数据元素 item 入栈
Type Pop ( ) ; //将栈顶元素出栈
Type GetTop ( ) ; //读取栈顶元素
void MakeEmpty ( ) { top=-1;} //置空栈,top=-1表示栈为空
int IsEmpty ( ) const { return top==-1;} //判栈空
int IsFull ( ) const { return top==maxSize-1;} //判栈满
private,//top=maxSize-1表示栈已满
int top;//栈顶指针（栈顶元素下标）
Type * elements;//存储顺序栈的数组
int maxSize;//顺序栈的最大容量
}
2009-7-25 4
顺序栈的基本操作（算法）
（ 1）顺序栈初始化算法（构造函数）
template <class Type> Stack<Type>::Stack(int s):top(-1),maxSize(s)
//建立一个最大尺寸为 s 的空栈，若分配不成功则错误处理
{
element=new Type[maxSize];//创建顺序栈空间（数组）
assert( elements != 0);
//断言语句：若条件成立，则继续；否则出错处理并终止执行
}
（ 2）顺序栈入栈算法
template <class Type> void Stack<Type>::Push(const Type & item)
//若栈不满，则将元素 item 插入到栈顶，否则出错处理
{
assert( ! IsFull());//断言：栈不满则继续执行
elements[++top]=item;//栈顶指针先加 1,然后按此地址进栈
}
2009-7-25 5
（ 3）顺序栈出栈算法
template <class Type> Type Stack<Type>::Pop()
//若栈不空，则返回栈顶元素，并使栈顶指针退 1 ；否则出错处理
{
assert( ! IsEmpty());//断言：若栈不空，则继续执行
return elements[top--];//返回栈顶元素，并使栈顶指针退 1
}
（ 4）读取顺序栈栈顶元素算法
Template <class Type> Type Stack<Type>::GetTop()
//若栈不空，则返回栈顶元素；否则出错处理
{
assert( ! IsEmpty());//断言：若栈不空，则继续执行
return elements[top];//返回栈顶元素，注意：栈顶指针不变
}
2009-7-25 6
4.1.3 链栈 —— 利用链式存贮结构实现的栈与顺序表一样，顺序栈的最大尺寸（ maxSize）也难以确定，太小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域，
宜采用链栈。
链栈的结构如下图所示。与单链表相似，但不设头结点，第一个结点即为栈顶。插入（入栈）与删除（出栈）操作均只能在表头进行。
当 top = NULL 时，表示空栈
… ^top
栈顶元素 栈底元素
2009-7-25 7
链栈的定义：
链栈结点类的定义：
template <class Type> class Stack; //链栈类的前视声明
template <class Type> class StackNode
{
friend class Stack <Type>;
private:
Type data;
StackNode <Type> * link;
StackNode(Type d=0,StackNode<Type> * l=NULL):
data(d),link(l) { } //构造函数，初始化一链栈结点
}
data link
链栈结点结构
2009-7-25 8
链栈类的定义：
template <class Type> class Stack
{ public:
Stack( ),top(NULL) { } //构造函数，初始化一个空链栈
~Stack( );
//析构函数，释放链栈的所有结点，并使 top=NULL。置栈空操作
void Push(const Type & item); //入栈操作
Type Pop( ); //出栈操作
Type GetTop( ); //读取栈顶元素
void MakeEmpty( ) { top=NULL;}
//置栈空操作，应先删除栈内所有结点
int IsEmpty( ) const {return top == NULL;} //判栈空操作
int IsFull ( ) const {return 0}
//判栈满，在链栈中该操作无意义
private:
StackNode<Type> * top; //栈顶指针
}
2009-7-25 9
链栈的入栈算法：
Template <class Type> void Stack<Type>,,Push(const Type & item)
//将数据元素 item 入栈
{
top=new StackNode<Type>(item,top);
//创建一个新的链栈结点，并将该结点的 data 域置为 item,
//link 域置为 top,最后将该结点的指针赋值给 top,参见下图
}
… ^
top 原栈顶新栈顶
item
(1)(2)
2009-7-25 10
比较与思考：
（ 1）比较顺序栈与链栈的类定义两者的类名相同，均为 Stack
两者成员函数的名、参数、返回类型与规格说明均相同，但内部的实现有别假定某大型软件系统原来使用顺序栈，因经常上溢，欲改用链栈，请问哪些部分需要改动？
2009-7-25 11
栈应用举例 —— 迷宫问题迷宫问题：求迷宫中从入口点到出口点所有可能的简单路径迷宫模型：
入口
(i,j)
出口墙通道
2009-7-25 12
所谓的简单路径是指：在求出的任何一条路径上，不能重现某一通道块，否则总有任意多条路径迷宫问题是许多实际问题的抽象，求解这类问题时，没有现成的数学公式可以套用，只能采用系统化的试探方法。
下面规定：
通道用空格,,表示墙壁用,#,表示足迹用,0,表示从入口点到当前立足点间，具有足迹标志的相连的通道块构成的简单路径叫当前路径将迷宫模型用二维字符型数组表示：
char maze[n+1][n+1];
并假定入口为 maze[0][0],出口为 maze[n][n]
考虑一般情况，设 maze[ i ][ j ] 为当前立足点，并纳入当前路径
（即印上足迹标志,0,），则从当前立足点继续试探的算法如下：
2009-7-25 13
if maze[ i ][ j ] 是出口
then 打印刚找到的一条简单路径，并回溯一步；
else if 东面的是通道块
then 前进一步
else if 南面的是通道块
then 前进一步
else if 西面的是通道块
then 前进一步
else if 北面的是通道块
then 前进一步
else 回溯一步( i,j ) 东南西北
2009-7-25 14
前进一步：将下一通道块印上,0,作为当前立足点（切换当前立足点），并保存原立足点的信息以便回溯。
回溯一步：去掉当前立足点的足迹,0,;
把最近的原立足点重新切换为当前立足点；
试探尚未试探过的方向。
上述的活动均需要在迷宫中移动，并且具有方向性，这种活动可以使用二维数组下标增量技术来实现：
行下标增量 di[ k ]
列下标增量 dj[ k ]
方向及其序号 k 东 0 南 1 西 2 北 3
int di[4]={0,1,0,-1};
int dj[4]={1,0,-1,0};
0
1
1
0
0
－ 1
－ 1
0
2009-7-25 15
在上述的规定下：
k=0 时,maze[i+di[k]][j+dj[k]] 为立足点的东面下一块；
k=1 时,maze[i+di[k]][j+dj[k]] 为立足点的南面下一块；
k=2 时,maze[i+di[k]][j+dj[k]] 为立足点的西面下一块；
k=3 时,maze[i+di[k]][j+dj[k]] 为立足点的北面下一块；
客体的表示方法设计：从上述的用试探法走迷宫的过程可知，其中所管理的信息是立足点的信息。可以用三元组 （ i,j,k ) 来表示立足点，其中 ( i,j ) 表示立足点的位置信息,k 表示立足点的下一个试探方向。可以将三元组定义成一个结构：
struct items { int i,j,k; };
数据的组织方法设计：
考察上述用试探法走迷宫的过程：
前进一步时，需要保存原立足点的信息；
回溯一步时，需要取出最近的原立足点的信息，并且遵循后保存的先取出的原则，即“后进先出”的原则，因此可以用栈来记录立足点的信息。
迷宫问题的算法框架：
2009-7-25 16
1 Stack <items> s(sz);
//栈初始化：创建一个大小为 sz 的栈，其数据元素类型为 items
2 items e; int k;
3 e.i=0; e.j=0; e.k=0; s.Push( e ); maze[ e.i ][e.j]=‘0’;
//将入口作为立足点并入栈
4 while ( ! s.IsEmpty( ) ) //若栈不空则继续循环试探
//若空表示已找到所有简单路径，可以结束程序
5 {e=s.Pop( ); //出栈，准备试探下一方向或实现回溯一步操作
6 if ( e.k==4 ) maze[ e.i ][e.j]=‘ ‘; //四个方向均试探完毕
//消足迹,当再执行到 5 时回溯一步
else if ( e.i==n && e.j==n ) printmaze(); //当前立足点为出口
//成功找到一条简单路径并输出，当再执行到 5 时回溯一步
else{k=e.k; e.k=e.k+1;s.Push( e ); //记住立足点的下一试探方向
e.i=e.i+di[k]; e.j=e.j+dj[k]; e.k=0; //沿 k 方向前进一步
if ( maze[e.i][e.j]==‘ ‘ )//若为通道则切换为新立足点并入栈
{s.Push( e ); maze[ e.i ][e.j]=‘0’;}
}
}
2009-7-25 17
作业：
完善迷宫问题解决算法（迷宫数组的输入 inputmaze() 算法、
简单路径的输出 printmaze() 算法等）
编写软件并上机实习要求 11 月 6 日前完成
2009-7-25 18
4.3 队列定义：队列是限制插入操作只能在一端进行，而删除操作只能在另一端进行的线性表，并按先进向出（ FIFO）的原则进行操作。
在一个队列中，能进行删除的一端称为队首（ front），能进行插入操作的一端称为队尾（ rear）。
出列 入列队首（ front） 队尾（ rear）
与栈类似，队列的封闭性也非常好栈能对输入序列部分或全局起求逆作用队列对输入序列起缓冲作用，队列的应用非常广泛
e0 e1 … en-2 en-1
2009-7-25 19
队列的基本操作
Template < class Type > class Queue
{
public:
Queue ( int = 10 ); //构造函数，队列初始化操作
void EnQueue ( const Type & item ); //入列操作
Type DeQueue ( ); //出列操作
Type GetFront ( ); //读取队首元素操作
void MakeEmpty ( ); //置队空操作
int IsEmpty ( ) const; //判队空操作
int IsFull ( ) const; //判队满操作
}
2009-7-25 20
队列的顺序存储结构 —— 循环队列（环型队列）
由于在队列的入列和出列操作中，其对应的队尾和队首指针（下标）都是进 1 操作（否则出列操作需要移动所有的数据元素），随着入列和出列操作的进行，队尾和队首指针都在逐步增大，因此队列若用普通的顺序存储结构来实现，则很容易上溢，
基本不能使用，因此实际中一般使用循环队列。
通过求余运算（ %），可以实现下标的循环累进：
index = ( index + 1 ) % m
0 1 2 … m -1
因此，对队首和队尾进行如下操作就可以实现循环队列：
front = ( front +1 ) % maxSize 队首指针循环进 1
rear = ( rear + 1 ) % maxSize 队尾指针循环进 1
maxSize表示数组的最大尺寸
front 和 rear 的最大取值为 maxSize-1
2009-7-25 21
循环队列：逆时针运行示意图
Queue
0
1
2
maxSize-1
maxSize-2
front
队首指针
rear
队尾指针规定：
队空,front==rear
队满,front==(rear+1) % maxSize
队尾元素：
elements[rear]
队首元素：
elements [ (front+1) % maxSize ]
@ @ @ @
2009-7-25 22
循环队列：满队列示意图
Queue
0
1
2
maxSize-1
maxSize-2
front 队首指针
rear 队尾指针front==(rear+1) % maxSize
本图满足上述队满条件。
由图可知：队满时队首指针所指的单元不能利用，此时再入列会使队列变成空队列 ( front==rear )
队尾元素 elements[rear]
队首元素
@ @ @ @
@
@
@
@ @
@
@
@
2009-7-25 23
循环队列的类定义：
#include <assert.h>
template < class Type > class Queue
{ public,
Queue ( int=10 ) ;
~Queue ( ) { delete [ ] elements ; }
void EnQueue ( const Type & item ) ;
Type DeQueue ( ) ;
Type GetFront ( ) ;
void MakeEmpty ( ) { front=rear=0 ; }
int IsEmpty ( ) const { return front==rear ; }
int IsFull ( ) const { return front==(rear+1) % maxSize ; }
int Length ( ) const { return (rear-front+maxSize) % maxSize ;}
private,
int rear,front,maxSize ;
Type * elements ;
}
2009-7-25 24
循环队列入列操作算法：
template <class Type> void Queue<Type>::EnQueue(const Type & item)
//若队列不满，则将元素 item 插入到队尾，否则出错处理
{
assert( ! IsFull ( ) );//断言：队列不满则继续，否则出错处理
rear = ( rear + 1 ) % maxSize;//队尾指针循环加 1
elements[ rear ]= item;//在队尾插入 item
}
循环队列出列操作算法：
template <class Type> Type Queue<Type>::DeQueue( )
//若队列不空，则删除并返回队首元素，否则出错处理
{
assert( ! IsEmpty ( ) );//断言：队列不空则继续，否则出错处理
front = ( front + 1 ) % maxSize;//队首指针循环加 1，队首元素出列
return elements[ front ];//返回出列的队首元素
}
2009-7-25 25
4.3.3 链队列 —— 利用链式存贮结构实现的队列与顺序表一样，循环队列的最大尺寸（ maxSize）也难以确定，
太小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域，宜采用链队列。
链队列的结构如下图所示。与单链表相似，但不设头结点，第一个结点即为队首。最后一个结点为队尾。插入（入列）操作只能在队尾进行，删除（出列）操作只能在队首进行。
当 front=rear = NULL 时，表示空队列
… ^front
队首指针队首 队尾
rear
队尾指针
2009-7-25 26
链队列的类定义
template <class Type> class Queue;
template <class Type> class QueueNode
{//链队列结点的类定义
friend class Queue<Type>;//将链队列类作为链队列结点类的友元
private:
Type data;
QueueNode<Type> * link;
QueueNode(Type d=0,QueueNode * l=NULL):
data( d ),link( l ) { }
};
template <class Type> class Queue//链队列的类定义
{ public:
//链队列类的成员函数
private:
QueueNode<Type> * front,* rear;//队首与队尾指针
};
2009-7-25 27
链队列类的成员函数：
Queue ( int =10),rear ( NULL ),front ( NULL ) { }//构造函数，建立一个
//空链队列,int 型参数是为了与循环队列一致而设，此处无意义
~Queue ( ) ; //析构函数，释放链队列的所有结点，参见下页定义
void EnQueue ( const Type & item );//入列操作
Type DeQueue ( );//出列操作
Type GetFront ( );//读取队首元素
void MakeEmpty ( );//置空队列，与析构函数类似，参见下页定义
int IsEmpty ( ) const { return front == NULL ; }//判队空操作
int IsFull ( ) const;//为了与循环队列一致而设，对链队列无意义
int Length ( ) const;//为了与循环队列一致而设，对链队列意义不大比较循环队列的类定义可知：链队列的成员函数的名、返回类型和参数表与循环队列的完全一样，这样安排的好处是，当一个大型软件原来使用循环队列时经常发生溢出，此时改用链队列的话只需将原来循环队列的类定义及其成员函数定义改为链队列的类定义和成员函数定义即可，无需更改软件的其他地方。
2009-7-25 28
链队列成员函数定义：
Template <class Type> void Queue<Type>::~Queue( )
{//析构函数，释放链队列中所有的结点
QueueNode<Type> * p ;
while ( front != NULL )
{//队列不空，继续循环
p = front ;// (1)
front = front -> link ;// (2) 出列队首结点
delete p ;//释放出列的结点
}
}
front ^…
rearp front
( 1 ) ( 2 )
2009-7-25 29
置空队列操作：
Template <class Type> void Queue<Type>::MakeEmpty( )
{//置空队列操作，释放链队列中所有的结点
QueueNode<Type> * p ;
while ( front != NULL )
{//队列不空，继续循环
p = front ;front = front -> link ;// 出列队首结点
delete p ;//释放出列的结点
}
}
链队列入列操作：
Template <class Type> void Queue<Type>::EnQueue(const Type & item)
{ QueueNode<Type> * p =new QueueNode<Type> ( item,NULL );
if ( front == NULL ) front = rear = p ;
else {rear->link= p ;//(1)
rear = p ;//(2)
}
} ^
…
rear rear
p
(1)
(2)
原队尾 新队尾
item
2009-7-25 30
链队列出列操作：
template <class Type> Type Queue<Type>::DeQueue ( )
//若队列不空，则删除队首结点并返回该结点的值，否则出错处理
{ assert ( ! IsEmpty( ) );//若队列不空，则继续，否则出错处理
QueueNode<Type> * p = front ;//保留队首结点指针（ 1）
Type retvalue = p->data;//读取队首结点的值
front=front->link;//队首指针指向下一结点，即删除队首结点（ 2）
if ( rear==p ) rear=NULL; //若原队列只有一个结点，
//则出列后为空队列,front=rear=NULL
delete p;//释放原队首结点
return retvalue;//返回原队首结点的值
} 原队首 新队首
…front
p front
(1) (2)
2009-7-25 31
4.5 事件驱动模拟（ Event-Driven Simulation ）
模拟目的：
（ 1）计算银行顾客的平均（最大）等待时间
（ 2）计算银行出纳员的工作繁忙程度
（ 3）计算银行顾客队列的最大长度出纳员服务原则：
（ 1）某一时刻只能接待一位顾客
（ 2）若本窗口还有顾客则应立刻服务顾客活动原则：
（ 1）顾客达到时间为 ArrivalTime（随机数）
（ 2）顾客需要服务的时间为 ServiceTime（随机数）
（ 3）顾客选择最短的队列排队
（ 4）顾客的等待时间（从进门到轮到服务）为 WaitTime
（ 5）银行上班时间到后顾客才能进门，下班时间到时顾客不能进门
2009-7-25 32
仿真模型：
窗口队列 服务窗口顾客选择排队顾客流（队列）
…… ……
2009-7-25 33
事件分析：
顾客进门事件触发下列操作：
（ 1）从顾客流队列中出列进门事件
（ 2）从各窗口队列中选择一最短队列
（ 3）计算顾客需要等待的时间
（ 4）将该顾客入列到所选的最短窗口队列中出纳员对当前顾客服务完毕事件触发下列操作：
（ 1）累计本窗口的服务时间
（ 2）累计本窗口顾客的等待时间
（ 3）记录本窗口顾客的最大等待时间
（ 4）记录本窗口的最大队列长度
（ 5）累计本窗口服务的顾客总数
（ 6）将当前顾客出列
2009-7-25 34
数据结构设计：
（ 1）顾客信息的表示 —— 可将其定义为一结构 Event
进门时间（随机数） ArrivalTime —— 事件进门序号（顾客号） CustomerID —— 用于统计顾客总数要求服务的时间（随机数） ServiceTime
需要等待的时间（计算数） WaitTime
（ 2）窗口信息的表示 —— 将其定义为一结构 TellerStatus
本窗口完成当前窗口队列服务的时刻 finishService
本窗口已经服务的顾客总数 CustomerCount
本窗口的累计顾客等待时间 totalCustomerWait
本窗口的最大顾客等待时间 maxCustomerWait
本窗口的最大队列长度 maxQlength
本窗口的累计服务时间 totalService
（ 3）数据的组织方法 —— 采用队列将未进门的顾客按将要进门的先后顺序入列到顾客流队列中将已进门的顾客（进门事件）入列到最短窗口队列中
2009-7-25 35
仿真算法思路：
（ 1）利用随机数发生器预先计算一天中达到银行的所有顾客，并将他们入列到顾客流队列 CustomerFlow 中。
该功能由下述的 CreateCustomerFlow( ) 函数实现：
Queue<Event> CustomerFlow;//定义顾客流队列
void CreateCustomerFlow( )//创建顾客流队列
{ Event e= GetAEvent( );//获取一事件（使用随机数发生器）
CustomerFlow.EnQueue( e );//将事件入列到顾客流队列中
}//上述的每一事件代表一个顾客
（ 2）用一虚拟时钟 VirtualTimer 来模拟前述进门事件和服务完毕事件的发生。此处的虚拟时钟是一查询循环，
每循环一次代表走过一个时间单位，用查询模拟随机的中断请求，从而实现用顺序执行模拟并发执行过程。该功能由下页的 RunSimulation( ) 函数实现。
2009-7-25 36
仿真运行函数设计：
若规定上班时间为 StartTime,下班时间为 EndTime,则查询循环结构如下：
Void RunSimulation( )
//
{
for ( int t=StartTime ; t<EndTime ; t++ ) //虚拟时钟
{ Event e=CustomerFlow.GetFront( );//读取顾客流队列的队首
if ( e.ArrivalTime==t ) ArrivalEvent( );
//发现一进门事件并作相应处理。
for ( i=0 ; i < tellernum ; i++ )//查询各窗口有无服务完毕事件
{ e=Windowq[i].GetFront( );
int time=e.ArrivalTime+e.waitTime+e.serviceTime;
if ( t>=time ) ServicedEvent(i);
//发现窗口 i 有一服务完毕事件并作相应处理
}
}
}
2009-7-25 37
进门事件处理函数
Queue<Event> Windowq[ tellernum ];//共定义了 tellernum 个窗口队列
Void ArrivalEvent( )//进门事件处理
{ Event e = CustomerFlow.DeQueue( );
//将进门事件从顾客流队列中出列到事件变量 e 中
//下面程序段实现从所有窗口队列中选择一最短队列
//若长度都一样，则选择 Windowq[0]
int j = 0;
int minLength = Windowq[ 0 ],Length( );
for ( int i = 1 ; i < tellernum ; i++ )
{ int L=Windowq[ i ],Length( );
if ( L< minLength )
{ j = i ;
minLength=L ;
}
}
2009-7-25 38
//改变窗口 j 的工作表
e.WaitTime=tstat[j].finishService-e.ArrivalTime;//计算等待时间
if ( e.WaitTime<0 ) {e.WaitTime=0; //窗口队列 j 为空队列
tstat[j].finishService=e.ArrivalTime+e.serviceTime;}//图 2
else tstat[j].finishService+=e.serviceTime; //图 1
Windowq[ j ],EnQueue( e );//将进门事件入列到最短窗口队列中
}
e.ArrivalTime 原 tstat[j].finishService 新 tstat[j].finishService
时间图 1
e.WaitTime e.serviceTime
原 tstat[j].finishService e.ArrivalTime 新 tstat[j].finishService
时间空闲时间 图 2
e.serviceTime
2009-7-25 39
服务完毕事件处理函数定义：
TellerStatus tstat [ tellernum ];
void ServiceEvent ( int windownum )
//累计本窗口的服务时间、顾客数和顾客的等待时间；
//记录本窗口顾客的最大等待时间和本窗口的最大队列长度；
{ int k=windownum;
int L= Windowq[k].Length( ) ;
if ( tstat[k].maxQlength< L ) tstat[k].maxQlength= L ;
//记录本窗口的最大队列长度
Event e=Windowq[k].DeQueue( ); //将当前顾客出列
tstat[k].totalService+=e.serviceTime; //累计本窗口的服务时间
tstat[k].totalCustomerWait+=e.WaitTime; //累计顾客的等待时间
if ( tstat[k].maxCustomerWait <e.WaitTime ) //记录本窗口顾客的
tstat[k].maxCustomerWait =e.WaitTime ;//最大等待时间
tstat[k].CustomerCount++;//累计本窗口的顾客数
}
2009-7-25 40
目标计算
Void printResult( )//计算并输出仿真结果
{ int sumWait=0,sumCustomer=0,maxlength=0,maxwait=0;
for ( int k=0;k<tellernum;k++ ） //计算所有顾客等待时间之和
{ sumWait+=tstat[k].totalCustomerWait;
sumCustomer+=tstat[k].Customercount;
tellerWork[k]= tstat[k].totalService/(EndTime-StartTime);
//各出纳员的工作繁忙度
if ( maxlength<tstat[k].maxQlength )
maxlength=tstat[k].maxQlength ;//最大队列长度
if ( maxwait<tstat[k].maxCustomerWait )
maxwait=tstat[k].maxCustomerWait;;//最大等待时间
}
float averagewait＝ sumWait/sumCustomer;//平均等待时间
output(maxwait,averagewait,maxlength,tellerWork);//输出
}
2009-7-25 41
主程序
#include<iostream.h>
#include<random.h>
#include<queue.h>
#include<simulation.h>
int main( )
{
inputBasicData( );//输入基本数据
CreatCustomerFlow( );//创建顾客流队列
RunSimulation( );//运行
printResult( );//计算并输出结果
}
2009-7-25 42
2009-7-25 43
2009-7-25 44
2009-7-25 45
2009-7-25 46
2009-7-25 47
2009-7-25 48
2009-7-25 49
2009-7-25 50
2009-7-25 51
2009-7-25 52
2009-7-25 53
2009-7-25 54
2009-7-25 55
2009-7-25 56
2009-7-25 57
2009-7-25 58
2009-7-25 59
2009-7-25 60
2009-7-25 61
2009-7-25 62
2009-7-25 63
2009-7-25 64
2009-7-25 65
2009-7-25 66
第四章 栈和队列栈和队列都是操作受限的线性表，应用十分广泛。
4.1 栈（ Stack）
定义：栈是限制插入和删除操作只能在某一端进行的线性表，并按先进后出（ F I L O )或后进先出（Ｌ IＦＯ）的原则进行操作入栈顺序：
e0 e1 e2 … en-2 en-1
出栈顺序：
en-1 en-2 … e2 e1 e0
栈可以对序列实现求逆
en-1
e0
e1
en-2
…
进栈（ Push） 出栈（ Pop）
栈顶 top
栈底
2009-7-25 2
栈的基本操作,（参见 P104）
（ 1）栈初始化 Stack ( int = 10 );//构造函数
（ 2）进栈 Push void Push( const Type & item );
（ 3）出栈 Pop Type Pop( );
（ 4）判栈空 IsEmpty int IsEmpty( ) { return top==-1;}
（ 5）读取栈顶元素 GetTop Type GetTop ( );
（ 6）置空栈 MakeEmpty void MakeEmpty( ) { top=-1;}
（ 7）判栈满 IsFull int IsFull( ) const { return top==maxSize;}
栈的封闭性及其抽象数据类型：
在一个栈中，出入口处称为栈顶，栈内最深处称为栈底。除了栈顶元素外，其他元素不会被改变，因而栈的封闭性非常好，
使用起来非常安全。另外，在下面的栈的类定义中，体现了栈的抽象数据类型，在此定义中，所有栈的成员函数都是共有的，其他类的成员函数都可以使用这些函数，但是，栈的存储表示和成员函数的实现对其他类的成员来说都是隐蔽的。
2009-7-25 3
4.1.1 顺序栈－－在顺序存储结构上实现的栈
# include < assert.h > //C＋＋断言功能
template <class Type > class Stack //顺序栈的类定义
{ public:
Stack ( int=10 );//栈初始化，建立一个空栈，缺省大小为 10
~Stack ( ) { delete [ ] elements ; }
void Push ( const Type & item ); //将数据元素 item 入栈
Type Pop ( ) ; //将栈顶元素出栈
Type GetTop ( ) ; //读取栈顶元素
void MakeEmpty ( ) { top=-1;} //置空栈,top=-1表示栈为空
int IsEmpty ( ) const { return top==-1;} //判栈空
int IsFull ( ) const { return top==maxSize-1;} //判栈满
private,//top=maxSize-1表示栈已满
int top;//栈顶指针（栈顶元素下标）
Type * elements;//存储顺序栈的数组
int maxSize;//顺序栈的最大容量
}
2009-7-25 4
顺序栈的基本操作（算法）
（ 1）顺序栈初始化算法（构造函数）
template <class Type> Stack<Type>::Stack(int s):top(-1),maxSize(s)
//建立一个最大尺寸为 s 的空栈，若分配不成功则错误处理
{
element=new Type[maxSize];//创建顺序栈空间（数组）
assert( elements != 0);
//断言语句：若条件成立，则继续；否则出错处理并终止执行
}
（ 2）顺序栈入栈算法
template <class Type> void Stack<Type>::Push(const Type & item)
//若栈不满，则将元素 item 插入到栈顶，否则出错处理
{
assert( ! IsFull());//断言：栈不满则继续执行
elements[++top]=item;//栈顶指针先加 1,然后按此地址进栈
}
2009-7-25 5
（ 3）顺序栈出栈算法
template <class Type> Type Stack<Type>::Pop()
//若栈不空，则返回栈顶元素，并使栈顶指针退 1 ；否则出错处理
{
assert( ! IsEmpty());//断言：若栈不空，则继续执行
return elements[top--];//返回栈顶元素，并使栈顶指针退 1
}
（ 4）读取顺序栈栈顶元素算法
Template <class Type> Type Stack<Type>::GetTop()
//若栈不空，则返回栈顶元素；否则出错处理
{
assert( ! IsEmpty());//断言：若栈不空，则继续执行
return elements[top];//返回栈顶元素，注意：栈顶指针不变
}
2009-7-25 6
4.1.3 链栈 —— 利用链式存贮结构实现的栈与顺序表一样，顺序栈的最大尺寸（ maxSize）也难以确定，太小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域，
宜采用链栈。
链栈的结构如下图所示。与单链表相似，但不设头结点，第一个结点即为栈顶。插入（入栈）与删除（出栈）操作均只能在表头进行。
当 top = NULL 时，表示空栈
… ^top
栈顶元素 栈底元素
2009-7-25 7
链栈的定义：
链栈结点类的定义：
template <class Type> class Stack; //链栈类的前视声明
template <class Type> class StackNode
{
friend class Stack <Type>;
private:
Type data;
StackNode <Type> * link;
StackNode(Type d=0,StackNode<Type> * l=NULL):
data(d),link(l) { } //构造函数，初始化一链栈结点
}
data link
链栈结点结构
2009-7-25 8
链栈类的定义：
template <class Type> class Stack
{ public:
Stack( ),top(NULL) { } //构造函数，初始化一个空链栈
~Stack( );
//析构函数，释放链栈的所有结点，并使 top=NULL。置栈空操作
void Push(const Type & item); //入栈操作
Type Pop( ); //出栈操作
Type GetTop( ); //读取栈顶元素
void MakeEmpty( ) { top=NULL;}
//置栈空操作，应先删除栈内所有结点
int IsEmpty( ) const {return top == NULL;} //判栈空操作
int IsFull ( ) const {return 0}
//判栈满，在链栈中该操作无意义
private:
StackNode<Type> * top; //栈顶指针
}
2009-7-25 9
链栈的入栈算法：
Template <class Type> void Stack<Type>,,Push(const Type & item)
//将数据元素 item 入栈
{
top=new StackNode<Type>(item,top);
//创建一个新的链栈结点，并将该结点的 data 域置为 item,
//link 域置为 top,最后将该结点的指针赋值给 top,参见下图
}
… ^
top 原栈顶新栈顶
item
(1)(2)
2009-7-25 10
比较与思考：
（ 1）比较顺序栈与链栈的类定义两者的类名相同，均为 Stack
两者成员函数的名、参数、返回类型与规格说明均相同，但内部的实现有别假定某大型软件系统原来使用顺序栈，因经常上溢，欲改用链栈，请问哪些部分需要改动？
2009-7-25 11
栈应用举例 —— 迷宫问题迷宫问题：求迷宫中从入口点到出口点所有可能的简单路径迷宫模型：
入口
(i,j)
出口墙通道
2009-7-25 12
所谓的简单路径是指：在求出的任何一条路径上，不能重现某一通道块，否则总有任意多条路径迷宫问题是许多实际问题的抽象，求解这类问题时，没有现成的数学公式可以套用，只能采用系统化的试探方法。
下面规定：
通道用空格,,表示墙壁用,#,表示足迹用,0,表示从入口点到当前立足点间，具有足迹标志的相连的通道块构成的简单路径叫当前路径将迷宫模型用二维字符型数组表示：
char maze[n+1][n+1];
并假定入口为 maze[0][0],出口为 maze[n][n]
考虑一般情况，设 maze[ i ][ j ] 为当前立足点，并纳入当前路径
（即印上足迹标志,0,），则从当前立足点继续试探的算法如下：
2009-7-25 13
if maze[ i ][ j ] 是出口
then 打印刚找到的一条简单路径，并回溯一步；
else if 东面的是通道块
then 前进一步
else if 南面的是通道块
then 前进一步
else if 西面的是通道块
then 前进一步
else if 北面的是通道块
then 前进一步
else 回溯一步( i,j ) 东南西北
2009-7-25 14
前进一步：将下一通道块印上,0,作为当前立足点（切换当前立足点），并保存原立足点的信息以便回溯。
回溯一步：去掉当前立足点的足迹,0,;
把最近的原立足点重新切换为当前立足点；
试探尚未试探过的方向。
上述的活动均需要在迷宫中移动，并且具有方向性，这种活动可以使用二维数组下标增量技术来实现：
行下标增量 di[ k ]
列下标增量 dj[ k ]
方向及其序号 k 东 0 南 1 西 2 北 3
int di[4]={0,1,0,-1};
int dj[4]={1,0,-1,0};
0
1
1
0
0
－ 1
－ 1
0
2009-7-25 15
在上述的规定下：
k=0 时,maze[i+di[k]][j+dj[k]] 为立足点的东面下一块；
k=1 时,maze[i+di[k]][j+dj[k]] 为立足点的南面下一块；
k=2 时,maze[i+di[k]][j+dj[k]] 为立足点的西面下一块；
k=3 时,maze[i+di[k]][j+dj[k]] 为立足点的北面下一块；
客体的表示方法设计：从上述的用试探法走迷宫的过程可知，其中所管理的信息是立足点的信息。可以用三元组 （ i,j,k ) 来表示立足点，其中 ( i,j ) 表示立足点的位置信息,k 表示立足点的下一个试探方向。可以将三元组定义成一个结构：
struct items { int i,j,k; };
数据的组织方法设计：
考察上述用试探法走迷宫的过程：
前进一步时，需要保存原立足点的信息；
回溯一步时，需要取出最近的原立足点的信息，并且遵循后保存的先取出的原则，即“后进先出”的原则，因此可以用栈来记录立足点的信息。
迷宫问题的算法框架：
2009-7-25 16
1 Stack <items> s(sz);
//栈初始化：创建一个大小为 sz 的栈，其数据元素类型为 items
2 items e; int k;
3 e.i=0; e.j=0; e.k=0; s.Push( e ); maze[ e.i ][e.j]=‘0’;
//将入口作为立足点并入栈
4 while ( ! s.IsEmpty( ) ) //若栈不空则继续循环试探
//若空表示已找到所有简单路径，可以结束程序
5 {e=s.Pop( ); //出栈，准备试探下一方向或实现回溯一步操作
6 if ( e.k==4 ) maze[ e.i ][e.j]=‘ ‘; //四个方向均试探完毕
//消足迹,当再执行到 5 时回溯一步
else if ( e.i==n && e.j==n ) printmaze(); //当前立足点为出口
//成功找到一条简单路径并输出，当再执行到 5 时回溯一步
else{k=e.k; e.k=e.k+1;s.Push( e ); //记住立足点的下一试探方向
e.i=e.i+di[k]; e.j=e.j+dj[k]; e.k=0; //沿 k 方向前进一步
if ( maze[e.i][e.j]==‘ ‘ )//若为通道则切换为新立足点并入栈
{s.Push( e ); maze[ e.i ][e.j]=‘0’;}
}
}
2009-7-25 17
作业：
完善迷宫问题解决算法（迷宫数组的输入 inputmaze() 算法、
简单路径的输出 printmaze() 算法等）
编写软件并上机实习要求 11 月 6 日前完成
2009-7-25 18
4.3 队列定义：队列是限制插入操作只能在一端进行，而删除操作只能在另一端进行的线性表，并按先进向出（ FIFO）的原则进行操作。
在一个队列中，能进行删除的一端称为队首（ front），能进行插入操作的一端称为队尾（ rear）。
出列 入列队首（ front） 队尾（ rear）
与栈类似，队列的封闭性也非常好栈能对输入序列部分或全局起求逆作用队列对输入序列起缓冲作用，队列的应用非常广泛
e0 e1 … en-2 en-1
2009-7-25 19
队列的基本操作
Template < class Type > class Queue
{
public:
Queue ( int = 10 ); //构造函数，队列初始化操作
void EnQueue ( const Type & item ); //入列操作
Type DeQueue ( ); //出列操作
Type GetFront ( ); //读取队首元素操作
void MakeEmpty ( ); //置队空操作
int IsEmpty ( ) const; //判队空操作
int IsFull ( ) const; //判队满操作
}
2009-7-25 20
队列的顺序存储结构 —— 循环队列（环型队列）
由于在队列的入列和出列操作中，其对应的队尾和队首指针（下标）都是进 1 操作（否则出列操作需要移动所有的数据元素），随着入列和出列操作的进行，队尾和队首指针都在逐步增大，因此队列若用普通的顺序存储结构来实现，则很容易上溢，
基本不能使用，因此实际中一般使用循环队列。
通过求余运算（ %），可以实现下标的循环累进：
index = ( index + 1 ) % m
0 1 2 … m -1
因此，对队首和队尾进行如下操作就可以实现循环队列：
front = ( front +1 ) % maxSize 队首指针循环进 1
rear = ( rear + 1 ) % maxSize 队尾指针循环进 1
maxSize表示数组的最大尺寸
front 和 rear 的最大取值为 maxSize-1
2009-7-25 21
循环队列：逆时针运行示意图
Queue
0
1
2
maxSize-1
maxSize-2
front
队首指针
rear
队尾指针规定：
队空,front==rear
队满,front==(rear+1) % maxSize
队尾元素：
elements[rear]
队首元素：
elements [ (front+1) % maxSize ]
@ @ @ @
2009-7-25 22
循环队列：满队列示意图
Queue
0
1
2
maxSize-1
maxSize-2
front 队首指针
rear 队尾指针front==(rear+1) % maxSize
本图满足上述队满条件。
由图可知：队满时队首指针所指的单元不能利用，此时再入列会使队列变成空队列 ( front==rear )
队尾元素 elements[rear]
队首元素
@ @ @ @
@
@
@
@ @
@
@
@
2009-7-25 23
循环队列的类定义：
#include <assert.h>
template < class Type > class Queue
{ public,
Queue ( int=10 ) ;
~Queue ( ) { delete [ ] elements ; }
void EnQueue ( const Type & item ) ;
Type DeQueue ( ) ;
Type GetFront ( ) ;
void MakeEmpty ( ) { front=rear=0 ; }
int IsEmpty ( ) const { return front==rear ; }
int IsFull ( ) const { return front==(rear+1) % maxSize ; }
int Length ( ) const { return (rear-front+maxSize) % maxSize ;}
private,
int rear,front,maxSize ;
Type * elements ;
}
2009-7-25 24
循环队列入列操作算法：
template <class Type> void Queue<Type>::EnQueue(const Type & item)
//若队列不满，则将元素 item 插入到队尾，否则出错处理
{
assert( ! IsFull ( ) );//断言：队列不满则继续，否则出错处理
rear = ( rear + 1 ) % maxSize;//队尾指针循环加 1
elements[ rear ]= item;//在队尾插入 item
}
循环队列出列操作算法：
template <class Type> Type Queue<Type>::DeQueue( )
//若队列不空，则删除并返回队首元素，否则出错处理
{
assert( ! IsEmpty ( ) );//断言：队列不空则继续，否则出错处理
front = ( front + 1 ) % maxSize;//队首指针循环加 1，队首元素出列
return elements[ front ];//返回出列的队首元素
}
2009-7-25 25
4.3.3 链队列 —— 利用链式存贮结构实现的队列与顺序表一样，循环队列的最大尺寸（ maxSize）也难以确定，
太小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域，宜采用链队列。
链队列的结构如下图所示。与单链表相似，但不设头结点，第一个结点即为队首。最后一个结点为队尾。插入（入列）操作只能在队尾进行，删除（出列）操作只能在队首进行。
当 front=rear = NULL 时，表示空队列
… ^front
队首指针队首 队尾
rear
队尾指针
2009-7-25 26
链队列的类定义
template <class Type> class Queue;
template <class Type> class QueueNode
{//链队列结点的类定义
friend class Queue<Type>;//将链队列类作为链队列结点类的友元
private:
Type data;
QueueNode<Type> * link;
QueueNode(Type d=0,QueueNode * l=NULL):
data( d ),link( l ) { }
};
template <class Type> class Queue//链队列的类定义
{ public:
//链队列类的成员函数
private:
QueueNode<Type> * front,* rear;//队首与队尾指针
};
2009-7-25 27
链队列类的成员函数：
Queue ( int =10),rear ( NULL ),front ( NULL ) { }//构造函数，建立一个
//空链队列,int 型参数是为了与循环队列一致而设，此处无意义
~Queue ( ) ; //析构函数，释放链队列的所有结点，参见下页定义
void EnQueue ( const Type & item );//入列操作
Type DeQueue ( );//出列操作
Type GetFront ( );//读取队首元素
void MakeEmpty ( );//置空队列，与析构函数类似，参见下页定义
int IsEmpty ( ) const { return front == NULL ; }//判队空操作
int IsFull ( ) const;//为了与循环队列一致而设，对链队列无意义
int Length ( ) const;//为了与循环队列一致而设，对链队列意义不大比较循环队列的类定义可知：链队列的成员函数的名、返回类型和参数表与循环队列的完全一样，这样安排的好处是，当一个大型软件原来使用循环队列时经常发生溢出，此时改用链队列的话只需将原来循环队列的类定义及其成员函数定义改为链队列的类定义和成员函数定义即可，无需更改软件的其他地方。
2009-7-25 28
链队列成员函数定义：
Template <class Type> void Queue<Type>::~Queue( )
{//析构函数，释放链队列中所有的结点
QueueNode<Type> * p ;
while ( front != NULL )
{//队列不空，继续循环
p = front ;// (1)
front = front -> link ;// (2) 出列队首结点
delete p ;//释放出列的结点
}
}
front ^…
rearp front
( 1 ) ( 2 )
2009-7-25 29
置空队列操作：
Template <class Type> void Queue<Type>::MakeEmpty( )
{//置空队列操作，释放链队列中所有的结点
QueueNode<Type> * p ;
while ( front != NULL )
{//队列不空，继续循环
p = front ;front = front -> link ;// 出列队首结点
delete p ;//释放出列的结点
}
}
链队列入列操作：
Template <class Type> void Queue<Type>::EnQueue(const Type & item)
{ QueueNode<Type> * p =new QueueNode<Type> ( item,NULL );
if ( front == NULL ) front = rear = p ;
else {rear->link= p ;//(1)
rear = p ;//(2)
}
} ^
…
rear rear
p
(1)
(2)
原队尾 新队尾
item
2009-7-25 30
链队列出列操作：
template <class Type> Type Queue<Type>::DeQueue ( )
//若队列不空，则删除队首结点并返回该结点的值，否则出错处理
{ assert ( ! IsEmpty( ) );//若队列不空，则继续，否则出错处理
QueueNode<Type> * p = front ;//保留队首结点指针（ 1）
Type retvalue = p->data;//读取队首结点的值
front=front->link;//队首指针指向下一结点，即删除队首结点（ 2）
if ( rear==p ) rear=NULL; //若原队列只有一个结点，
//则出列后为空队列,front=rear=NULL
delete p;//释放原队首结点
return retvalue;//返回原队首结点的值
} 原队首 新队首
…front
p front
(1) (2)
2009-7-25 31
4.5 事件驱动模拟（ Event-Driven Simulation ）
模拟目的：
（ 1）计算银行顾客的平均（最大）等待时间
（ 2）计算银行出纳员的工作繁忙程度
（ 3）计算银行顾客队列的最大长度出纳员服务原则：
（ 1）某一时刻只能接待一位顾客
（ 2）若本窗口还有顾客则应立刻服务顾客活动原则：
（ 1）顾客达到时间为 ArrivalTime（随机数）
（ 2）顾客需要服务的时间为 ServiceTime（随机数）
（ 3）顾客选择最短的队列排队
（ 4）顾客的等待时间（从进门到轮到服务）为 WaitTime
（ 5）银行上班时间到后顾客才能进门，下班时间到时顾客不能进门
2009-7-25 32
仿真模型：
窗口队列 服务窗口顾客选择排队顾客流（队列）
…… ……
2009-7-25 33
事件分析：
顾客进门事件触发下列操作：
（ 1）从顾客流队列中出列进门事件
（ 2）从各窗口队列中选择一最短队列
（ 3）计算顾客需要等待的时间
（ 4）将该顾客入列到所选的最短窗口队列中出纳员对当前顾客服务完毕事件触发下列操作：
（ 1）累计本窗口的服务时间
（ 2）累计本窗口顾客的等待时间
（ 3）记录本窗口顾客的最大等待时间
（ 4）记录本窗口的最大队列长度
（ 5）累计本窗口服务的顾客总数
（ 6）将当前顾客出列
2009-7-25 34
数据结构设计：
（ 1）顾客信息的表示 —— 可将其定义为一结构 Event
进门时间（随机数） ArrivalTime —— 事件进门序号（顾客号） CustomerID —— 用于统计顾客总数要求服务的时间（随机数） ServiceTime
需要等待的时间（计算数） WaitTime
（ 2）窗口信息的表示 —— 将其定义为一结构 TellerStatus
本窗口完成当前窗口队列服务的时刻 finishService
本窗口已经服务的顾客总数 CustomerCount
本窗口的累计顾客等待时间 totalCustomerWait
本窗口的最大顾客等待时间 maxCustomerWait
本窗口的最大队列长度 maxQlength
本窗口的累计服务时间 totalService
（ 3）数据的组织方法 —— 采用队列将未进门的顾客按将要进门的先后顺序入列到顾客流队列中将已进门的顾客（进门事件）入列到最短窗口队列中
2009-7-25 35
仿真算法思路：
（ 1）利用随机数发生器预先计算一天中达到银行的所有顾客，并将他们入列到顾客流队列 CustomerFlow 中。
该功能由下述的 CreateCustomerFlow( ) 函数实现：
Queue<Event> CustomerFlow;//定义顾客流队列
void CreateCustomerFlow( )//创建顾客流队列
{ Event e= GetAEvent( );//获取一事件（使用随机数发生器）
CustomerFlow.EnQueue( e );//将事件入列到顾客流队列中
}//上述的每一事件代表一个顾客
（ 2）用一虚拟时钟 VirtualTimer 来模拟前述进门事件和服务完毕事件的发生。此处的虚拟时钟是一查询循环，
每循环一次代表走过一个时间单位，用查询模拟随机的中断请求，从而实现用顺序执行模拟并发执行过程。该功能由下页的 RunSimulation( ) 函数实现。
2009-7-25 36
仿真运行函数设计：
若规定上班时间为 StartTime,下班时间为 EndTime,则查询循环结构如下：
Void RunSimulation( )
//
{
for ( int t=StartTime ; t<EndTime ; t++ ) //虚拟时钟
{ Event e=CustomerFlow.GetFront( );//读取顾客流队列的队首
if ( e.ArrivalTime==t ) ArrivalEvent( );
//发现一进门事件并作相应处理。
for ( i=0 ; i < tellernum ; i++ )//查询各窗口有无服务完毕事件
{ e=Windowq[i].GetFront( );
int time=e.ArrivalTime+e.waitTime+e.serviceTime;
if ( t>=time ) ServicedEvent(i);
//发现窗口 i 有一服务完毕事件并作相应处理
}
}
}
2009-7-25 37
进门事件处理函数
Queue<Event> Windowq[ tellernum ];//共定义了 tellernum 个窗口队列
Void ArrivalEvent( )//进门事件处理
{ Event e = CustomerFlow.DeQueue( );
//将进门事件从顾客流队列中出列到事件变量 e 中
//下面程序段实现从所有窗口队列中选择一最短队列
//若长度都一样，则选择 Windowq[0]
int j = 0;
int minLength = Windowq[ 0 ],Length( );
for ( int i = 1 ; i < tellernum ; i++ )
{ int L=Windowq[ i ],Length( );
if ( L< minLength )
{ j = i ;
minLength=L ;
}
}
2009-7-25 38
//改变窗口 j 的工作表
e.WaitTime=tstat[j].finishService-e.ArrivalTime;//计算等待时间
if ( e.WaitTime<0 ) {e.WaitTime=0; //窗口队列 j 为空队列
tstat[j].finishService=e.ArrivalTime+e.serviceTime;}//图 2
else tstat[j].finishService+=e.serviceTime; //图 1
Windowq[ j ],EnQueue( e );//将进门事件入列到最短窗口队列中
}
e.ArrivalTime 原 tstat[j].finishService 新 tstat[j].finishService
时间图 1
e.WaitTime e.serviceTime
原 tstat[j].finishService e.ArrivalTime 新 tstat[j].finishService
时间空闲时间 图 2
e.serviceTime
2009-7-25 39
服务完毕事件处理函数定义：
TellerStatus tstat [ tellernum ];
void ServiceEvent ( int windownum )
//累计本窗口的服务时间、顾客数和顾客的等待时间；
//记录本窗口顾客的最大等待时间和本窗口的最大队列长度；
{ int k=windownum;
int L= Windowq[k].Length( ) ;
if ( tstat[k].maxQlength< L ) tstat[k].maxQlength= L ;
//记录本窗口的最大队列长度
Event e=Windowq[k].DeQueue( ); //将当前顾客出列
tstat[k].totalService+=e.serviceTime; //累计本窗口的服务时间
tstat[k].totalCustomerWait+=e.WaitTime; //累计顾客的等待时间
if ( tstat[k].maxCustomerWait <e.WaitTime ) //记录本窗口顾客的
tstat[k].maxCustomerWait =e.WaitTime ;//最大等待时间
tstat[k].CustomerCount++;//累计本窗口的顾客数
}
2009-7-25 40
目标计算
Void printResult( )//计算并输出仿真结果
{ int sumWait=0,sumCustomer=0,maxlength=0,maxwait=0;
for ( int k=0;k<tellernum;k++ ） //计算所有顾客等待时间之和
{ sumWait+=tstat[k].totalCustomerWait;
sumCustomer+=tstat[k].Customercount;
tellerWork[k]= tstat[k].totalService/(EndTime-StartTime);
//各出纳员的工作繁忙度
if ( maxlength<tstat[k].maxQlength )
maxlength=tstat[k].maxQlength ;//最大队列长度
if ( maxwait<tstat[k].maxCustomerWait )
maxwait=tstat[k].maxCustomerWait;;//最大等待时间
}
float averagewait＝ sumWait/sumCustomer;//平均等待时间
output(maxwait,averagewait,maxlength,tellerWork);//输出
}
2009-7-25 41
主程序
#include<iostream.h>
#include<random.h>
#include<queue.h>
#include<simulation.h>
int main( )
{
inputBasicData( );//输入基本数据
CreatCustomerFlow( );//创建顾客流队列
RunSimulation( );//运行
printResult( );//计算并输出结果
}
2009-7-25 42
2009-7-25 43
2009-7-25 44
2009-7-25 45
2009-7-25 46
2009-7-25 47
2009-7-25 48
2009-7-25 49
2009-7-25 50
2009-7-25 51
2009-7-25 52
2009-7-25 53
2009-7-25 54
2009-7-25 55
2009-7-25 56
2009-7-25 57
2009-7-25 58
2009-7-25 59
2009-7-25 60
2009-7-25 61
2009-7-25 62
2009-7-25 63
2009-7-25 64
2009-7-25 65
2009-7-25 66
