Chapter 3 QUEUES
1,Specifications for Queues
2,Implementation of Queues
3,Contiguous Queues in C++
4,Demonstration and Testing
5,Application,Airport
Simulation
6,Pointers and Pitfalls
A Queue is a data
structure in which
insertions take place
at one end and
deletions take place
at the opposite end.
3.1 Specifications for
Queue
Characteristic:
First In First Out
2
3
4
1
1
1
2
2
front
rear
Queue,,Queue( );
Post,The Queue has been created and is
initialized
to be empty.
Error_code Queue,,append(const Queue
entry &x);
Post,If there is space,x is added to the Queue
as its
rear.Otherwise an Error code of overflow
is
Error_code Queue,,serve( );
Post,If the Queue is not empty,the front of
the
Queue has been removed,Otherwise an
Error
code of underflow is returned.Error_code Queue::retrieve(Queue entry &x)
const;
Post,If the Queue is not empty,the front of the
Queue has been recorded as x,
Otherwise an
bool Queue,,empty( ) const;
Post,Return true if the Queue is empty,
otherwise
return false.Extended Queues
class Extended queue,public Queue
{ public,bool full( ) const;
int size( ) const;
void clear( );
Error_code serve and retrieve(Queue entry
&item);
};
Exist what problem?
Circular
Implementatio
n of Queues
Boundary Conditions
3.2 Implementations of Queues
?The physical model,a linear array with
the front always in the first position and all
entries moved up the array whenever the
front is deleted.
?A linear array with two indices always
increasing.
?A circular array with front and rear indices
and one position left vacant.
?A circular array with front and rear indices
and a Boolean flag to indicate fullness (or
emptiness).
?A circular array with front and rear indices
and an integer counter of entries.
?A circular array with front and rear indices
taking special values to indicate emptiness.
3.3 Circular Implementation of Queues in
C++
//顺序循环队列的模板类接口定义以及基本运算的实现代码
#include<iostream.h>
enum Error_code{ success,overflow,underflow,
can_land,can_depart,fail };
const int maxqueue = 10; // small value for testing
template <class Queue_entry> class Queue
{ public:
Queue( );
bool empty( ) const { return count==0; }
Error_code serve( );
Error_code append(const Queue_entry &item);
Error_code retrieve(Queue_entry &item) const;
protected:
int count;
int front,rear;
Queue_entry entry[maxqueue];
friend class Runway;
}; // 结束类 Queue声明
template <class Queue_entry>
Queue<Queue_entry>::Queue( )
// Post,The Queue is initialized to be empty,
{ count=0; rear=maxqueue-1; front=0; }
template <class Queue_entry> Error_code
Queue<Queue_entry>::append(const Queue_entry
&item)
// Post,item is added to the rear of the Queue, If the
Queue is
// full return an overflow and leave the Queue
unchanged.
{ if (count>=maxqueue) return overflow;
count ++;
rear = ((rear+1) == maxqueue)? 0,(rear+1);
entry[rear]=item;
return success;
}
template <class Queue_entry> Error_code
Queue<Queue_entry>::serve( )
// Post,The front of the Queue is removed,If the Queue
is //
// empty return an underflow
{ if (count<=0) return underflow;
count--;
front = ((front+1) == maxqueue)? 0,(front+1);
return success;
}
template <class Queue_entry> Error_code Queue
<Queue_entry>::retrieve(Queue_entry &item)
const
// Post,The front of the Queue retrieved to the
output
// parameteritem, If the Queue is empty
return
// an Error_code of underflow.
{
if(count<=0) return underflow;
item = entry[front];
return success;
}
3.4 Demonstration and Testing
Skip,ask everyone's oneself to
see the book P93
3.5 Application of Queues,
Simulation of an Airport
Simulation is the use of one
system to imitate the behavior of
another system,
A computer simulation is a
program to imitate the behavior of
the system under study.
?The same runway is used for both
landings and takeoffs.
?One plane can land or take off in a unit of
time,but not both.
?A random number of planes arrive in
each time unit.
?A plane waiting to land goes before one
waiting to take off.
?The planes that are waiting are kept in
queues landing and takeoff,both of which
have a strictly limited size.
#include <iostream.h>
#include <time.h>
#include "random.h"
#include "Plane.H"
#include "Runway.H"
void main( ) // Airport simulation program
/* Pre,The user must supply the number of time intervals
the simulation is to run,the expected number of planes
arriving,the expected number of planes departing per time
interval,and the maximum allowed size for runway queues.
Post,The program performs a random simulation of the
airport,showing the status of the runway at each time
interval,and prints out a summary of airport operation at
the conclusion.
Uses,Classes Runway,Plane,Random and functions
run run_idle,initialize, */
{ int end_time; //time to run simulation
int queue_limit; //size of Runway queues
int flight_number = 0;
double arrival_rate,departure_rate;
void initialize(int&,int&,double&,double&);
void run_idle(int);
initialize(end_time,queue_limit,arrival_rate,
departure_rate);
Random variable;
Runway small_airport(queue_limit);
for(int current_time=0; current_time<end_time;
current_time++)
{
int number_arrivals=variable.poisson(arrival_rate);
for(int i=0; i<number_arrivals; i++)
{
Plane current_plane(flight_number++,current_time,
arriving);
if(small_airport.can_land(current_plane)!=success)
current_plane.refuse( );
}
int number_departures = variable.poisson(departure_rate);
for(int j=0; j<number_departures; j++)
{ Plane current_plane(flight_number++,current_time,
departing);
if(small_airport.can_depart(current_plane)!=success)
current_plane.refuse( );
}
Plane moving_plane;
switch(small_airport.activity(current_time,
moving_plane))
{
case land,moving_plane.land(current_time); break;
case flyingoff,moving_plane.fly(current_time); break;
case idle,run_idle(current_time);
}
}
small_airport.shut_down(end_time);
}
The Runway Class Specification
#include "Queue.h"
enum Runway_activity {idle,land,flyingoff};
class Runway
{
public:
Extended_queue<Plane> landing;
Extended_queue<Plane> takeoff;
Runway(int limit);
Error_code can_land(const Plane &current);
Error_code can_depart(const Plane &current);
Runway_activity activity(int time,Plane &moving);
void shut_down(int time) const;
#include "Queue.h"
enum Runway_activity {idle,land,flyingoff};
class Runway
{
public:
Extended_queue<Plane> landing;
Extended_queue<Plane> takeoff;
Runway(int limit);
Error_code can_land(const Plane &current);
Error_code can_depart(const Plane &current);
Runway_activity activity(int time,Plane &moving);
void shut_down(int time) const;
private,
int queue_limit;
int num_land_requests; // number of planes asking to
land
int num_takeoff_requests; // number of planes asking to
take off
int num_landings; // number of planes that have
landed
int num_takeoffs; //number of planes that have taken
off
int num_land_accepted; // number of planes queued to
land
int num_takeoff_accepted; // number of planes queued to
take off
int num_land_refused; // number of landing planes
The Plane Class
Specificationenum Plane_status { null,arriving,departing };
class Plane
{ public,
Plane( );
Plane(int flt,int time,Plane_status status);
void refuse( ) const;
void land(int time) const;
void fly(int time) const;
int started( ) const { return clock_start; }
private:
int flt_num; int clock_start;
Plane_status state;
};
Simulation Initialization
void initialize(int &end_time,int &queue_limit,double
&arrival_rate,double &departure_rate)
/* Pre,The user specifies the number of time units in
the
simulation,the maximal queue sizes permitted,
and the
expected arrival and departure_rates for the
airport.
Post,The program prints instructions and
initializes the
parameter send_time,queue_limit,arrival_rate,
and
departure_rate to the specified values.
Uses,utility function user says yes
cout<<"One plane can land or depart in each unit of
time.\n";
cout<<"Up to what number of planes can be waiting to
land";
cout<<"or take off at any time? "<<flush;
cin>>queue_limit;
cout<<"How many units of time will the simulation run?\n";
cin>>end_time; bool acceptable;
do{ cout<<"Expected number of arrivals per unit
time?"<<flush;
cin>>arrival_rate;
cout<<"Expected number of departures per unit time?
"
cout<< flush; cin>>departure_rate;
if (arrival_rate<0.0 || departure_rate<0.0)
cerr<<,These_rates must be nonnegative," <<
cout<<"One plane can land or depart in each unit of
time.\n";
cout<<"Up to what number of planes can be waiting to
land";
cout<<"or take off at any time? "<<flush;
cin>>queue_limit;
cout<<"How many units of time will the simulation run?\n";
cin>>end_time; bool acceptable;
do{ cout<<"Expected number of arrivals per unit
time?"<<flush;
cin>>arrival_rate;
cout<<"Expected number of departures per unit time?
"
cout<< flush; cin>>departure_rate;
if (arrival_rate<0.0 || departure_rate<0.0)
cerr<<,These_rates must be nonnegative," <<
cerr<<"Safety Warning,This airport will become
saturated";
}while(!acceptable);
} Runway Methods
Runway::Runway(int limit)
/* Post,The Runway data members are initialized to record
no
prior Runway use and to record the limit on queue
sizes,*/
{ queue_limit=limit;
num_land_requests=num_takeoff_requests=0;
num_landings=num_takeoffs=0;
num_land_refused=num_takeoff_refused=0;
num_land_accepted = num_takeoff_accepted=0;
land_wait=takeoff_wait=idle_time=0;
}
Error_code Runway::can_land(const Plane &current)
/* Post,If possible,the Plane current is added to the
landing
Queue ; otherwise,an Error_code of overflow is
returned,
The Runway statistics are updated.
Uses,class Extended queue, */
{ Error_code result;
if(landing.size()<queue_limit)
result=landing.append(current);
else result=fail;
num_land_requests++;
if(result!=success) num_land_refused++;
else num_land_accepted++;
return result;
Error_code Runway::can_depart(const Plane &current)
/* Post,If possible,the Plane current is added to the
departing
Queue ; otherwise,an Error_code of overflow is
returned,
The Runway statistics are updated.
Uses,class Extended queue, */
{ Error_code result;
if(takeoff.size()<queue_limit)
result=takeoff.append(current);
else result=fail;
num_takeoff_requests++;
if(result!=success) num_takeoff_refused++;
else num_takeoff_accepted++;
return result;
Error_code Runway::activity(int time,Plane &moving)
/* Post,If the landing Queue has entries,its front Plane is
copied
to the parameter moving and a result land is returned,
Otherwise,f the takeoff Queue has entries,its front
Plane is
copied to the parameter moving and a result takeoff is
returned,Otherwise,idle is returned,The Runway
statistics
are updated.
Uses,class Extended queue, */
{ Runway_activity in_progress;
if (!landing.empty( ))
{ landing.retrieve(moving);
land_wait += time-moving.started( );
else if (!takeoff.empty( ))
{ takeoff.retrieve(moving);
takeoff_wait+=time-moving.started( );
num_takeoffs++; in_progress = flyingoff;
takeoff.serve( );
}
else{ idle_time++;
in_progress = idle;
}
return in_progress;
}
Plane Initialization
Plane::Plane(int flt,int time,Plane_status status)
/* Post,The Plane data members flt num,clock_start,and
state
are set to the values of the parameters flt,time and
status,
respectively,*/
{ flt_num=flt;
clock_start = time;
state = status;
cout<<" Plane number "<<flt<<" ready to ";
if (status==arriving)
cout<<"land."<<endl;
else
cout<<"take off."<<endl;
}
Plane::Plane( )
/* Post,The Plane data membersflt num,clock_start,state
are set to illegal default
values,*/
{
flt_num=-1;
clock_start =-1;
state=null;
}
Plane Methods
void Plane::refuse( ) const
/* Post,Processes a Plane wanting to use Runway,
when the Queue is full,*/
{ cout<<" Plane number "<<flt_num;
if (state==arriving)
cout <<" directed to another airport"<<endl;
else
cout<<" told to try to takeoff again later"<<endl;
}
void Plane::land(int time) const
/* Post,Processes a Plane that is landing at the specified
time,*/
{ int wait = time-clock_start;
cout<<time<<",Plane number "<<flt_num << " landed
after ";
cout<<wait<<" time unit"<<((wait==1)? "", "s");
cout<<" in the takeoff queue." << endl;
}
void Plane::fly(int time) const
/* Post,Process aPlane that is taking off at the speci
ed time,*/
{ int wait = time-clock_start;
cout<<time << ",Plane number " << flt_num ;
cout << " took off after ";
cout<<wait<<" time unit"<< ((wait == 1)? "", "s");
cout<<" in the takeoff queue."<<endl;
}
Finishing the Simulation
void Runway::shut_down(int time) const
/* Post,Runway usage statistics are summarized and
printed,*/
{
cout<<"\n\nSimulation has concluded after "<<time;
cout<<" time units.\n Total number of planes processed ";
cout<<(num_land_requests +
num_takeoff_requests)<<endl;
cout<<"Total number of planes asking to land ";
cout <<num_land_requests<<endl;
cout<<"Total number of planes asking to take off ";
cout <<num_takeoff_requests<<endl;
cout<<"Total number of planes accepted for landing ";
cout <<num_land_accepted<<endl;
cout<<"Total number of planes accepted for takeoff ";
cout<<num_takeoff_accepted<<endl;
cout<<"Total number of planes refused for landing ";
cout<<num_land_refused<<endl;
cout<< "Total number of planes refused for takeoff ";
cout << num_takeoff_refused<<endl;
cout<< "Total number of planes that landed ";
cout<<num_landings<<endl;
cout<< "Total number of planes that took off ";
cout<<num_takeoffs<<endl;
cout<< "Total number of planes left in landing queue ";
cout<<landing.size( )<<endl;
cout<< "Total number of planes left in takeoff queue ";
cout<<takeoff.size( )<<endl;
cout<< "Percentage of time runway idle ";
cout<<(100.0*(float)idle_time)/((float)time)<<"%"<<endl;
cout<<"Average wait in landing queue ";
cout<<((float)land_wait)/((float)num_landings);
cout<< " time units "<<endl;
cout<< "Average wait in takeoff queue";
cout<<((float) takeoff_wait)/((float) num_takeoffs);
cout<< "time units"<<endl;
cout<< "Average observed rate of planes wanting to land
";
cout<<((float) num_land_requests)/((float)time);
cout<< " per time unit "<<endl;
cout<< "Average observed rate of planes wanting to take
off ";
cout<<((float)num_takeoff_requests)/((float)time);
cout<< " per time unit "<<endl;
}
Pointers and Pitfalls
◆ Before choosing implementations,be sure that
all the data structures and their associated
operations are fully specified on the abstract
level.
◆ In choosing between implementations,
consider the necessary operations on the data
structure.
◆ If every object of class A has all the properties
of an object of class B,implement class A as a
derived class of B.
◆ Consider the requirements of derived classes
when declaring the members of a base class.
◆ Implement is-a relationships between classes
by using public inheritance.
◆ Implement has-a relationships between classes
by layering.
◆ Use Poisson random variables to model
random event occurrences.