c++第十二章续（队列结构类模拟）

队列类

设计类，需要开发公有接口和私有实现

 Queue类接口

公有接口：

默认初始化，和可以用显式初始化覆盖默认值

 Queue类的实现

如何表示队列数据：

一种方法是使用new动态分配一个数组，它包含所需的元素数。不过，对于队列操作而言，数组并不太合适。例如，删除数组的第一个元素后，需要将余下的所有元素向前移动一位:否则需要作一些更费力的工作，

如将数组视为是循环的。不过链表能够很好地满足队列的要求。链表由节点序列构成。每一个节点中都包含要保存到链表中的信息以及个指向下一个节点的指针。对于这里的队列来说，数据部分都是一个Item 类型的值，因此可以使用下面

单项链表

跟踪链表

由于队列总是将新项目添加到队尾，因此包含一个指向最后一个节点的数据成员将非常方便。

上述声明使用了 C++的一项新特性:在类中嵌套结构或类声明。通过将Node声明放在 Queue 类中，可以使其作用域为整个类。也就是说，Node是这样一种类型:可以使用它来声明类成员，也可以将它作为类方法中的类型名称，但只能在类中使用。

类方法

类构造函数

错误的类构造函数

问题在于 qsize 是常量，所以可以对它进行初始化，但不能给它赋值。

对于cons数据成员，必须在执行到构造函数体之前，即创建对象时进行初始化。

C++提供了一种特殊的句法来完成上述工作，它叫做成员初始化列表(member initializer list)。成员初始化列表由逗号分隔的初始化列表组成前面带冒号)。它位于参数列表的右括号之后、函数体左括号之前。

如果数据成员的名称为mdata，并需要将它初始化为 val，则初始化器为 mdata(val)。使用这种表示法，可以这样编写Queue 的构造函数:

构造函数可以改成

只有构造函数可以使用初始化列表句法。

另外，被声明为引用的类成员，也必须使用该句法

这是因为引用与 const 数据类似,只能在被创建时进行初始化。

入队方法

出队方法

 

 显式析构函数

删除所有节点

Customer类（模拟客户）

设计客户类。通常，ATM 客户有很多属性，例如姓名、账户和账户结余。不过，这里的模拟需要使用的惟--个属性是客户何时进入队列以及客户交易所需的时间。当模拟生成新客户时，程序将创建一个新的客户对象，并在其中存储客户的到达时间以及一个随机生成的交易时间。当客户到达队首时程序将记录此时的时间，并将其与进入队列的时间相减，得到客户的等候时间。下面的代码演示了如何定义和实现 Customer类:

头文件

queue.h

#ifndef QUEUE_H_
#define QUEUE_H_
class Customer
{
private:long arrive;     // arrival time for customerint processtime; // processing time for customer
public:Customer() { arrive = processtime = 0; }void set(long when);long when() const { return arrive; }int ptime() const{return processtime;}
};typedef Customer Item;class Queue
{
private:// class scope definitions//  Node is a nested structure definition local to this classstruct Node{Item item;struct Node *next;};enum{Q_SIZE = 10};// private class membersNode *front; // pointer to front of QueueNode *rear;  // pointer to rear of Queueint items;// current number of items in Queueconst int qsize; // maximum number of items in Queue// preemptive definitions to prevent public copyingQueue(const Queue &g) : qsize(0) {}Queue &operator=(const Queue &q) { return *this; }public:Queue(int qs = Q_SIZE); // create queue with a gs limit~Queue();bool isempty() const;bool isfull() const;int queuecount() const;bool enqueue(const Item &item); // add item to endbool dequeue(Item &item);// remove item from front
};#endif

方法文件

queue.cpp

#include "queue.h"
#include <cstdlib>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::queuecount() const
{return items;
}bool Queue::enqueue(const Item &item)
{if (isfull())return false;Node *add = new Node; // create nodeif (add == NULL)return false;add->item = item;add->next = NULL;items++;if (front == NULL)front = add;elserear->next = add; // else place at rearear = add;return true;// have rear point to new node
}bool Queue::dequeue(Item &item)
{if (front == NULL)return false;item = front->item; // set item to first item in queueitems--;Node *temp = front;front = front->next;delete temp;if (items == 0)rear = NULL;return true;
}// Customer methods
void Customer::set(long when)
{processtime = std::rand() % 3 + 1;arrive = when;
}

模拟

程序需要完成下面的工作

个有趣的问题是，程序如何确定是否有新的客户到来。假设平均每小时有10名客户到达，则相当于每6分钟有一名客户。程序将计算这个值，并将它保存在min_per_cust变量中。不过，刚好每6分钟来名客户不太现实，我们真正(至少在大部分时间内)希望的是一个更随机的过程--平均每6分钟来名客户。程序将使用下面的函数来确定是否在循环期间

工作原理

程序文件

bank.cpp

#include <iostream>
#include <cstdlib>
#include <ctime>
#include "queue.h"
const int MIN_PER_HR = 60;bool newcustomer(double x);int main()
{using std::cin;using std::cout;using std::endl;using std::ios_base;std::srand(std::time(0));// random initializing ofrand()cout << "Case Study:Bank of Heather Automatic Teller\n";cout << "Enter maximum size of queue:";int qs;cin >> qs;Queue line(qs);// line queue holds up to qs peoplecout << "Enter the number of simulation hours: ";int hours;                            // hours of simulationcin >> hours;                         // simulation will run l cycle per minutelong cyclelimit = MIN_PER_HR * hours; // #of cyclescout << "Enter the average:number of customers per hour: ";double perhour; // average #of arrival per hourcin >> perhour;double min_per_cust; // average time between arrivalsmin_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 newcomer{if (line.isfull())turnaways++;else{customers++;temp.set(cycle);    // cycle = time of arrivalline.enqueue(temp); // add newcomer toline}}if (wait_time <= 0 && !line.isempty()){line.dequeue(temp);       // attend next customerwait_time = temp.ptime(); // for wait time minutesline_wait += cycle - temp.when();served++;}if (wait_time > 0)wait_time--;sum_line += line.queuecount();}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(ios_base::fixed, ios_base::floatfield);cout.setf(ios_base::showpoint);cout << (double)sum_line / cyclelimit << endl;cout << "average wait time: "<< (double)line_wait / served << "minutes\n";}elsecout << "No customers!\n";cout << "Done!\n";return 0;
}bool newcustomer(double x)
{return (std::rand() * x / RAND_MAX < 1);
}