#算法#队列和链表无处不在

请查看原文：

 

http://www.ibaiyang.org/2012/11/20/queue-list/

 

在我读严蔚敏版的《数据结构》的时候，看到其中一个例子，让我对数据结构佩服的五体投地，让人把如此的一个问题分析的这么透彻，十分钦佩。也让我明白了一个道理，在设计好的算法之前，一定要设计好的数据结构，当你设计了好的数据结构之后，反而会为你写算法有很大的帮助，这是我深有体会的。

在这里，就将在重复一下这个例子吧，方便以后借鉴，这个例子主要是模拟离散事件的例子。

引言

在日常生活中，我们经常会遇到各种排队的事情，比如乘地铁，去食堂就餐。我们就以去银行办理业务为例，在我们走进银行之后，我们需要到窗口办理自己的业务。

现在需要编制一个软件，模拟银行的这种业务活动并计算一天客户中在银行逗留的平均时间。

在这里，需要满足以下条件：

• 进来的客户是随即的；
• 进来之后的客户选择较短的队列排队；

为了计算客户在一天当中的平均逗留时间，需要知道每个客户在银行的逗留时间，然后其每个客户逗留时间之和除以总人数既是平均逗留时间。在通常情况下，我们知道客户到达和离开银行的时间，自然知道每个客户在银行的逗留时间。所以，我们将客户达到和离开银行这二个时刻发生的事情称为“事件”，整个模拟程序是按照事件发生的先后顺序来进行处理，这样一种模拟程序称作“事件驱动模拟”。

实现

以下描述正是上述银行客户的离散事件驱动模拟程序：

void bank_simulation(int close_time)
{
    open_for_day();
    while(more_event){
        event_drive(occure_time, event_type);
        switch(event_type){
        case "A": customer_arrived();  break;
        case "D": customer_departure(); break;
        default: invalid();
        }
    }
    close_for_day();
}

以上算法主要处理对象是“事件”, 事件的主要信息是由事件类型和事件发生的时刻。算法中要处理二类事件：一类是客户达到事件；一类是客户离开事件。前一类事件发生的时刻随客户的打来而自然形成；后一类事件发生则由客户事务所需时间和等待所消耗的时间而定。由于程序驱动是按照事件发生时刻的先后顺序进行，则事件表应该是有序表，其主要操作是插入和删除事件。

模拟程序中的另一种数据结构是表示客户排队的队列，假设银行有4个窗口，则程序需要有4个队列，队列中有关客户的主要信息是客户到达的时刻和客户办理事务所需要的时间。每个队列中的对头客户即为正在窗口办理事务的客户，他办完事务离开队列的时刻就是即将发生客户离开事件的时刻，对每个队列头客户都存在一个将要驱动的客户离开事件。因此，在任何时刻即将发生的事件只有以下5种可能：

• 新的客户达到；
• 1号窗口客户离开；
• 2号窗口客户离开；
• 3号窗口客户离开；
• 4号窗口客户离开；

由以上分析，在这个模拟程序中只需要二种数据结构：有序表和队列。他们的数据元素类型分别定义如下：

typedef struct {
    int  occure_time;
    int  event_type;
} Event;

typedef vector< Event> event_list;

typedef struct {
    int arrival_time;
    int duration;
} QElemType;

 

给出了数据结构，结合之前的算法框架，就很容易实现程序了，以下给出伪代码

event_list ev;   // 事件表
Event en;        // 事件
LinkQueue  q[5]; // 4个客户队列
QElemType  customer; // 客户记录

int total_time, customer_nr = 0;

void open_for_day()
{
    total_time = customer_nr = 0;
    init_list(ev);
    en.occure_time = 0; en.event_type = 0; // 设定第一个客户到达事件
    order_insert(ev, en, cmp);
    for(i = 1; i < 4; i++){
        init_queue(q[i]);
    }
}

void customer_arrived()
{
    customer_nr ++;
    random(durtime, intertime);      // 产生随机数
    t = en.occure_time + intertime;  // 下一个客户到达事件
    if( t < close_time ){
        order_insert(ev, (t, 0), cmp);
    }
    
    i = minimum(q);
    enqueue(q[i], (en.occure_time, durtime));
    if( queue_len(q[i]) == 1){
        order_insert(ev, (en.occure_time + durtime, i), cmp);
    }
}

void customer_departure()
{
     i = en.event_type; del_queue(q[i], customer); // 删除队列头的客户
     total_time += en.occure_time - customer.arrival_time;

     if( !queue_empty() ){  // 设定第i队列的一个离开事件并插入事件表
         get_head(q[i], customer);
         order_insert(ev, (en.occure_time + customer.duration, i)), cmp);
     }
}

我觉得写到这里，读者应该仔细去体会“驱动”二字，请分别看以上函数，举customer_departure函数为例，当该i队列产生客户离开事件后，并产生一个新的离开事件，如果该i队列不为空的话，为何会产生这个离开事件呢，因为事件表中产生了一个事件，表明第i个队列的头客户已经离开，故会产生另一个客户排在队头，当然会产生一个离开事件了。

联想

在慢慢的品味这个算法时，让我联想到了多线程中，生产—消费模型，貌似也是一个事件驱动模型,不知道对不对，不过我认为是吧，可以知道生产和消费为其中的二个事件。给出伪代码。

void produce()
{
   // 创建临界区域
    lock();
    while( v.len() == max_len ){
        condition_wait();
    }
    v.push_back( t );
    unlock();

    if( v.len() == 1){
        notify_all();
    }
}

void consume()
{
    lock();
    while ( v.len() == 0 ){
        condition_wait();
    }
    t = v.pop();
    unlock();

    if( v.len() == 0){
        notify_all();
    }
}

为什么我说这是事件驱动模型呢，因为我觉得，当生产出来了资源，即v不为空时，自然会唤醒consume线程去消费它，相反，当v为空时，又会唤醒produce生产资源，其中的唤醒类似驱动原理。

【注】如有理解偏差，实属能力问题，本人还在努力之中，共同进步。

-----------------打造高质量的文章 更多关注 把酒泯恩仇---------------

为了打造高质量的文章，请  推荐  一下吧。。。。谢谢了，请关注我后续的文章，会更精彩哦

请关注sina微博：http://weibo.com/baiyang26

把酒泯恩仇官方博客：http://www.ibaiyang.org 【推荐用google reader订阅】

把酒泯恩仇官方豆瓣：http://www.douban.com/people/baiyang26/

如果您想转载本博客，请注明出处

如果您对本文有意见或者建议，欢迎留言