队列之c++实现

c++ primer（第5版的一个例子）

queue_my.h

主要定义客户类和队列类

#ifndef QUEUE_H_
#define QUEUE_H_

/************************************************************************/
/* description：Queue class 的实现（模拟提款机排队）

date： 2012.12.26

author： anderson */
/************************************************************************/
//customer class
class Customer
{
private:
long arrive; //客户的到达时间
int processtime; //客户的操作时间
public:
Customer(){arrive = processtime = 0;}
void set(long when);
long when()const {return arrive;}
int ptime()const {return processtime;}
};

typedef Customer Item;

//queue class
class Queue
{
private:
struct Node{Item item;struct Node* next;};
enum {Q_SIZE = 10};

Node* front; //队首
Node* rear; //队尾
int items; //队列中的元素
const int qsize; //队列的最大容量

Queue(const Queue& q):qsize(0){}
Queue& operator=(const Queue& q){return *this;}

public:
Queue(int qs = Q_SIZE);
~Queue();

bool isempty()const;
bool isfull()const;

int queuecout()const;

bool enqueue(const Item& item);
bool dequeue(Item& item);
};
#endif

queue_my.cpp

#include "queue_my.h"
#include "stdlib.h"

Queue::Queue(int qs):qsize(qs)
{
front = rear = NULL;
items = 0;
}

Queue::~Queue()
{
Node* temp;
while (front != NULL)
{
temp = front;
front = front->next;
delete temp;
}
}

bool Queue::isempty()const
{
return items == 0;
}

bool Queue::isfull()const
{
return items == qsize;
}

int Queue::queuecout()const
{
return items;
}

bool Queue::enqueue(const Item& item)
{
if(isfull())
return false;

Node* add = new Node;
if(add == NULL)
return false;
add->item = item;
add->next = NULL;
items++;

if(front == NULL)
front = add;
else
rear->next = add;

rear = add;

return true;
}

bool Queue::dequeue(Item& item)
{
if(front ==NULL)
return false;
item = front->item;
items--;

Node* temp = front;
front = front->next;
delete temp;

if(items == 0)
rear =NULL;
return true;
}

/***************************************************************/

void Customer::set(long when)
{
processtime = rand()%3 + 1;
arrive = when;
}

queue_my_test.cpp

#include "iostream.h"
#include "time.h"
#include "stdlib.h"
#include "queue_my.h"

const int MIN_PER_HR = 60;

bool newcustomer(double x)
{
return (rand() * x /RAND_MAX < 1);
}

int main()
{
srand(time(0));

cout<<"Case study: bank of heather automatic teller\n";
cout<<"enter maximum size of queue:";
int qs;
cin>>qs;

Queue line(qs);

cout<<"enter the number of simulation hours:";
int hours;
cin>>hours;

long cyclelimit = MIN_PER_HR * hours;

cout<<"enter the average number of customers per hour:";
double perhour;
cin>>perhour;

double min_per_cust;
min_per_cust = MIN_PER_HR / perhour;

Item temp;
long turnaways = 0;
long customers = 0;
long served = 0;
long sum_line = 0;
int wait_time = 0;
long line_wait = 0;

for (int cycle = 0; cycle < cyclelimit; cycle ++)
{
if (newcustomer(min_per_cust)) //have new customer
{
if(line.isfull())
turnaways ++;
else
{
customers ++;
temp.set(cycle);
line.enqueue(temp);
}
}
if (wait_time <= 0 && !line.isempty())
{
line.dequeue(temp);
wait_time = temp.ptime();
line_wait += cycle - temp.when();
served ++;
}
if(wait_time > 0)
wait_time --;
sum_line += line.queuecout();
}

if (customers > 0)
{
cout<<"customers accepted:"<<customers<<endl;
cout<<" customers served:"<<served<<endl;
cout<<" turnaways:"<<turnaways<<endl;
cout<<"average queue size:";
// cout.precision(2);
// cout.setf(fixed,floatfield);
// cout.setf(showpoint);

cout<<(double)sum_line / cyclelimit << endl;
cout << " average wait time:" << (double)line_wait / served << " minutes\n";
}
else
cout << "no customers!\n";
cout << "done!\n";
return 0;
}