3.3 典型例題

【例3.5】 循環隊列應用——鍵盤輸入循環緩沖區問題。

在操作系統中，循環隊列經常用于實時應用程序。例如，當程序正在執行其他任務時，用戶可以從鍵盤上不斷輸入內容，很多字處理軟件就是這樣工作的。系統在利用這種分時處理方法時，用戶輸入的內容不能在屏幕上立刻顯示出來，直到當前正在工作的那個進程結束為止。但在這個進程執行時，系統在不斷地檢查鍵盤狀態，如果檢測到用戶輸入了一個新的字符，就立刻把它存到系統緩沖區中，然后繼續運行原來的進程。當當前工作的進程結束后，系統就從緩沖區中取出輸入的字符，并按要求進行處理。這里的鍵盤輸入緩沖區采用了循環隊列，隊列的特性保證了先輸入、先保存、先處理的要求，循環結構又有效地限制了緩沖區的大小，并避免了假溢出問題。下面用一段程序來模擬這種應用情況。

[問題描述]：有兩個進程同時存在于一個程序中。其中第一個進程在屏幕上連續顯示字符“A”，與此同時，程序不斷檢測鍵盤是否有輸入，如果有，就讀入用戶輸入的字符并保存到輸入緩沖區中。在用戶輸入時，輸入的字符并不立即顯示在屏幕上。當用戶輸入一個逗號（，）時，表示第一個進程結束，第二個進程從緩沖區中讀取那些已輸入的字符并顯示在屏幕上。第二個進程結束后，程序又進入第一個進程，重新顯示字符“A”，同時用戶又可以繼續輸入字符，直到用戶輸入一個分號（；），才結束第一個進程，同時結束整個程序。

[算法描述]：

#include "stdio.h"
#include "conio.h"
#include "dos.h"
main()
{/*模擬鍵盤輸入循環緩沖區*/
char ch1,ch2;
SeQueue Q;
int f;
Init_Queue (&Q);   /* 隊列初始化 */
for( ; ;)
{
  for( ; ;)  /*第一個進程*/
  {
    printf("A");
    if(kbhit())
      {
        ch1=getch(); /*讀取輸入的字符，但屏幕上不顯示*/
        if (ch1==';'||ch1=='.') break; /*第一進程正常中斷*/
        f=In_Queue(&Q,ch1);
        if(f==FALSE)
        {
           printf("循環隊列已滿\n");
           break;   /* 循環隊列滿時，強制中斷第一個進程*/
        }
      }
    }
   while (!Empty_Queue(Q))  /*第二個進程*/
  {
     Out_Queue (&Q,&ch2);
     putchar(ch2);   /*顯示輸入緩沖區的內容*/
  }
  if(ch1==';')
     break;   /*整個程序結束*/
  }
}

【例3.6】 鏈列應用——模擬患者醫院看病過程。

患者在醫院看病過程：先排隊等候，再看病治療。在排隊的過程中主要重復做兩件事情，一是患者到達診室時，將病歷交給護士，排到等候隊列中候診；二是護士從等候隊列中取出下一個患者的病歷，該患者進入診室看病。

[算法思想]：在排隊時按照“先到先服務”的原則，設計一個算法模擬患者等候就診的過程。其中，“患者到達”用命令a表示，“護士讓下一位患者就診”用命令n表示，“不再接受患者排隊”用命令q表示。

本算法采用鏈隊存放患者的病歷號。

（1）當有“患者到達”命令時，則入隊；

（2）當有“護士讓下一位患者就診”命令時，則出隊；

（3）當有“不再接受患者排隊”命令時，則隊列中所有元素出隊，程序終止。

[算法描述]：

void SeeDoctor()
{
Init_Queue(Q);
flag=1;
while (flag) {
     printf("\n請輸入命令：");
     ch=getchar();
     switch(ch) {
                  case ‘a’: printf("\n 病歷號：");
                            scanf("%d",&n);
                            In_Queue(&Q,n);
                            break;
                  case 'n': if (!Empty_Queue(Q))
                                   {Out_Queue(&Q,&n);
                                    printf("\n 病歷號為%d的患者就診", n);
                                   }
                                else
                                   printf("\n 無患者等候就診");
                                break;
                      case ‘q’: printf("\n 停止掛號，下列患者依次就診：");
                                while ()
                                   { Out_Queue (&Q,&n);
                                     printf("\n 病歷號為%d的患者就診", n);
                                   }
                                   flag=0;
                                   break;
                        default: printf("\n 無效命令！");
                       }
             }
}