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 无效命令！");
                       }
             }
}