2011-7-18 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
栈底
2011-7-18 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;}
栈的封闭性及其抽象数据类型：
在一个栈中，出入口处称为栈顶，栈内最深处称为栈底。除
了栈顶元素外，其他元素不会被改变，因而栈的封闭性非常好，
使用起来非常安全。另外，在下面的栈的类定义中，体现了栈的
抽象数据类型，在此定义中，所有栈的成员函数都是共有的，其
他类的成员函数都可以使用这些函数，但是，栈的存储表示和成
员函数的实现对其他类的成员来说都是隐蔽的。
2011-7-18 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;//顺序栈的最大容量
}
2011-7-18 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,然后按此地址进栈
}
2011-7-18 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];//返回栈顶元素，注意：栈顶指针不变
}
2011-7-18 6
4.1.3 链栈 —— 利用链式存贮结构实现的栈
与顺序表一样，顺序栈的最大尺寸（ maxSize）也难以确定，太
小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域，
宜采用链栈。
链栈的结构如下图所示。与单链表相似，但不设头结点，第一
个结点即为栈顶。插入（入栈）与删除（出栈）操作均只能在表头
进行。
当 top = NULL 时，表示空栈
… ^top
栈顶元素 栈底元素
2011-7-18 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
链栈结点结构
2011-7-18 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; //栈顶指针
}
2011-7-18 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)
2011-7-18 10
比较与思考：
（ 1）比较顺序栈与链栈的类定义
两者的类名相同，均为 Stack
两者成员函数的名、参数、返回类型与规格说明均相同，但
内部的实现有别
假定某大型软件系统原来使用顺序栈，因经常上溢，欲改用链
栈，请问哪些部分需要改动？
2011-7-18 11
栈应用举例 —— 迷宫问题
迷宫问题：求迷宫中从入口点到出口点所有可能的简单路径
迷宫模型：
入口
(i,j)
出口
墙
通道
2011-7-18 12
所谓的简单路径是指：在求出的任何一条路径上，不能重现某
一通道块，否则总有任意多条路径
迷宫问题是许多实际问题的抽象，求解这类问题时，没有现成
的数学公式可以套用，只能采用系统化的试探方法。
下面规定：
通道用空格,, 表示
墙壁用, #, 表示
足迹用, 0, 表示
从入口点到当前立足点间，具有足迹标志的相连的通道块
构成的简单路径叫当前路径
将迷宫模型用二维字符型数组表示：
char maze[n+1][n+1];
并假定入口为 maze[0][0],出口为 maze[n][n]
考虑一般情况，设 maze[ i ][ j ] 为当前立足点，并纳入当前路径
（即印上足迹标志, 0, ），则从当前立足点继续试探的算法如下：
2011-7-18 13
if maze[ i ][ j ] 是出口
then 打印刚找到的一条简单路径，并回溯一步；
else if 东面的是通道块
then 前进一步
else if 南面的是通道块
then 前进一步
else if 西面的是通道块
then 前进一步
else if 北面的是通道块
then 前进一步
else 回溯一步( i,j ) 东
南
西
北
2011-7-18 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
2011-7-18 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; };
数据的组织方法设计：
考察上述用试探法走迷宫的过程：
前进一步时，需要保存原立足点的信息；
回溯一步时，需要取出最近的原立足点的信息，并且遵循
后保存的先取出的原则，即“后进先出”的原则，因此可以用
栈
来记录立足点的信息。
迷宫问题的算法框架：
2011-7-18 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’;}
}
}
2011-7-18 17
作业：
完善迷宫问题解决算法（迷宫数组的输入 inputmaze() 算法、
简单路径的输出 printmaze() 算法等）
编写软件并上机实习
要求 11 月 6 日前完成
2011-7-18 18
4.3 队列
定义：队列是限制插入操作只能在一端进行，而删除操作只能在另
一端进行的线性表，并按先进向出（ FIFO）的原则进行操作。
在一个队列中，能进行删除的一端称为队首（ front），能进行
插入操作的一端称为队尾（ rear）。
出列 入列
队首（ front） 队尾（ rear）
与栈类似，队列的封闭性也非常好
栈能对输入序列部分或全局起求逆作用
队列对输入序列起缓冲作用，队列的应用非常广泛
e0 e1 … en-2 en-1
2011-7-18 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; //判队满操作
}
2011-7-18 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
2011-7-18 21
循环队列：逆时针运行示意图
Queue
0
1
2
maxSize-1
maxSize-2
front
队首指针
rear
队尾指针
规定：
队空,front==rear
队满,front==(rear+1) % maxSize
队尾元素：
elements[rear]
队首元素：
elements [ (front+1) % maxSize ]
@ @ @ @
2011-7-18 22
循环队列：满队列示意图
Queue
0
1
2
maxSize-1
maxSize-2
front 队首指针
rear 队尾指针front==(rear+1) % maxSize
本图满足上述队满条件。
由图可知：队满时队首指针所指
的单元不能利用，此时再入列会
使队列变成空队列 ( front==rear )
队尾元素 elements[rear]
队首元素
@ @ @ @
@
@
@
@ @
@
@
@
2011-7-18 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 ;
}
2011-7-18 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 ];//返回出列的队首元素
}
2011-7-18 25
4.3.3 链队列 —— 利用链式存贮结构实现的队列
与顺序表一样，循环队列的最大尺寸（ maxSize）也难以确定，
太小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领
域，宜采用链队列。
链队列的结构如下图所示。与单链表相似，但不设头结点，第
一个结点即为队首。最后一个结点为队尾。插入（入列）操作只能
在队尾进行，删除（出列）操作只能在队首进行。
当 front=rear = NULL 时，表示空队列
… ^front
队首指针
队首 队尾
rear
队尾指针
2011-7-18 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;//队首与队尾指针
};
2011-7-18 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;//为了与循环队列一致而设，对链队列意义不大
比较循环队列的类定义可知：链队列的成员函数的名、返回类型和参数
表与循环队列的完全一样，这样安排的好处是，当一个大型软件原来使用循
环队列时经常发生溢出，此时改用链队列的话只需将原来循环队列的类定义
及其成员函数定义改为链队列的类定义和成员函数定义即可，无需更改软件
的其他地方。
2011-7-18 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 )
2011-7-18 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
2011-7-18 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)
2011-7-18 31
4.5 事件驱动模拟（ Event-Driven Simulation ）
模拟目的：
（ 1）计算银行顾客的平均（最大）等待时间
（ 2）计算银行出纳员的工作繁忙程度
（ 3）计算银行顾客队列的最大长度
出纳员服务原则：
（ 1）某一时刻只能接待一位顾客
（ 2）若本窗口还有顾客则应立刻服务
顾客活动原则：
（ 1）顾客达到时间为 ArrivalTime（随机数）
（ 2）顾客需要服务的时间为 ServiceTime（随机数）
（ 3）顾客选择最短的队列排队
（ 4）顾客的等待时间（从进门到轮到服务）为 WaitTime
（ 5）银行上班时间到后顾客才能进门，下班时间到时顾客
不能进门
2011-7-18 32
仿真模型：
窗口队列 服务窗口
顾客选择排队
顾客流（队列）
…… ……
2011-7-18 33
事件分析：
顾客进门事件触发下列操作：
（ 1）从顾客流队列中出列进门事件
（ 2）从各窗口队列中选择一最短队列
（ 3）计算顾客需要等待的时间
（ 4）将该顾客入列到所选的最短窗口队列中
出纳员对当前顾客服务完毕事件触发下列操作：
（ 1）累计本窗口的服务时间
（ 2）累计本窗口顾客的等待时间
（ 3）记录本窗口顾客的最大等待时间
（ 4）记录本窗口的最大队列长度
（ 5）累计本窗口服务的顾客总数
（ 6）将当前顾客出列
2011-7-18 34
数据结构设计：
（ 1）顾客信息的表示 —— 可将其定义为一结构 Event
进门时间（随机数） ArrivalTime —— 事件
进门序号（顾客号） CustomerID —— 用于统计顾客总数
要求服务的时间（随机数） ServiceTime
需要等待的时间（计算数） WaitTime
（ 2）窗口信息的表示 —— 将其定义为一结构 TellerStatus
本窗口完成当前窗口队列服务的时刻 finishService
本窗口已经服务的顾客总数 CustomerCount
本窗口的累计顾客等待时间 totalCustomerWait
本窗口的最大顾客等待时间 maxCustomerWait
本窗口的最大队列长度 maxQlength
本窗口的累计服务时间 totalService
（ 3）数据的组织方法 —— 采用队列
将未进门的顾客按将要进门的先后顺序入列到顾客流队列中
将已进门的顾客（进门事件）入列到最短窗口队列中
2011-7-18 35
仿真算法思路：
（ 1）利用随机数发生器预先计算一天中达到银行的所有
顾客，并将他们入列到顾客流队列 CustomerFlow 中。
该功能由下述的 CreateCustomerFlow( ) 函数实现：
Queue<Event> CustomerFlow;//定义顾客流队列
void CreateCustomerFlow( )//创建顾客流队列
{ Event e= GetAEvent( );//获取一事件（使用随机数发生器）
CustomerFlow.EnQueue( e );//将事件入列到顾客流队列中
}//上述的每一事件代表一个顾客
（ 2）用一虚拟时钟 VirtualTimer 来模拟前述进门事件和
服务完毕事件的发生。此处的虚拟时钟是一查询循环，
每循环一次代表走过一个时间单位，用查询模拟随机的
中断请求，从而实现用顺序执行模拟并发执行过程。该
功能由下页的 RunSimulation( ) 函数实现。
2011-7-18 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 有一服务完毕事件并作相应处理
}
}
}
2011-7-18 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 ;
}
}
2011-7-18 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
2011-7-18 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++;//累计本窗口的顾客数
}
2011-7-18 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);//输出
}
2011-7-18 41
主程序
#include<iostream.h>
#include<random.h>
#include<queue.h>
#include<simulation.h>
int main( )
{
inputBasicData( );//输入基本数据
CreatCustomerFlow( );//创建顾客流队列
RunSimulation( );//运行
printResult( );//计算并输出结果
}
2011-7-18 42
2011-7-18 43
2011-7-18 44
2011-7-18 45
2011-7-18 46
2011-7-18 47
2011-7-18 48
2011-7-18 49
2011-7-18 50
2011-7-18 51
2011-7-18 52
2011-7-18 53
2011-7-18 54
2011-7-18 55
2011-7-18 56
2011-7-18 57
2011-7-18 58
2011-7-18 59
2011-7-18 60
2011-7-18 61
2011-7-18 62
2011-7-18 63
2011-7-18 64
2011-7-18 65
2011-7-18 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
栈底
2011-7-18 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;}
栈的封闭性及其抽象数据类型：
在一个栈中，出入口处称为栈顶，栈内最深处称为栈底。除
了栈顶元素外，其他元素不会被改变，因而栈的封闭性非常好，
使用起来非常安全。另外，在下面的栈的类定义中，体现了栈的
抽象数据类型，在此定义中，所有栈的成员函数都是共有的，其
他类的成员函数都可以使用这些函数，但是，栈的存储表示和成
员函数的实现对其他类的成员来说都是隐蔽的。
2011-7-18 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;//顺序栈的最大容量
}
2011-7-18 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,然后按此地址进栈
}
2011-7-18 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];//返回栈顶元素，注意：栈顶指针不变
}
2011-7-18 6
4.1.3 链栈 —— 利用链式存贮结构实现的栈
与顺序表一样，顺序栈的最大尺寸（ maxSize）也难以确定，太
小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域，
宜采用链栈。
链栈的结构如下图所示。与单链表相似，但不设头结点，第一
个结点即为栈顶。插入（入栈）与删除（出栈）操作均只能在表头
进行。
当 top = NULL 时，表示空栈
… ^top
栈顶元素 栈底元素
2011-7-18 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
链栈结点结构
2011-7-18 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; //栈顶指针
}
2011-7-18 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)
2011-7-18 10
比较与思考：
（ 1）比较顺序栈与链栈的类定义
两者的类名相同，均为 Stack
两者成员函数的名、参数、返回类型与规格说明均相同，但
内部的实现有别
假定某大型软件系统原来使用顺序栈，因经常上溢，欲改用链
栈，请问哪些部分需要改动？
2011-7-18 11
栈应用举例 —— 迷宫问题
迷宫问题：求迷宫中从入口点到出口点所有可能的简单路径
迷宫模型：
入口
(i,j)
出口
墙
通道
2011-7-18 12
所谓的简单路径是指：在求出的任何一条路径上，不能重现某
一通道块，否则总有任意多条路径
迷宫问题是许多实际问题的抽象，求解这类问题时，没有现成
的数学公式可以套用，只能采用系统化的试探方法。
下面规定：
通道用空格,, 表示
墙壁用, #, 表示
足迹用, 0, 表示
从入口点到当前立足点间，具有足迹标志的相连的通道块
构成的简单路径叫当前路径
将迷宫模型用二维字符型数组表示：
char maze[n+1][n+1];
并假定入口为 maze[0][0],出口为 maze[n][n]
考虑一般情况，设 maze[ i ][ j ] 为当前立足点，并纳入当前路径
（即印上足迹标志, 0, ），则从当前立足点继续试探的算法如下：
2011-7-18 13
if maze[ i ][ j ] 是出口
then 打印刚找到的一条简单路径，并回溯一步；
else if 东面的是通道块
then 前进一步
else if 南面的是通道块
then 前进一步
else if 西面的是通道块
then 前进一步
else if 北面的是通道块
then 前进一步
else 回溯一步( i,j ) 东
南
西
北
2011-7-18 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
2011-7-18 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; };
数据的组织方法设计：
考察上述用试探法走迷宫的过程：
前进一步时，需要保存原立足点的信息；
回溯一步时，需要取出最近的原立足点的信息，并且遵循
后保存的先取出的原则，即“后进先出”的原则，因此可以用
栈
来记录立足点的信息。
迷宫问题的算法框架：
2011-7-18 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’;}
}
}
2011-7-18 17
作业：
完善迷宫问题解决算法（迷宫数组的输入 inputmaze() 算法、
简单路径的输出 printmaze() 算法等）
编写软件并上机实习
要求 11 月 6 日前完成
2011-7-18 18
4.3 队列
定义：队列是限制插入操作只能在一端进行，而删除操作只能在另
一端进行的线性表，并按先进向出（ FIFO）的原则进行操作。
在一个队列中，能进行删除的一端称为队首（ front），能进行
插入操作的一端称为队尾（ rear）。
出列 入列
队首（ front） 队尾（ rear）
与栈类似，队列的封闭性也非常好
栈能对输入序列部分或全局起求逆作用
队列对输入序列起缓冲作用，队列的应用非常广泛
e0 e1 … en-2 en-1
2011-7-18 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; //判队满操作
}
2011-7-18 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
2011-7-18 21
循环队列：逆时针运行示意图
Queue
0
1
2
maxSize-1
maxSize-2
front
队首指针
rear
队尾指针
规定：
队空,front==rear
队满,front==(rear+1) % maxSize
队尾元素：
elements[rear]
队首元素：
elements [ (front+1) % maxSize ]
@ @ @ @
2011-7-18 22
循环队列：满队列示意图
Queue
0
1
2
maxSize-1
maxSize-2
front 队首指针
rear 队尾指针front==(rear+1) % maxSize
本图满足上述队满条件。
由图可知：队满时队首指针所指
的单元不能利用，此时再入列会
使队列变成空队列 ( front==rear )
队尾元素 elements[rear]
队首元素
@ @ @ @
@
@
@
@ @
@
@
@
2011-7-18 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 ;
}
2011-7-18 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 ];//返回出列的队首元素
}
2011-7-18 25
4.3.3 链队列 —— 利用链式存贮结构实现的队列
与顺序表一样，循环队列的最大尺寸（ maxSize）也难以确定，
太小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领
域，宜采用链队列。
链队列的结构如下图所示。与单链表相似，但不设头结点，第
一个结点即为队首。最后一个结点为队尾。插入（入列）操作只能
在队尾进行，删除（出列）操作只能在队首进行。
当 front=rear = NULL 时，表示空队列
… ^front
队首指针
队首 队尾
rear
队尾指针
2011-7-18 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;//队首与队尾指针
};
2011-7-18 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;//为了与循环队列一致而设，对链队列意义不大
比较循环队列的类定义可知：链队列的成员函数的名、返回类型和参数
表与循环队列的完全一样，这样安排的好处是，当一个大型软件原来使用循
环队列时经常发生溢出，此时改用链队列的话只需将原来循环队列的类定义
及其成员函数定义改为链队列的类定义和成员函数定义即可，无需更改软件
的其他地方。
2011-7-18 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 )
2011-7-18 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
2011-7-18 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)
2011-7-18 31
4.5 事件驱动模拟（ Event-Driven Simulation ）
模拟目的：
（ 1）计算银行顾客的平均（最大）等待时间
（ 2）计算银行出纳员的工作繁忙程度
（ 3）计算银行顾客队列的最大长度
出纳员服务原则：
（ 1）某一时刻只能接待一位顾客
（ 2）若本窗口还有顾客则应立刻服务
顾客活动原则：
（ 1）顾客达到时间为 ArrivalTime（随机数）
（ 2）顾客需要服务的时间为 ServiceTime（随机数）
（ 3）顾客选择最短的队列排队
（ 4）顾客的等待时间（从进门到轮到服务）为 WaitTime
（ 5）银行上班时间到后顾客才能进门，下班时间到时顾客
不能进门
2011-7-18 32
仿真模型：
窗口队列 服务窗口
顾客选择排队
顾客流（队列）
…… ……
2011-7-18 33
事件分析：
顾客进门事件触发下列操作：
（ 1）从顾客流队列中出列进门事件
（ 2）从各窗口队列中选择一最短队列
（ 3）计算顾客需要等待的时间
（ 4）将该顾客入列到所选的最短窗口队列中
出纳员对当前顾客服务完毕事件触发下列操作：
（ 1）累计本窗口的服务时间
（ 2）累计本窗口顾客的等待时间
（ 3）记录本窗口顾客的最大等待时间
（ 4）记录本窗口的最大队列长度
（ 5）累计本窗口服务的顾客总数
（ 6）将当前顾客出列
2011-7-18 34
数据结构设计：
（ 1）顾客信息的表示 —— 可将其定义为一结构 Event
进门时间（随机数） ArrivalTime —— 事件
进门序号（顾客号） CustomerID —— 用于统计顾客总数
要求服务的时间（随机数） ServiceTime
需要等待的时间（计算数） WaitTime
（ 2）窗口信息的表示 —— 将其定义为一结构 TellerStatus
本窗口完成当前窗口队列服务的时刻 finishService
本窗口已经服务的顾客总数 CustomerCount
本窗口的累计顾客等待时间 totalCustomerWait
本窗口的最大顾客等待时间 maxCustomerWait
本窗口的最大队列长度 maxQlength
本窗口的累计服务时间 totalService
（ 3）数据的组织方法 —— 采用队列
将未进门的顾客按将要进门的先后顺序入列到顾客流队列中
将已进门的顾客（进门事件）入列到最短窗口队列中
2011-7-18 35
仿真算法思路：
（ 1）利用随机数发生器预先计算一天中达到银行的所有
顾客，并将他们入列到顾客流队列 CustomerFlow 中。
该功能由下述的 CreateCustomerFlow( ) 函数实现：
Queue<Event> CustomerFlow;//定义顾客流队列
void CreateCustomerFlow( )//创建顾客流队列
{ Event e= GetAEvent( );//获取一事件（使用随机数发生器）
CustomerFlow.EnQueue( e );//将事件入列到顾客流队列中
}//上述的每一事件代表一个顾客
（ 2）用一虚拟时钟 VirtualTimer 来模拟前述进门事件和
服务完毕事件的发生。此处的虚拟时钟是一查询循环，
每循环一次代表走过一个时间单位，用查询模拟随机的
中断请求，从而实现用顺序执行模拟并发执行过程。该
功能由下页的 RunSimulation( ) 函数实现。
2011-7-18 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 有一服务完毕事件并作相应处理
}
}
}
2011-7-18 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 ;
}
}
2011-7-18 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
2011-7-18 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++;//累计本窗口的顾客数
}
2011-7-18 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);//输出
}
2011-7-18 41
主程序
#include<iostream.h>
#include<random.h>
#include<queue.h>
#include<simulation.h>
int main( )
{
inputBasicData( );//输入基本数据
CreatCustomerFlow( );//创建顾客流队列
RunSimulation( );//运行
printResult( );//计算并输出结果
}
2011-7-18 42
2011-7-18 43
2011-7-18 44
2011-7-18 45
2011-7-18 46
2011-7-18 47
2011-7-18 48
2011-7-18 49
2011-7-18 50
2011-7-18 51
2011-7-18 52
2011-7-18 53
2011-7-18 54
2011-7-18 55
2011-7-18 56
2011-7-18 57
2011-7-18 58
2011-7-18 59
2011-7-18 60
2011-7-18 61
2011-7-18 62
2011-7-18 63
2011-7-18 64
2011-7-18 65
2011-7-18 66
