(一三三)队列模拟

  1. 云栖社区>
  2. 博客>
  3. 正文

(一三三)队列模拟

零零水 2016-01-30 01:32:00 浏览759
展开阅读全文

所谓队列,大概就是指能够容纳一定数量有序的项目,新的项目被添加到队尾,也可以删除队首的项目。(比如银行排队办业务)

 

队列是先进先出原则(栈是LIFO)。

 

 

 

 

队列的特征有:

①队列存储有序的项目序列;

②队列所能容纳的项目数有一定限制;

③应当能够创建空队列;

④应当能够检查队列是否为空;

⑤应当能够检查队列是否为满;

⑥应当能够在队尾添加项目;

⑦应当能在队首删除项目;

⑧应当能够确认队伍的项目数;

 

 

 

根据队列特征,经过个人思考,创造一个类:

1)需要有计数器,计数器类型为静态变量。——解决⑧

 

2)有静态常量,使用枚举常量或者static const int这样的,用于设置项目数的限制(结合计数器)——解决②

 

3)有两个函数,bool类型,返回空、或者满的判断(使用计数器、静态常量)——解决④和⑤

 

4)一个函数用途添加项目,一个函数用于删除项目,并且,可以返回添加和删除是否成功——解决⑥⑦

 

5)构造函数,可以创建空队列——解决③

 

6)①还不太清楚怎么做。

 

 

书上是这么给的(注释我自己加的):

typedef int Item;	//将Item用作一个类型的别名
class Queue
{
private:
	enum { Q_size = 10 };	//最大值,用于限制队列数量
	//其他私有成员暂时不表
public:
	Queue(int qs = Q_size);	//创造一个用传递的变量qs限制的队列
	~Queue();
	bool isempty()const;	//返回队列是否空的
	bool isfull()const;		//返回队列是否满的
	int queuecout()const;	//计算队列项目数量
	bool enqueue(const Item &item);	//将东西放进队列,并返回放置结果
	bool dequeue(Item &item);	//将东西取出,并返回取出结果
};

 

在这个类,构造函数创建一个空队列。默认情况下,队列最多可存储10个项目,但是可以用显式初始化参数覆盖该默认值。

例如 Queue line_1; 就是10个项目为上限的队列;

而 Queue line_2(20); 是20个项目为上限的队列;

 

另外,关于typedef 定义的Item,将在14章介绍如何使用类模板(所以现在不会

 

 

 

 

思路:

关于①:

因为要存储有序(且有限)的项目序列。

首先要有项目,这里用别名Item代替(可以通过更改别名的来源来更改别名的指向)。

其次,因为要有序,所以应该前后连接,要么内存上是连贯的(且每个占用内存是相等,这个貌似可以采用缓存区。另外,这个假设是我自己想的,不知道可行不,要么前一个项目可以指向后一个项目的地址(这是书上的,因此可以从前一个抵达后一个)。

于是,使用结构,结构有两个成员,第一个是项目(至于项目内部怎么处理,另说),第二个是指针,指针指向下一个项目(如果有的话)。

有结构:

struct Node //node是节点的意思

{

Item item;

struct Node* next; //struct Node表示struct Node的指针,貌似只用Node*next也可以

};

 

因为要指向下一个项目,那么指针类型就需要和下一个项目的类型一致;

而下一个项目也要有指针指向下下个项目,假如项目和指针独立的话,就变成下一个项目有指针,这个项目没指针(因为少个指针,当前项目和下个项目就不一致了),因此,每个项目都应该有个指针,指向下一个项目。

假如指针在项目里,那么调用指针需要使用成员运算符,例如 项目.指针。一方面是麻烦,另一方面,在设置项目的时候就多了一个内容(假如这个项目类型,有其他的也需要使用,就容易出问题)。

因此,用一个结构,指针指向结构,结构包含项目和指针。

 

 

又因为需要有序,且有进有出,那么根据之前写栈的代码,就知道,需要有一个指针,指向进来的地址和出去的地址。因此有结构指针:

Node *front; //表示最前,也就是first in和first out

Node *rear; //表示最后,也就是last int和last out(对目前来说)

 

另外,注意,这段代码需要在结构之后(因为他使用的是结构的指针)。

 

 

 

 

关于②:

需要有上限,于是有静态常量;需要有计数器(类对象内的项目),因此有整型变量:

int items; //变量,用作计数器

enum { Max = 10 }; //静态常量,用作限制。枚举作为静态常量个人感觉更方便一些

 

又考虑到要允许自定义上限,枚举常量的值显然是不能被修改的,因此有必要再设置一个常量(因为非常量的话,可能会被修改,也许有的时候需要修改队列,不过这里为了方便考虑不能被修改):

const int size; //常量,用作对象的项目最大数

 

这个时候,①和②就基本完成了,这也是私有成员的部分,类的数据成员:

private:
enum { Q_size = 10 };	//最大值,用于限制队列数量
struct Node	//node是节点的意思
{
Item item;
Node* next;	//struct Node表示struct Node的指针,貌似只用Node*next也可以
};
Node *front;	//表示最前,也就是first in和first out
Node *rear;	//表示最后,也就是last int和last out(对目前来说)
int items;	//静态变量,用作计数器
enum { Max = 10 };	//静态常量,用作限制。枚举作为静态常量个人感觉更方便一些
const int size;	//常量,用作对象的项目最大数
 

 

关于③:

因为已有项目,于是我们便可以创造空队列。

队列显然是有长度限制的,我们可以根据默认的(如枚举常量Max),最好也能使用自定义的(于是需要传递参数)。

但存在一个问题,假如使用常量(const int size),那么常量的特点是声明并初始化后就不能被修改(如果使用变量就没有那么多问题了)。那么就需要初始化它(但类声明是不分配内存的)。

 

显然不能在创建对象的时候,在函数内部初始化它(因为那个时候类各个数据成员已经被声明了)。

有一个办法可以在创建对象的时候初始化各个数据对象,那就是在参数列表右括号后,函数体大括号前(就是当类对象被调用,限制其数据成员不能被修改的const的位置),使用

(参数列表):私有成员1 (给该成员赋值的参数), 私有成员2 (给该成员赋值的参数)

这样的代码,可以初始化私有成员,或者const常量(但是不能初始化静态变量,因为其被所有对象共享)。注意,只能在构造函数中使用(因为其初始化对象)。

 

例如:

Queue::Queue(int n = Max) :size(n), items(0)	//size为限制,被参数n赋值,计数器初始化为0,
{
rear = front = nullptr;	//表示最前和最后的都是空指针(因为队列内没项目)
}
 


 

关于初始化:

C++11前,需要通过以上方式初始化非静态const数据成员(主要是为了const成员赋值)。这种初始化方式有几点需要注意的:

1)只能用于构造函数

2)必须用这种方法初始化const对象(在C++11前),原因是若是进入函数块内,各个数据成员便已经被声明过了,自然const成员不能被修改;

3)必须用这种格式来初始化引用数据成员(原因在于,引用在初始化时,决定引用的对象,之后,它已经和被引用的对象绑定了,无法再被修改,用赋值运算符其实就是赋值,会影响被引用的对象);

4)数据成员被初始化的顺序,与他们出现在类声明中的顺序相同,与初始化容器中的排列顺序无关(也就是在这里初始化,前后顺序无所谓);

5)不能在构造函数以外使用这种方法。

6)在函数定义后使用

 

另外,成员初始化列表使用的括号方式,也可以用于常规初始化。例如:

int a=1;  和 int a(1); 的效果是一样的

 

 

C++11的类内初始化:

就是在类内声明数据对象时,同时给其一个赋值,作为初始化。

方法是在类内声明数据成员的时候,同时给其一个值作为初始化值,但需要明确,声明类定义的时候,不会为类分配内存,因此,这些值将在构造函数时使用(这也是为什么另一种初始化方式,只能在构造函数中使用的原因)。

 

例如:

class Name
{
	int a = 1;
public:
	Name(int c = 3) :a(2)
	{
		a = c;
	}
	void show() { std::cout << a << std::endl; }
};

 

int a=1是C++11的类内初始化;

:a(2)是构造函数用的括号初始化;

而int c=3是默认参数初始化。

假如在main函数内声明:Name q(4);;则是给默认构造函数添加参数。

 

这四种初始化可以同时存在,并且存在优先级,优先级从高到低依次是:

1)在main函数(或者其他函数内)声明一个类对象,并赋予参数,这种形式的优先级是最高的。例如假如这四种都存在,对象qa的值最终为4

 

2)其次是默认参数。默认参数在未给参数的时候,作为参数使用,因此优先级第二高;

 

3)再次是构造函数参数列表后面的初始化a(2),假如构造函数只有a=1a(2)两种初始化,那么a将等于2

 

4)在其他情况都不存在的时候,a的值为类内初始化的值。

 

思考:

关于这四种初始化的顺序:

根据实际测试,在a=c之前,对象已经被初始化,

以类对象为另一个类成员为例:

class Player
{
	double a = 1.1;
public:
	Player(int m = 1) { a = m;cout << 1 << endl; }
	void operator=(int m) { a = m;cout << 2 << endl; }
	operator double() { return a; }
};

class Name
{
	Player q = 3;
public:
	Name(int c = 3) :q(4)
	{
		q = c;
	}
	void show() { std::cout << q << std::endl; }
};

 

其中,Player类对象,是Name类的数据成员。

Name类对象被创建的时候,Player对象q也随之被创建(且同时使用构造函数/默认构造函数)。涉及到这一步的是3)和4)。而q=c这行代码,调用的是赋值运算符,涉及到的是1)和2)。

也就是说,如果类对象在带有以上4种初始化方式进行初始化时,将涉及到两步——初始化和赋值

 

第一步,是选择3)或者4)中的一个,且3)优先于4)进行初始化。此时调用的是 构造函数

第二步,是选择1)或者2)中的一个,且1)优先于2)进行赋值。此刻调用的是 赋值运算符(如果没有赋值运算符的话,将 调用构造函数创建临时对象 并赋值,然后删除这个临时对象)。

 

 

因此,有了类Queue构造函数:

Queue::Queue(int n = Max) :size(n), items(0)		//size为限制,被参数n赋值,计数器初始化为0,
{
	rear = front = nullptr;	//表示最前和最后的都是空指针(因为队列内没项目)
}

 

关于④和⑤:

④和⑤报告是否是满/空,由于有计数器(变量items),因此很简单。

判断是否为空:

bool Queue::isempty()const
{
	return !items;	//如果是空,则为item==0,加叹号后则为true
}

判断是否为满:

bool Queue::isfull()const
{
	return (items == size);		//如果为满,则items等于size,返回true,否则返回false
}

 

 

 

 

关于⑥和⑦:

⑥是队尾添加,⑦是队首删除。

添加的前提是没满,删除的前提是没空,因此可以用④和⑤的函数,作为条件。

顺便返回添加删除是否失败,因此返回类型为bool

 

由于用指针rear指向新加进来的,用指针front指向最先加进来的(也就是应被删除的)。

 

添加用new来分配动态内存(类型为结构Node),删除用delete删除(正好形成一个new对应一个delete)。

 

新添加的,结构成员next指向空指针,其他的,结构成员next指向下一个结构体。

 

故有⑥的函数:

bool Queue::enqueue(const Item &item)	//队尾添加新对象
{
	if (isfull())	//如果队列满了
	{
		cout << "队列已满,无法添加新成员。" << endl;
		return false;
	}
	Node* one = new Node;
	one->item = item;	//将参数赋值给new出来的item成员
	one->next = nullptr;	//new出来的item成员的指针是空的
	rear = one;	//rear指向新的结构
rear->next = one;	//之前一个的指针指向新出来的位置
	if (items==0)	//如果队列为0,书上这里用items==nullptr的判断条件,但个人感觉是一样的
	{
		front = rear;	//那么front指针和rear指针指向同一个位置,否则front的位置不变(指向最开始的那个)
	}
	items++;	//计数器加1
	return true;	//返回添加成功
}

 

⑦的函数:

bool Queue::dequeue(Item &item)	//队首删除,并将删除的对手传递给参数
{
	if (isempty())	//如果队列空的,则无法删除
	{
		cout << "队列是空的,无法删除。" << endl;
		return false;
	}
	Node* one = front->next;	//创建一个指针,指向下一个位置。如果下一个位置是空,则这里结果是空指针
	item = front->item;	//将将要被删除的对象,传递给参数
	delete front;	//删除队首
	front = one;	//让front指向one(也就是说下次的队首)
	items--;	//计数器减一
	return true;
}

 

这里之所以用new一个新的结构,原因在于,需要用new出来的结构作为中介,传递结构内部的指针

 

 

关于⑧:

确认队伍里对象的数量,这个很简单,查看计数器即可,使用内联函数。

int queuecout()const { return items; }; //计算队列项目数量

 

 

 

关于析构函数:

为了防止内存溢出,故设置析构函数,清除所有由new创建的对象。

Queue::~Queue()
{
	while (front != nullptr)	//如果队首的不是空指针
	{
		Node* newone = front->next;	//创建一个指针指向下一个结构
		delete front;	//删除当前结构
		front = newone;	//front变成下一个结构
	}		//这样可以一直删除到遇见front是空指针(因为最后一个结构的指针是空指针)
}

因此有类定义和类方法定义:

typedef int Item;	//将Item用作一个类型的别名
class Queue
{
private:
	struct Node	//node是节点的意思
	{
		Item item;
		Node* next;	//struct Node表示struct Node的指针,貌似只用Node*next也可以
	};
	Node *front;		//表示最前,也就是first in和first out
	Node *rear;		//表示最后,也就是last int和last out(对目前来说)
	int items;	//变量,用作计数器
	enum { Max = 10 };	//静态常量,用作限制。枚举作为静态常量个人感觉更方便一些
	const int size;		//常量,用作对象的项目最大数
public:
	Queue(int qs = Max);	//创造一个用传递的变量qs限制的队列
	~Queue();	//析构函数
	bool isempty()const;	//返回队列是否空的
	bool isfull()const;		//返回队列是否满的
	int queuecout()const { return items; };	//计算队列项目数量
	bool enqueue(const Item &item);	//将东西放进队列,并返回放置结果
	bool dequeue(Item &item);	//将东西取出,并返回取出结果

};

Queue::Queue(int qs) :size(qs), items(0)
{
	front = rear = nullptr;
}

bool Queue::isempty()const
{
	return !items;	//如果是空,则为item==0,加叹号后则为true
}

bool Queue::isfull()const
{
	return (items == size);		//如果为满,则items等于size,返回true,否则返回false
}

bool Queue::enqueue(const Item &item)	//队尾添加新对象
{
	if (isfull())	//如果队列满了
	{
		std::cout << "队列已满,无法添加新成员。" << std::endl;
		return false;
	}
	Node* newone = new Node;
	newone->item = item;	//将参数赋值给new出来的item成员
	newone->next = nullptr;	//new出来的item成员的指针是空的
	if (items == 0)	//如果队列为0,书上这里用items==nullptr的判断条件,但个人感觉是一样的
	{
		front = newone;	//那么front指针和rear指针指向同一个位置,否则front的位置不变(指向最开始的那个)
	}
	else	//如果队列里有东西,则
	{
		rear->next = newone;	//之前一个的指针指向新出来的位置
	}
	rear = newone;	//rear指向新的结构
	items++;	//计数器加1
	return true;	//返回添加成功
}

bool Queue::dequeue(Item &item)	//队首删除,并将删除的对手传递给参数
{
	if (isempty())	//如果队列空的,则无法删除
	{
		std::cout << "队列是空的,无法删除。" << std::endl;
		return false;
	}
	Node* one = front->next;	//创建一个指针,指向下一个位置。如果下一个位置是空,则这里结果是空指针
	item = front->item;	//将将要被删除的对象,传递给参数
	delete front;	//删除队首
	front = one;	//让front指向one(也就是说下次的队首)
	--items;	//计数器减一
	if (items == 0)rear = nullptr;	//如果没有项目了,那么rear也要是空指针(原因在于剩一个项目时,rear和front指向同一个
	return true;
}

Queue::~Queue()
{
	while (front != nullptr)	//如果队首的不是空指针
	{
		Node* newone = front->next;	//创建一个指针指向下一个结构
		delete front;	//删除当前结构
		front = newone;	//front变成下一个结构
	}		//这样可以一直删除到遇见front是空指针(因为最后一个结构的指针是空指针)
}

 

注意:

①我在写的时候,犯的最主要的错误是,忘记遇见 第一个项目(Item,要根据不同情况,frontrear指针要可能要指向 空指针 

 

例如,在0项目添加时,frontrear此时状态是空指针。然后rear指向了新创建的结构的地址(每次新项目都要这么做),但front此时还是空指针(其理应指向第一个,也就是0项目时创建的结构);

 

在删除最后一个项目时,front指向当前结构的指针(也就是下一个结构,此时是空指针,并没有什么错误,每次都应该这么做)。但rear此时依然指向当前结构(也就是被删除的这个项目),在删除后剩0项目的情况下,rear应该是空指针,而不应该是被删除的结构(因为这个结构的内存已经被释放了)。

 

 

 

 

 

 

链表:

以上这种 一个结构包含一个项目(也许是多个项目),外加一个指针(这个指针指向下一个结构) 的形式,被称为是链表。

 

链表由节点序列组成, 每一个节点 中都包含要 保存到链表中的信息 和一个 指向下一个节点的指针 

 

这里是单向链表,也就是每个节点中的指针都指向下一个节点,这样的话,我们拥有第一个节点的地址时,就可以找到这个链表中任何一个节点。而最后一个节点的指针通常是nullptr(空指针,C++11表示方法)。

 

除了单向链表之外,还有双向链表,以及循环链表。

双向链表则每个节点额外增加一个指针,指向上一个节点。

循环链表则是最后一个节点的指针指向第一个节点,这样的话,就成为了一个圆。

 

 

 

嵌套:

在这里,节点是结构,而结构在类中,作用域为整个类,因此,结构被嵌套在了类之中。

 

如果结构在公有部分(public),那么可以通过 类名::结构名 来使用结构,如果在私有部分,就只能通过友元函数来使用了。

 

有的老式版本不接受这种编译方式,于是结构就只能声明为全局的。

 

 

 

 

 

队列复制:

假如我们创建了一个这样的队列(Queue类对象one),然后用另一个Queue对象b,将a赋值给他(或者使用a作为参数调用复制构造函数)。

 

这样出现了一个问题,例如,两个队列的的第一个节点,其指针指向同一个地址(第二个节点),假如删除对象a的第一个节点,那么对象b的第一个节点也随之删除了(但对象b的计数器、front,甚至rear都保持原样),于是对对象a的操作便会出现问题(不能delete一个已经被delete的结构)。

 

两个办法:

①自定义复制构造函数/赋值运算符。

即一个一个复制对象a的节点,然后使用new创建节点,把对象a对应的节点的Item复制到对象b之中,然后对象b的上一个节点的指针指向现在这个节点。然后循环重复。

 

②禁止使用复制构造函数/赋值运算符进行默认的赋值。

即将其变为私有成员(私有成员不能在类外使用)(书上称为 伪私有成员化),也就是把复制构造函数和赋值运算符挪到private部分。

 

备注:在类的数据成员有 常量类型 时(例如const int a),没有 默认的赋值运算符(operator=(const Queue&))。

如:
Queue(const Queuea):size(0) {} //伪私有成员化复制构造函数,由于size是常量,因此这里要初始化

Queueoperator=(const Queue&a) {} //伪私有成员化赋值运算符

 

于是:

Queue one(5); //允许

Queue two; //允许

two = one; //不允许

Queue three(one); //不允许

 

C++11还提供了另外一种禁用的方式(使用关键字delete),第18章。

 

 

 

节点中的项目:

之前,使用Item作为int的别名。但是实际中,Item也可以成为结构、类、或者其他类型的别名,只要满足Queue类的需求(例如可以把一个Item通过赋值符号赋值给另一个Item)即可。

 

 

在书上,由于模拟的是ATM,那么用的则是customer类(顾客)。

 

因为简化,因此数据成员取最重要的两点:①等待时间(到自己时消耗了多少时间);②消耗时间(自己需要多久),单位根据实际需要。

 

其次,关于类方法需要:

①新建一个顾客(默认构造函数);

②设置顾客的等待时间(给参数赋值)和消耗时间(随机生成);

③返回顾客的等待时间(可直接返回);

④返回顾客的消耗时间(可直接返回)。

 

在这个类定义中,是无法直接统计顾客已经等待的时间的。但可以用一个类外定义的变量来记录(数值可以从方法④中得到,并给方法②赋值,方法③可以得到通过②赋值后的等待时间)。

 

若要计算一个顾客需要等多久到她,可以通过指针,然后读取每个节点的消耗时间并累计相加即可。

 

项目的代码:

class Customer
{
	long arrive;	//等待时间
	int processtime;	//自身消耗时间
public:
	Customer() { arrive = processtime = 0; }	//默认构造函数,初始化
	long when()const { return arrive; }	//返回等待时间
	int ptime()const { return processtime; }	//返回消耗时间
	void set(long when)
	{
		processtime = std::rand() % 3 + 1;	//等待1~4单位时间
		arrive = when;	//等待时间等于when
	}
};

 

 

综合使用:

Customer类和Queue类综合使用,将Item作为Customer类的别名。

有几件需要注意的:

①需要一个变量来记录等待时间;

②需要一个函数来随机生成顾客(即不固定时间增添新顾客);

③需要别的变量记录有必要记录的事情。

 

这里,仿照书上:

将②定位平均6分钟来一名顾客;

记录空闲时间;

记录所有顾客总等待时间;

记录平均每名顾客的等待时间;

记录每名顾客的来访时间,及其消耗时间;

 

 

思路:

①来到了新的一分钟

②如果有人正在办理,那么办理剩余时间-1。减一后,如果剩余时间为0,则说明办理完了,否则继续办理。——这里分析正在办理的顾客,情况是办理中

③否则需要一个新的顾客来办理。

④判定是否来了新顾客。来了,添加到队列(参数为进入队伍时间),不来,无改变

⑤由于可以接受新的办理顾客,那么判断

⑥如果队列空,说明接下来的1分钟柜台没人。进入下1分钟。

⑦如果队列有人,那么把最前排的人从队列中取出,读取其进入队伍时间(当前时间-进入队伍时间=排队时间,把排队时间加入到总等待时间之中),读取其消耗时间,把剩余办理时间改为消耗时间(于是状态为正在办理)。

⑧重复循环,直到出统计结果。

全部代码为:

//queue.cpp	定义类
#pragma once
class Customer
{
	long arrive;	//到达时间
	int processtime;	//自身消耗时间
public:
	Customer() { arrive = processtime = 0; }	//默认构造函数,初始化
	long when()const { return arrive; }	//返回到达时间
	int ptime()const { return processtime; }	//返回消耗时间
	void set(long when)	//将到达时间作为参数传递
	{
		processtime = std::rand() % 3 + 1;	//等待1~4单位时间
		arrive = when;	//到达时间等于when
	}
};

typedef Customer Item;	//将Item用作一个类型的别名

class Queue
{
private:
	struct Node	//node是节点的意思
	{
		Item item;
		Node* next;	//struct Node表示struct Node的指针,貌似只用Node*next也可以
	};
	Node *front;		//表示最前,也就是first in和first out
	Node *rear;		//表示最后,也就是last int和last out(对目前来说)
	int items;	//变量,用作计数器
	enum { Max = 10 };	//静态常量,用作限制。枚举作为静态常量个人感觉更方便一些
	const int size;		//常量,用作对象的项目最大数
	Queue(const Queue& a) :size(0) {}	//伪私有成员化复制构造函数,由于size是常量,因此这里要初始化
	Queue& operator=(const Queue&a) {}	//伪私有成员化赋值运算符
public:
	Queue(int qs = Max);	//创造一个用传递的变量qs限制的队列
	~Queue();	//析构函数
	bool isempty()const;	//返回队列是否空的
	bool isfull()const;		//返回队列是否满的
	int queuecout()const { return items; };	//计算队列项目数量
	bool enqueue(const Item &item);	//将东西放进队列,并返回放置结果
	bool dequeue(Item &item);	//将东西取出,并返回取出结果
};

bool iscoming(int when);

//queue.cpp 定义类Queue的类方法
#include<iostream>
#include"queue.h"

Queue::Queue(int qs) :size(qs), items(0)
{
	front = rear = nullptr;
}

bool Queue::isempty()const
{
	return !items;	//如果是空,则为item==0,加叹号后则为true
}

bool Queue::isfull()const
{
	return (items == size);		//如果为满,则items等于size,返回true,否则返回false
}

bool Queue::enqueue(const Item &item)	//队尾添加新对象
{
	if (isfull())	//如果队列满了
		return false;
	Node* newone = new Node;
	newone->item = item;	//将参数赋值给new出来的item成员
	newone->next = nullptr;	//new出来的item成员的指针是空的
	if (items == 0)	//如果队列为0,书上这里用items==nullptr的判断条件,但个人感觉是一样的
	{
		front = newone;	//那么front指针和rear指针指向同一个位置,否则front的位置不变(指向最开始的那个)
	}
	else	//如果队列里有东西,则
	{
		rear->next = newone;	//之前一个的指针指向新出来的位置
	}
	rear = newone;	//rear指向新的结构
	items++;	//计数器加1
	return true;	//返回添加成功
}

bool Queue::dequeue(Item &item)	//队首删除,并将删除的对手传递给参数
{
	if (isempty())	//如果队列空的,则无法删除
		return false;
	Node* one = front->next;	//创建一个指针,指向下一个位置。如果下一个位置是空,则这里结果是空指针
	item = front->item;	//将将要被删除的对象,传递给参数
	delete front;	//删除队首
	front = one;	//让front指向one(也就是说下次的队首)
	--items;	//计数器减一
	if (items == 0)rear = nullptr;	//如果没有项目了,那么rear也要是空指针(原因在于剩一个项目时,rear和front指向同一个
	return true;
}

Queue::~Queue()	//析构函数
{
	while (front != nullptr)	//如果队首的不是空指针
	{
		Node* newone = front->next;	//创建一个指针指向下一个结构
		delete front;	//删除当前结构
		front = newone;	//front变成下一个结构
	}		//这样可以一直删除到遇见front是空指针(因为最后一个结构的指针是空指针)
}


bool iscoming(int when)	//参数为平均多久来一位顾客
{
	return (rand()*when / RAND_MAX < 1);
}

//1.cpp main函数,用于测试类
#include<iostream>
#include<ctime>
#include"queue.h"

struct time_q
{
	long time_clock;	//时间轴
	long time_max;	//最大时间
	int average;	//平均时间
	long all_wait;	//累计等待时间
	int all_customers;	//累计办理完顾客
	int lazy_time;	//累计空闲时间
	int leave;	//因为满而离开的顾客数
};

int main()
{
	using namespace std;
	time_q how;	//记录时间用
	char q;
	int wait_times, last_time;
	cout << "如果退出,输入q,否则,继续" << endl;
	while (cin >> q)
	{
		//初始化部分
		wait_times = 0;	//记录当前等待时间
		last_time = 0;	//记录剩余时间
		Item one;	//顾客,新来的和正在办理的
		how.all_wait = how.all_customers = how.lazy_time = how.leave = 0;
		srand(time(0));
		cout << endl;

		cin.sync();
		if (q == 'q')
			break;
		cout << "************ATM模拟程序************" << endl;
		cout << "输入模拟总时间:";
		cin >> how.time_max;
		cout << "输入顾客平均到达间隔:";
		cin >> how.average;
		cout << "输入ATM允许排队的长度(不包括正在办理的):";
		int num;
		cin >> num;
		cout << "***********参数加载完毕************" << endl;
		Queue ATM(num);	//创建队列ATM,参数为num

		for (how.time_clock = 0;how.time_clock < how.time_max;++how.time_clock)	//初始化时间轴为0,模拟时间不大于总时间
		{
			if (wait_times > 0)	//如果等待时间大于0,说明有人正在办理
			{
				wait_times--;	//等待时间-1,因为来到新的一分钟,所以需要-1
				if (wait_times == 0)	//如果-1后等于0了,说明正在办理的人从上个时间到这个时间后,已经办完了
				{
					how.all_customers++;	//办理完的顾客数+1
				}
			}
			if (iscoming(how.average))	//如果有人来
			{
				one.set(how.time_clock);	//设置这个人
				if (!ATM.enqueue(one))	//将这个人加入到队列
					how.leave++;	//加入失败的话,因人多而离开的人数+1
			}

			if (ATM.isempty()&& wait_times == 0)	//如果队列是空的,等待时间也为0(要么没人办,要么有人办理完了)
			{
				how.lazy_time++;	//空闲时间+1(因为没人需要在这个时间办理)
				continue;	//如果是空的,则进入下一个单位时间
			}		//排除这个情况后,那么可能队列空,但是有人还在办理

			if (wait_times == 0)	//如果等待时间为0,因为上面否认队列空且等待时间为0,所以队列肯定有人
			{
				ATM.dequeue(one);	//取出最前排的对象
				wait_times = one.ptime();	//办理完成需要时间从对象数据中读取
				how.all_wait += (how.time_clock - one.when());	//总等待时间加上当前顾客的等待时间
			}
		}
		cout << "累计等待时间为:" << how.all_wait << "分钟" << endl;
		cout << "空闲时间" << how.lazy_time << "分钟,占比" << double(how.lazy_time) / how.time_max * 100 << "%" << endl;
		cout << "累计完成业务办理顾客" << how.all_customers << "人" << endl;
		cout << "因队列满离开人数为" << how.leave << endl;
		cout << "平均等待时间为:" << double(how.all_wait) / how.all_customers << "分钟" << endl << endl;
		cout << "如果退出,输入q,否则,继续" << endl;
		ATM.~Queue();	//调用析构函数,清除ATM队列
	}
	system("pause");
	return 0;
}

 

 

 

总结:

①我在写每分钟的通报情况纠结了很久,后来放弃了。

比如“第X分钟,是否来新顾客,当前顾客是否办理完,还需要多少分钟。队列里还有几个人,是否有新的顾客开始办理,开始办理的顾客等待了多久,他需要多少分钟办理完等”。

原因在于,这个Queue类的在应用时,其原理是不包含正在队列中办理的人,也就是,ATM前分为2种顾客,一种是正在办理的(不计算在队列中),一种是正在排队的(计算在队列中)。第一种从队列中取出(使用dequeue()函数),计算队列只考虑第二种。

但我在初期考虑时,以为队列中包含了正在办理的人,因此纠结了很久(因为读取后,判断队列是否满,在之前的函数是不直接支持的)。

 

②关于书上的代码,思路和我的有所区别。书上代码的思路是:

1)判断是否有新顾客来,如果有,尝试加入到队列,加入失败,则离开人数+1

2)判断是否等待时间为0,且队列不空。如果成立,则把队列中的顾客加入到正在办理中,把其需要消耗时间设置为等待时间。把其等待时间加入到总等待时间。

3)如果等待时间大于0,那么说明有人正在办理,于是等待时间-1

4)计算此时队列的长度,加入到总队列长度(之后可以除以时间求得队列长度)

 

和我的思路主要区别在于:

书上的是等待的人在当前分钟减1

我的是进入新的1分钟后再判断是否-1

不过两种方法都有共同缺陷,都无法判断假如到最后一分钟时,有人刚好办理完业务,把这个人加入到办理完业务的人之中。

 

 

③另一个错误在于进行可以循环的修改代码时,忘记把每个数值都重新初始化了,因此多次循环会导致数据偏差。

 

 

补:之所以会导致平均队列增加,是因为每个人平均消耗2.5分钟,2分钟来一个,如果没有限制队伍长度的话,因为拒绝的人少了,因此会导致人数很容易累计起来。从来导致平均队伍长度的增加。

但感觉还是有点蛋疼。

 

 

我的模拟结果是:

如果退出,输入q,否则,继续
1

************ATM模拟程序************
输入模拟总时间:6000
输入顾客平均到达间隔:4
输入ATM允许排队的长度(不包括正在办理的):10
***********参数加载完毕************
累计等待时间为:1020分钟
空闲时间2929分钟,占比48.8167%
累计完成业务办理顾客1539人
因队列满离开人数为0
平均等待时间为:0.662768分钟
平均队列长度为:0.170167人

如果退出,输入q,否则,继续
1

************ATM模拟程序************
输入模拟总时间:6000
输入顾客平均到达间隔:2
输入ATM允许排队的长度(不包括正在办理的):10
***********参数加载完毕************
累计等待时间为:25859分钟
空闲时间234分钟,占比3.9%
累计完成业务办理顾客2879人
因队列满离开人数为71
平均等待时间为:8.98194分钟
平均队列长度为:4.30983人

如果退出,输入q,否则,继续
1

************ATM模拟程序************
输入模拟总时间:6000
输入顾客平均到达间隔:2
输入ATM允许排队的长度(不包括正在办理的):20
***********参数加载完毕************
累计等待时间为:63908分钟
空闲时间121分钟,占比2.01667%
累计完成业务办理顾客2923人
因队列满离开人数为55
平均等待时间为:21.8638分钟
平均队列长度为:10.6553人

如果退出,输入q,否则,继续
1

************ATM模拟程序************
输入模拟总时间:6000
输入顾客平均到达间隔:2
输入ATM允许排队的长度(不包括正在办理的):20
***********参数加载完毕************
累计等待时间为:59763分钟
空闲时间57分钟,占比0.95%
累计完成业务办理顾客2924人
因队列满离开人数为46
平均等待时间为:20.4388分钟
平均队列长度为:10.0062人

如果退出,输入q,否则,继续
q

请按任意键继续. . .


网友评论

登录后评论
0/500
评论
零零水
+ 关注