知识结构：
图1知识结构队列是我们经常使用的一种数据结构，如下图所示，购物结账，去食堂打饭等都需要排队，而结账或打饭的顺序与我们排队的顺序是相同的，即谁先排队就为谁先服务。
图2队列举例比如我们发送邮件、打印资料，这些都是队列的具体应用。我们把需要发送的邮件先放到发送队列中，然后按照放入的顺序进行发送，把需要打印的文件先放到打印队列中，然后按照放入的顺序进行打印。下面我们就来详细介绍“队列”这种数据结构。
1.队列的定义与操作1.1队列的定义插入（入队）在一端（队尾）进行而删除（出队）在另一端（队首）进行的线性表。即先进先出（FirstInFirstOut）的线性表。
线性表
入队与出队演示。
图3顺序表模拟入队、出队图4单链表模拟入队、出队1.2队列的操作入队操作：将数据元素插入队尾。出队操作：移除队首的数据元素。是否为空：判断队中是否包含数据元素。得到队长：获取队中实际包含数据元素的个数。清空操作：移除队中的所有数据元素。获取队首元素。图5队列接口usingSystem;namespaceLinearStruct{///summary///队列的抽象数据类型////summary///typeparamname="T"队列中元素的类型/typeparampublicinterfaceIQueueTwhereT:IComparableT{///summary///获取队列中实际包含元素的个数////summaryintLength{get;}///summary///获取队首元素////summaryTQueueFront{get;}///summary///数据元素入队////summary///paramname="data"要入队的元素/paramvoidEnQueue(Tdata);///summary///数据元素出队////summaryvoidDeQueue();///summary///判断队列中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnsboolIsEmpty();///summary///从队列中移除所有元素////summaryvoidClear();}}2.队列的顺序存储2.1顺序队列
顺序队列（SequenceQueue）：利用顺序表实现的队列。
实现：
图6顺序队列usingSystem;namespaceLinearStruct{///summary///用顺序存储结构实现的队列--顺序队列////summary///typeparamname="T"顺序队列中元素的类型/typeparampublicclassSeqQueueT:IQueueTwhereT:IComparableT{privatereadonlySeqListT_lst;///summary///初始化SeqQueue类的新实例////summary///paramname="max"SeqQueue中最多包含元素的个数/parampublicSeqQueue(intmax){if(max=0)thrownewArgumentOutOfRangeException();_lst=newSeqListT(max);}///summary///获取SeqQueue中最多包含元素的个数////summarypublicintMaxSize{get{return_lst.MaxSize;}}///summary///获取SeqQueue中实际包含元素的个数////summarypublicintLength{get{return_lst.Length;}}///summary///获取SeqQueue中的队首元素////summarypublicTQueueFront{get{if(_lst.IsEmpty())thrownewException("队列为空,不能得到队首元素.");return_lst[0];}}///summary///数据元素入队////summary///paramname="data"要入队的元素/parampublicvoidEnQueue(Tdata){if(_lst.Length==_lst.MaxSize)thrownewException("队列已满,不能入队.");_lst.Insert(_lst.Length,data);}///summary///数据元素出队////summarypublicvoidDeQueue(){if(_lst.IsEmpty())thrownewException("队列为空,不能出队.");_lst.Remove(0);}///summary///判断队列中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnspublicboolIsEmpty(){return_lst.IsEmpty();}///summary///从队列中移除所有元素////summarypublicvoidClear(){_lst.Clear();}}}
应用：
classProgram{staticvoidMain(string[]args){QueueTest(newSeqQueuestring(20));}privatestaticvoidQueueTest(IQueuestringqueue){queue.EnQueue("a1");queue.EnQueue("a2");queue.EnQueue("a3");while(queue.IsEmpty()==false){Console.WriteLine(queue.QueueFront);queue.DeQueue();}//a1//a2//a3}}2.2循环队列
循环队列（CircularSequenceQueue）：利用数组采用循环的方式实现的队列。
线性表
入队与出队演示。
图7循环队列过程演示实现：
图8循环队列usingSystem;namespaceLinearStruct{///summary///用顺序存储结构实现的队列--循环队列////summary///typeparamname="T"循环队列中元素的类型/typeparampublicclassCSeqQueueT:IQueueTwhereT:IComparableT{privateint_pFront;privateint_pRear;privatereadonlyT[]_dataset;///summary///获取CSeqQueue中实际包含元素的个数////summarypublicintLength{get;privateset;}///summary///获取CSeqQueue中最多包含元素的个数////summarypublicintMaxSize{get;}///summary///获取CSeqQueue中的队首元素////summarypublicTQueueFront{get{if(Length==0)thrownewException("队列为空不能得到队首元素.");return_dataset[_pFront];}}///summary///初始化CSeqQueue类的新实例////summary///paramname="max"CSeqQueue中最多包含元素的个数/parampublicCSeqQueue(intmax){if(max=0)thrownewArgumentOutOfRangeException();MaxSize=max;Length=0;_dataset=newT[MaxSize];_pFront=0;_pRear=0;}///summary///数据元素入队////summary///paramname="data"要入队的元素/parampublicvoidEnQueue(Tdata){if(Length==MaxSize)thrownewException("队列已满,不能入队.");_dataset[_pRear]=data;_pRear=(_pRear+1)%MaxSize;Length++;}///summary///数据元素出队////summarypublicvoidDeQueue(){if(Length==0)thrownewException("队列为空,不能出队.");_pFront=(_pFront+1)%MaxSize;Length--;}///summary///判断队列中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnspublicboolIsEmpty(){returnLength==0;}///summary///从队列中移除所有元素////summarypublicvoidClear(){_pFront=0;_pRear=0;Length=0;}}}
应用：
classProgram{staticvoidMain(string[]args){QueueTest(newCSeqQueuestring(20));}privatestaticvoidQueueTest(IQueuestringqueue){queue.EnQueue("a1");queue.EnQueue("a2");queue.EnQueue("a3");while(queue.IsEmpty()==false){Console.WriteLine(queue.QueueFront);queue.DeQueue();}//a1//a2//a3}}3.队列的链式存储
链队：利用单链表实现的队列。
利用单链表实现：
图9链队usingSystem;namespaceLinearStruct{///summary///用链式存储结构实现的队列////summary///typeparamname="T"队列中元素的类型/typeparampublicclassLinkQueueT:IQueueTwhereT:IComparableT{privatereadonlySLinkListT_lst;///summary///获取LinkQueue中实际包含元素的个数////summarypublicintLength{get{return_lst.Length;}}///summary///获取LinkQueue中的队首元素////summarypublicTQueueFront{get{if(_lst.IsEmpty())thrownewException("队列为空,不能取队首元素.");return_lst[0];}}///summary///初始化LinkQueue类的新实例////summarypublicLinkQueue(){_lst=newSLinkListT();}///summary///数据元素入队////summary///paramname="data"要入队的元素/parampublicvoidEnQueue(Tdata){_lst.InsertAtRear(data);}///summary///数据元素出队////summarypublicvoidDeQueue(){if(_lst.IsEmpty())thrownewException("队列为空,不能出队.");_lst.Remove(0);}///summary///判断队列中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnspublicboolIsEmpty(){return_lst.IsEmpty();}///summary///从队列中移除所有元素////summarypublicvoidClear(){_lst.Clear();}}}
用单链表实现队列，入队时会进行链表的遍历操作，非常耗时。故实际应用中，链队常常用循环链表来实现。
图10链队usingSystem;namespaceLinearStruct{///summary///用链式存储结构实现的队列////summary///typeparamname="T"队列中元素的类型/typeparampublicclassLinkQueueT:IQueueTwhereT:IComparableT{privatereadonlyCLinkListT_lst;///summary///获取LinkQueue中实际包含元素的个数////summarypublicintLength{get{return_lst.Length;}}///summary///获取LinkQueue中的队首元素////summarypublicTQueueFront{get{if(_lst.IsEmpty())thrownewException("队列为空,不能取队首元素.");return_lst[0];}}///summary///初始化LinkQueue类的新实例////summarypublicLinkQueue(){_lst=newCLinkListT();}///summary///数据元素入队////summary///paramname="data"要入队的元素/parampublicvoidEnQueue(Tdata){_lst.InsertAtRear(data);}///summary///数据元素出队////summarypublicvoidDeQueue(){if(_lst.IsEmpty())thrownewException("队列为空,不能出队.");_lst.Remove(0);}///summary///判断队列中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnspublicboolIsEmpty(){return_lst.IsEmpty();}///summary///从队列中移除所有元素////summarypublicvoidClear(){_lst.Clear();}}}
应用：
classProgram{staticvoidMain(string[]args){QueueTest(newLinkQueuestring());}privatestaticvoidQueueTest(IQueuestringqueue){queue.EnQueue("a1");queue.EnQueue("a2");queue.EnQueue("a3");while(queue.IsEmpty()==false){Console.WriteLine(queue.QueueFront);queue.DeQueue();}//a1//a2//a3}}4.进程4.1进程的定义
进程是程序的动态执行过程，是操作系统进行资源分配和调度的基本单位。
4.2C#对进程的管理我们通过一个具体的实例进行说明。
图11进程实例（1）所在命名空间
usingSystem.Diagnostics;
（2）进程的创建
//初始化Process类的新实例。Processpros=newProcess();
（3）进程的启动
privatevoidbuttonStartNotepad_Click(objectsender,EventArgse){Processpros=newProcess();//获取或设置要启动的应用程序或文档。pros.StartInfo.FileName="Notepad.exe";//获取或设置启动进程时使用的窗口状态。pros.StartInfo.WindowStyle=ProcessWindowStyle.Minimized;//启动此Process组件的StartInfo属性指定的进程资源，并将其与该组件关联。pros.Start();}
（4）进程的查询
privatevoidInitDataGridView(){dataGridView.ColumnCount=4;dataGridView.Columns[0].HeaderText="进程号";dataGridView.Columns[1].HeaderText="进程名称";dataGridView.Columns[2].HeaderText="所占内存";dataGridView.Columns[3].HeaderText="启动时间";}privatevoidbuttonViewProcess_Click(objectsender,EventArgse){dataGridView.RowCount=0;//为本地计算机上的每个进程资源创建一个新的Process组件。Process[]proses=Process.GetProcesses();foreach(Processpinproses){intid=p.Id;//进程号stringpName=p.ProcessName;//进程名称longmemory=p.WorkingSet64;//所占物理内存try{DateTimestartTime=p.StartTime;//进程启动的时间dataGridView.Rows.Add();intloc=dataGridView.RowCount-1;dataGridView.Rows[loc].Cells[0].Value=id;dataGridView.Rows[loc].Cells[1].Value=pName;dataGridView.Rows[loc].Cells[2].Value=memory;dataGridView.Rows[loc].Cells[3].Value=startTime;}catch{;}}}
（5）进程的终止
privatevoidbuttonAbortNotepad_Click(objectsender,EventArgse){Process[]pes=Process.GetProcessesByName("Notepad");foreach(Processpinpes){//指示Process组件在指定的毫秒数内等待关联进程退出。p.WaitForExit();//立即停止关联的进程。p.Kill();}}5.线程5.1线程的定义
同一个进程又可划分为若干个独立的执行流称之为线程，线程是CPU进行资源分配和调度的基本单位。
5.2C#对线程的管理（1）所在命名空间
usingSystem.Threading;
（2）线程的创建
//初始化Thread类的新实例。Threadthread1=newThread(enterPoint1);//enterPoint1,enterPoint2是线程要执行的方法。Threadthread2=newThread(enterPoint2);
（3）线程的启动
//导致操作系统将当前实例的状态更改为ThreadState.Running。thread1.Start();thread2.Start();
（4）线程的休眠
//将当前线程挂起指定的时间。该语句线程休眠1秒钟。Thread.Sleep();
（5）线程的合并
//阻止调用线程，直到某个线程终止为止。thread1.Join();//阻止调用线程，直到某个线程终止或经过了指定时间为止。//若thread2运行过程中需要等待thread1结束后才能继续执行，//可在thread2的模块中调用thread1.Join()，这时thread2处于阻塞状态。thread2.Join();
（6）线程的终止
//调用此方法通常会终止线程。thread1.Abort();
没有共享资源的情况下两个线程的并行。
staticclassTest{publicstaticvoidAddition(){intsum=0;for(inti=0;i=;i++){sum+=i;Console.WriteLine("sum:{0}",sum);}}publicstaticvoidDivision(){intdiv=;for(inti=0;i=;i++){div-=i;Console.WriteLine("div:{0}",div);}}}
客户端代码：
classProgram{staticvoidMain(string[]args){Threadthread1=newThread(Test.Add);Threadthread2=newThread(Test.SubStract);thread1.Start();thread2.Start();Console.WriteLine("MainThreadFinish!");}}图12运行结果
客户端代码：
classProgram{staticvoidMain(string[]args){Threadthread1=newThread(Test.Add);Threadthread2=newThread(Test.SubStract);thread1.Start();thread2.Start();thread1.Join();thread2.Join();Console.WriteLine("MainThreadFinish!");}}图13运行结果
（7）线程的同步
线程同步的定义图14线程同步Thread1没有执行完临界区代码，分配的时间片结束，这时Thread2执行临界区代码，可能会产生错误。通常要求Thread1执行完临界区代码后，Thread2才能执行临界区代码。
当两个或多个线程需要访问同一资源时，它们需要以某种顺序来确保该资源某一时刻只能被一个线程使用的方式称为线程同步。
有共享资源的情况下不同步的例子。
共享资源类：
publicclassResource{privateintcontext=0;publicvoidWrite(){context++;Console.WriteLine("Writer:{0}",context);}publicvoidRead(){Console.WriteLine("Reader{0}",context);}}
写线程执行的类：
publicclassWriter{privateResourcerec;publicWriter(Resourcer){rec=r;}publicvoidRun(){for(inti=0;i10;i++)rec.Write();}}
读线程执行的类：
publicclassReader{privateResourcerec;publicReader(Resourcer){rec=r;}publicvoidRun(){for(inti=0;i10;i++)rec.Read();}}
客户端代码：
publicclassProgram{staticvoidMain(string[]args){Resourcer=newResource();Writerwriter1=newWriter(r);Readerreader1=newReader(r);ThreadrThread=newThread(writer1.Run);ThreadwThread=newThread(reader1.Run);wThread.Start();rThread.Start();}}图15运行结果利用lock关键字进行线程同步。
用法：
privatestaticobjectobj=newobject();publicvoidFunciton(){lock(obj){//需要同步的代码段}}
改进：
publicclassResource{privateintcontext=0;privatestaticobjectobj=newobject();publicvoidWrite(){lock(obj){context++;Console.WriteLine("Writer:{0}",context);}}publicvoidRead(){lock(obj){Console.WriteLine("Reader{0}",context);}}}图16运行结果利用Monitor类进行线程同步。
用法：
privatestaticobjectobj=newobject();publicvoidFuntion(){Monitor.Enter(obj);//在指定对象上获取排他锁。//需要同步的代码段Monitor.Exit(obj);//释放指定对象上的排他锁。}
该结构与lock关键字结构等价。
publicclassResource{privateintcontext=0;privatestaticobjectobj=newobject();publicvoidWrite(){Monitor.Enter(obj);context++;Console.WriteLine("Writer:{0}",context);Monitor.Exit(obj);}publicvoidRead(){Monitor.Enter(obj);Console.WriteLine("Reader{0}",context);Monitor.Exit(obj);}}图17运行结果
wThread线程写入数据后，rThread线程读取数据，交替进行。
publicclassResource{privateintcontext=0;privateboolreadFlag=false;publicvoidWrite(){while(readFlag==true)//true:只能读,不能写(处于读状态).;context++;Console.WriteLine("Writer:{0}",context);readFlag=true;}publicvoidRead(){while(readFlag==false)//false:只能写,不能读(处于写状态).;Console.WriteLine("Reader{0}",context);readFlag=false;}}图18运行结果
以下代码与上面代码等价：
publicclassResource{privateintcontext=0;privateboolreadFlag=false;privatestaticobjectobj=newobject();publicvoidWrite(){Monitor.Enter(obj);if(readFlag==true)//true:只能读,不能写(处于读状态).Monitor.Wait(obj);//线程进入堵塞队列context++;Console.WriteLine("Writer:{0}",context);readFlag=true;Monitor.Pulse(obj);//从堵塞队列中出队Monitor.Exit(obj);}publicvoidRead(){Monitor.Enter(obj);if(readFlag==false)//false:只能写,不能读(处于写状态).Monitor.Wait(obj);Console.WriteLine("Reader:{0}",context);readFlag=false;Monitor.Pulse(obj);Monitor.Exit(obj);}}图19运行结果6.队列的应用
目前，在以银行营业大厅为代表的窗口行业中大量使用排队（叫号）系统，该系统完全模拟了人群排队全过程，通过取票进队、排队等待、叫号服务等功能，代替了人们站队的辛苦。
1.问题描述
排队叫号软件的具体操作流程为：
顾客取服务序号当顾客抵达服务大厅时，前往放置在入口处旁的取号机，并按一下其上的相应服务按钮，取号机会自动打印出一张服务单。单上显示服务号及该服务号前面正在等待服务的人数。
服务员工呼叫顾客服务员工只需按一下其柜台上呼叫器的相应按钮，则顾客的服务号就会按顺序的显示在显示屏上，并发出“叮咚”和相关语音信息，提示顾客前往该窗口办事。当一位顾客办事完毕后，柜台服务员工只需按呼叫器相应键，即可自动呼叫下一位顾客。
2.问题分析
编写程序模拟上面的工作过程，主要要求如下：
程序运行后，当看到“