3.4 棧與隊列的綜合應用舉例

棧和隊列這兩種特殊的線性表與基本線性表一樣，在實際工作和生活中有著廣泛的應用。本節通過一個實例再一次給出棧與隊列的綜合應用，使讀者能更進一步區分棧與隊列的特性和它們各自的實現技巧。

【例3-8】停車場管理問題。

【問題描述】假設停車場是一個可停放n輛車的狹長通道，并且只有一個大門可供汽車進出。在停車場內，汽車按到達的先后次序，由北向南依次排列（假設大門在最南端）。若車場內已停滿n輛車，則后來的汽車需在門外的便道上等候，當有車開走時，便道上的第一輛車即可駛入。當停車場內某輛車要離開時，在它之后進入的車輛必須先退出停車場為它讓路，待該輛車開出大門后，其他車輛再按原次序返回停車場。每輛車離開停車場時，應按其停留時間的長短交費（在便道上停留的時間不收費）。

試編寫程序，模擬上述管理過程。

【問題分析】由于停車場中某輛車的離開是按在它之后進入的車輛必須先退出停車場為它讓路的原則下進行的，顯然滿足了“后進先出”的特性，所以可以用棧式結構來模擬停車場；而對于指定停車場，它的車位數是相對固定的，因而本題采用順序棧來加以實現，并假設棧的容量為10。又由于便道上的車是按先到先開進停車場的原則進行的，即滿足“先進先出”的特性，所以可以用隊列來模擬便道；而對于便道上停放車輛的數目是不固定的，因而本題采用鏈隊列來加以實現。

為了能更好地模擬停車場管理，可以從終端讀入汽車到達或離去的數據，每組數據應該包括兩項：①汽車牌照號碼；②是“到達”還是“離去”。程序中通過庫函數time（0）自動獲取當前“到達”或“離去”的時間秒數。與每組輸入信息相應的輸出信息為：若是到達的車輛，則輸出其在停車場中或便道上的位置；若是離去的車輛，則輸出其在停車場中停留的時間和應交納的費用。

費用的計算方法是：由離開時間減去到達時間求得停留時間的總秒數，因time函數返回的為unix時間戳，即從1970年1月1日（UTC/GMT的午夜）開始所經過的秒數。然后再將秒數除以60使其轉換成多少分鐘，當不足整數分鐘時，則以整數分鐘計算。如停留時間是大于5分鐘而小于6分鐘，則以6分鐘計算。最后每分鐘的停車費乘以停車時間即可計算出總的停車費用。此題以每分鐘2元的費用進行模擬計算。

【參考代碼】

      #include"Queue.cpp"http://Queue.cpp中有隊列抽象數據類型定義中的所有基本操作函數

    #include"Stack.cpp"http://Stack.cpp中有棧抽象數據類型定義中的所有基本操作函數
    #include ＜stdio.h＞
    #include ＜time.h＞
    #include ＜string.h＞
    #define DEPARTURE 0；                    //標識車輛離開
    #define ARRIVAL 1；                      //標識車輛到達
    double fee 2.0                             //每分鐘停車費用，全局變量
    SqStack S；                             //順序棧存放停車場內的車輛信息，全局變量
    LinkQueue Q；                            //鏈隊列存放便道上的車輛信息，全局變量
    typedef struct
    { int state；                           //車輛狀態，離開或到達
        time_t  arrTime；                    //車輛達到時間
        time_t  depTime；                    //車輛離開時間
        char *license；                      //車牌號
    }CarInfo；                              //用于存放車輛信息的類型
    typedef  CarInfo  QElemType；
    typedef  CarInfo  SElemType；
    void ParkingManag（char *license，char *action）
    //停車場管理，參數license表示車牌號碼，action表示此車輛的動作到達或離開
    {   if（strcmp（"arrive"，action）==0）{    //車輛到達
            CarInfo info；                    //定義一個車輛信息類型變量
            info.license=l icense；           //修改車輛狀態
            if（StackLength（S）＜ S.stacksize）{ //停車場未滿
                info.arrTime=time（0）；       //當前時間初始化到達時間
                info.state=ARRIVAL；
                Push（S，info）；
                printf（"%s停放在停車場第%d個位置!\n"，info.l icense，StackLength（S））；
            }
            else {                           //停車場已滿
                EnQueue（Q，info）；             //進入便道隊列
                printf（"%s停放在便道第%d個位置\n"，info.l icense，QueueLength（Q））；
            }
        }
        else if（strcmp（"depart"，action）==0） //車輛離開
            {  CarInfo info；
                int location=0；             //車輛的位置
                SqStack S2；
                InitStack（S2）；  //構造棧用于存放因車輛離開而導致的其他車輛暫時退出停車場
                for（int i=StackLength（S）；i ＞ 0；i--）{
                      Pop（S，info）；
                      if（strcmp（info.license，l icense）==0）  //將離開的車輛

            { info.depTime=time（0）；   //用當前時間來初始化離開時間
              info.state=DEPARTURE；
              location=i；            //取得車輛位置信息
              break；
            }
          else                          //其他車輛暫時退出停車場
              Push（S2，info）；
        }//for
        while（! StackEmpty（S2））       //其他車輛重新進入停車場
        {  CarInfo e；
            Pop（S2，e）；
            Push（S，e）；
        }
        if（location !=0）            //停車場內存在指定車牌號碼的車輛
        //計算停放時間，并把秒換成分鐘
        {  double time=（d）ouble（info.depTime-info.arrTime）/60；
            if（（int）time＜time）       //停車時間處理后輸出
                printf（"%s停放%.2f分鐘，費用為：%.2f\n"，info.license，time，（int）（time+1）*fee）；
            else
                printf（"%s停放%.2f分鐘，費用為：%.2f\n"，info.license，time，（int）time*fee）；
        }
        if（!QueueEmpty（Q））            //便道上的第一輛車進入停車場
        {  DeQueue（Q，info）；
            info.arrTime=time（0）；      //當前時間來初始化到達時間
            info.state=ARRIVAL；
            Push（S，info）；
        }
  }
}//ParkingManag
int main（　）
{  char l icense[20]；
  char action[20]；
  InitStack（S）；                       //順序棧存放停車場內的車輛信息
  InitQueue（Q）；                       //鏈隊列存放便道上的車輛信息
  //初始化 12 輛車，車牌號分別為 1，2，…，12，其中有 10 輛車停在停車場內，2 輛車停放在便道上
  for（int i=1；i ＜=12；i++）
  {  printf（"請輸入第%d輛車的車牌號："，i）；
      gets（license）；
      ParkingManag（license，"arrive"）；
  }
  printf（"請輸入車牌號："）；

          gets（license）；
          printf（"arrive or depart ?"）；
          gets（action）；
          ParkingManag（license，action）；     //調用停車場管理函數
          return 0；
      } //例3-8 程序結束

此程序的運行結果如圖3-30所示。