【原】数据结构与算法：10 队列与多线程

老马的程序人生 2020-10-09

展开全文

10 队列与多线程

知识结构：

图1 知识结构

队列是我们经常使用的一种数据结构，如下图所示，购物结账，去食堂打饭等都需要排队，而结账或打饭的顺序与我们排队的顺序是相同的，即谁先排队就为谁先服务。

比如我们发送邮件、打印资料，这些都是队列的具体应用。我们把需要发送的邮件先放到发送队列中，然后按照放入的顺序进行发送，把需要打印的文件先放到打印队列中，然后按照放入的顺序进行打印。下面我们就来详细介绍“队列”这种数据结构。

1. 队列的定义与操作

1.1 队列的定义

插入（入队）在一端（队尾）进行而删除（出队）在另一端（队首）进行的线性表。即先进先出（First In First Out）的线性表。

【例子】线性表入队与出队演示。

1.2 队列的操作

入队操作：将数据元素插入队尾。
出队操作：移除队首的数据元素。
是否为空：判断队中是否包含数据元素。
得到队长：获取队中实际包含数据元素的个数。
清空操作：移除队中的所有数据元素。
获取队首元素。

图5 队列接口

using System;
namespace LinearStruct
{
    /// <summary>
    /// 队列的抽象数据类型
    /// </summary>
    /// <typeparam name="T">队列中元素的类型</typeparam>
    public interface IQueue<T> where T : IComparable<T>
    {
        /// <summary>
        /// 获取队列中实际包含元素的个数
        /// </summary>
        int Length { get; }
        /// <summary>
        /// 获取队首元素
        /// </summary>
        T QueueFront { get; }
        /// <summary>
        /// 数据元素入队
        /// </summary>
        /// <param name="data">要入队的元素</param>
        void EnQueue(T data);
        /// <summary>
        /// 数据元素出队
        /// </summary>
        void DeQueue();
        /// <summary>
        /// 判断队列中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        bool IsEmpty();
        /// <summary>
        /// 从队列中移除所有元素
        /// </summary>
        void Clear();
    }
}

2. 队列的顺序存储

2.1 顺序队列

顺序队列（Sequence Queue）：利用顺序表实现的队列。

实现：

图6 顺序队列

using System;
namespace LinearStruct
{
    /// <summary>
    /// 用顺序存储结构实现的队列--顺序队列
    /// </summary>
    /// <typeparam name="T">顺序队列中元素的类型</typeparam>
    public class SeqQueue<T> : IQueue<T> where T : IComparable<T>
    {
        private readonly SeqList<T> _lst;

        /// <summary>
        /// 初始化SeqQueue类的新实例
        /// </summary>
        /// <param name="max">SeqQueue中最多包含元素的个数</param>
        public SeqQueue(int max)
        {
            if (max <= 0)
                throw new ArgumentOutOfRangeException();
            _lst = new SeqList<T>(max);
        }
        /// <summary>
        /// 获取SeqQueue中最多包含元素的个数
        /// </summary>
        public int MaxSize
        {
            get { return _lst.MaxSize; }
        }
        /// <summary>
        /// 获取SeqQueue中实际包含元素的个数
        /// </summary>
        public int Length
        {
            get { return _lst.Length; }
        }
        /// <summary>
        /// 获取SeqQueue中的队首元素
        /// </summary>
        public T QueueFront
        {
            get
            {
                if (_lst.IsEmpty())
                    throw new Exception("队列为空,不能得到队首元素.");
                return _lst[0];
            }
        }
        /// <summary>
        /// 数据元素入队
        /// </summary>
        /// <param name="data">要入队的元素</param>
        public void EnQueue(T data)
        {
            if (_lst.Length == _lst.MaxSize)
                throw new Exception("队列已满,不能入队.");
            _lst.Insert(_lst.Length, data);
        }
        /// <summary>
        /// 数据元素出队
        /// </summary>
        public void DeQueue()
        {
            if (_lst.IsEmpty())
                throw new Exception("队列为空,不能出队.");
            _lst.Remove(0);
        }
        /// <summary>
        /// 判断队列中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        public bool IsEmpty()
        {
            return _lst.IsEmpty();
        }
        /// <summary>
        /// 从队列中移除所有元素
        /// </summary>
        public void Clear()
        {
            _lst.Clear();
        }
    }
}

应用：

class Program
{
    static void Main(string[] args)
    {
        QueueTest(new SeqQueue<string>(20));
    }
    private static void QueueTest(IQueue<string> queue)
    {
        queue.EnQueue("a1");
        queue.EnQueue("a2");
        queue.EnQueue("a3");
        while (queue.IsEmpty() == false)
        {
            Console.WriteLine(queue.QueueFront);
            queue.DeQueue();
        }
        // a1
        // a2
        // a3
    }
}

2.2 循环队列

循环队列（Circular Sequence Queue）：利用数组采用循环的方式实现的队列。

【例子】线性表入队与出队演示。

实现：

图8 循环队列

using System;
namespace LinearStruct
{
    /// <summary>
    /// 用顺序存储结构实现的队列--循环队列
    /// </summary>
    /// <typeparam name="T">循环队列中元素的类型</typeparam>
    public class CSeqQueue<T> : IQueue<T> where T : IComparable<T>
    {
        private int _pFront;
        private int _pRear;
        private readonly T[] _dataset;
        
        /// <summary>
        /// 获取CSeqQueue中实际包含元素的个数
        /// </summary>
        public int Length { get; private set; }
        /// <summary>
        /// 获取CSeqQueue中最多包含元素的个数
        /// </summary>
        public int MaxSize { get; }
        /// <summary>
        /// 获取CSeqQueue中的队首元素
        /// </summary>
        public T QueueFront
        {
            get
            {
                if (Length == 0)
                    throw new Exception("队列为空不能得到队首元素.");

                return _dataset[_pFront];
            }
        }
        /// <summary>
        /// 初始化CSeqQueue类的新实例
        /// </summary>
        /// <param name="max">CSeqQueue中最多包含元素的个数</param>
        public CSeqQueue(int max)
        {
            if (max <= 0)
                throw new ArgumentOutOfRangeException();
            MaxSize = max;
            Length = 0;
            _dataset = new T[MaxSize];
            _pFront = 0;
            _pRear = 0;
        }
        /// <summary>
        /// 数据元素入队
        /// </summary>
        /// <param name="data">要入队的元素</param>
        public void EnQueue(T data)
        {
            if (Length == MaxSize)
                throw new Exception("队列已满,不能入队.");
            _dataset[_pRear] = data;
            _pRear = (_pRear + 1)%MaxSize;
            Length++;
        }
        /// <summary>
        /// 数据元素出队
        /// </summary>
        public void DeQueue()
        {
            if (Length == 0)
                throw new Exception("队列为空,不能出队.");
            _pFront = (_pFront + 1)%MaxSize;
            Length--;
        }
        /// <summary>
        /// 判断队列中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        public bool IsEmpty()
        {
            return Length == 0;
        }
        /// <summary>
        /// 从队列中移除所有元素
        /// </summary>
        public void Clear()
        {
            _pFront = 0;
            _pRear = 0;
            Length = 0;
        }
    }
}

应用：

class Program
{
    static void Main(string[] args)
    {
        QueueTest(new CSeqQueue<string>(20));
    }
    private static void QueueTest(IQueue<string> queue)
    {
        queue.EnQueue("a1");
        queue.EnQueue("a2");
        queue.EnQueue("a3");
        while (queue.IsEmpty() == false)
        {
            Console.WriteLine(queue.QueueFront);
            queue.DeQueue();
        }
        // a1
        // a2
        // a3
    }
}

3. 队列的链式存储

链队：利用单链表实现的队列。

利用单链表实现：

图9 链队

using System;
namespace LinearStruct
{
    /// <summary>
    /// 用链式存储结构实现的队列
    /// </summary>
    /// <typeparam name="T">队列中元素的类型</typeparam>
    public class LinkQueue<T> : IQueue<T> where T : IComparable<T>
    {
        private readonly SLinkList<T> _lst;
        /// <summary>
        /// 获取LinkQueue中实际包含元素的个数
        /// </summary>
        public int Length
        {
            get { return _lst.Length; }
        }
        /// <summary>
        /// 获取LinkQueue中的队首元素
        /// </summary>
        public T QueueFront
        {
            get
            {
                if (_lst.IsEmpty())
                    throw new Exception("队列为空,不能取队首元素.");
                return _lst[0];
            }
        }
        /// <summary>
        /// 初始化LinkQueue类的新实例
        /// </summary>
        public LinkQueue()
        {
            _lst = new SLinkList<T>();
        }
        /// <summary>
        /// 数据元素入队
        /// </summary>
        /// <param name="data">要入队的元素</param>
        public void EnQueue(T data)
        {
            _lst.InsertAtRear(data);
        }
        /// <summary>
        /// 数据元素出队
        /// </summary>
        public void DeQueue()
        {
            if (_lst.IsEmpty())
                throw new Exception("队列为空,不能出队.");

            _lst.Remove(0);
        }
        /// <summary>
        /// 判断队列中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        public bool IsEmpty()
        {
            return _lst.IsEmpty();
        }
        /// <summary>
        /// 从队列中移除所有元素
        /// </summary>
        public void Clear()
        {
            _lst.Clear();
        }
    }
}

用单链表实现队列，入队时会进行链表的遍历操作，非常耗时。故实际应用中，链队常常用循环链表来实现。

图10 链队

using System;
namespace LinearStruct
{
    /// <summary>
    /// 用链式存储结构实现的队列
    /// </summary>
    /// <typeparam name="T">队列中元素的类型</typeparam>
    public class LinkQueue<T> : IQueue<T> where T : IComparable<T>
    {
        private readonly CLinkList<T> _lst;
        /// <summary>
        /// 获取LinkQueue中实际包含元素的个数
        /// </summary>
        public int Length
        {
            get { return _lst.Length; }
        }
        /// <summary>
        /// 获取LinkQueue中的队首元素
        /// </summary>
        public T QueueFront
        {
            get
            {
                if (_lst.IsEmpty())
                    throw new Exception("队列为空,不能取队首元素.");
                return _lst[0];
            }
        }
        /// <summary>
        /// 初始化LinkQueue类的新实例
        /// </summary>
        public LinkQueue()
        {
            _lst = new CLinkList<T>();
        }
        /// <summary>
        /// 数据元素入队
        /// </summary>
        /// <param name="data">要入队的元素</param>
        public void EnQueue(T data)
        {
            _lst.InsertAtRear(data);
        }
        /// <summary>
        /// 数据元素出队
        /// </summary>
        public void DeQueue()
        {
            if (_lst.IsEmpty())
                throw new Exception("队列为空,不能出队.");

            _lst.Remove(0);
        }
        /// <summary>
        /// 判断队列中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        public bool IsEmpty()
        {
            return _lst.IsEmpty();
        }
        /// <summary>
        /// 从队列中移除所有元素
        /// </summary>
        public void Clear()
        {
            _lst.Clear();
        }
    }
}

应用：

class Program
{
    static void Main(string[] args)
    {
        QueueTest(new LinkQueue<string>());
    }
    private static void QueueTest(IQueue<string> queue)
    {
        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.2 C# 对进程的管理

我们通过一个具体的实例进行说明。

（1）所在命名空间

using System.Diagnostics;

（2）进程的创建

//初始化Process类的新实例。
Process pros = new Process();

（3）进程的启动

private void buttonStartNotepad_Click(object sender, EventArgs e)
{
    Process pros = new Process();
    //获取或设置要启动的应用程序或文档。
    pros.StartInfo.FileName = "Notepad.exe";
    //获取或设置启动进程时使用的窗口状态。
    pros.StartInfo.WindowStyle = ProcessWindowStyle.Minimized;
    //启动此 Process 组件的 StartInfo 属性指定的进程资源，并将其与该组件关联。
    pros.Start();
}

（4）进程的查询

private void InitDataGridView()
{
    dataGridView.ColumnCount = 4;
    dataGridView.Columns[0].HeaderText = "进程号";
    dataGridView.Columns[1].HeaderText = "进程名称";
    dataGridView.Columns[2].HeaderText = "所占内存";
    dataGridView.Columns[3].HeaderText = "启动时间";
}

private void buttonViewProcess_Click(object sender, EventArgs e)
{
    dataGridView.RowCount = 0;
    //为本地计算机上的每个进程资源创建一个新的 Process 组件。
    Process[] proses = Process.GetProcesses();
    foreach (Process p in proses)
    {
        int id = p.Id;//进程号
        string pName = p.ProcessName;//进程名称
        long memory = p.WorkingSet64;//所占物理内存
        try
        {
            DateTime startTime = p.StartTime;//进程启动的时间
            dataGridView.Rows.Add();
            int loc = 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）进程的终止

private void buttonAbortNotepad_Click(object sender, EventArgs e)
{
    Process[] pes = Process.GetProcessesByName("Notepad");
    foreach (Process p in pes)
    {
        //指示 Process 组件在指定的毫秒数内等待关联进程退出。
        p.WaitForExit(1000);
        //立即停止关联的进程。
        p.Kill();
    }
}

5. 线程

5.1 线程的定义

同一个进程又可划分为若干个独立的执行流称之为线程，线程是CPU进行资源分配和调度的基本单位。

5.2 C#对线程的管理

（1）所在命名空间

using System.Threading;

（2）线程的创建

//初始化 Thread 类的新实例。
Thread thread1 = new Thread(enterPoint1);
//enterPoint1,enterPoint2 是线程要执行的方法。
Thread thread2 = new Thread(enterPoint2);

（3）线程的启动

//导致操作系统将当前实例的状态更改为 ThreadState.Running。
thread1.Start();
thread2.Start();

（4）线程的休眠

//将当前线程挂起指定的时间。该语句线程休眠1秒钟。
Thread.Sleep(1000);

（5）线程的合并

//阻止调用线程，直到某个线程终止为止。
thread1.Join();
//阻止调用线程，直到某个线程终止或经过了指定时间为止。
//若 thread2 运行过程中需要等待 thread1 结束后才能继续执行，
//可在 thread2 的模块中调用 thread1.Join()，这时 thread2处于阻塞状态。
thread2.Join(1000);

（6）线程的终止

//调用此方法通常会终止线程。
thread1.Abort();

【例子】没有共享资源的情况下两个线程的并行。

static class Test
{
    public static void Addition()
    {
        int sum = 0;
        for (int i = 0; i <= 100; i++)
        {
            sum += i;
            Console.WriteLine("sum:{0}", sum);
        }
    }

    public static void Division()
    {
        int div = 5050;
        for (int i = 0; i <= 100; i++)
        {
            div -= i;
            Console.WriteLine("div:{0}", div);
        }
    }
}

客户端代码：

class Program
{
    static void Main(string[] args)
    {
        Thread thread1 = new Thread(Test.Add);
        Thread thread2 = new Thread(Test.SubStract);
        thread1.Start();
        thread2.Start();
        Console.WriteLine("Main Thread Finish!");
    }
}

客户端代码：

class Program
{
    static void Main(string[] args)
    {
        Thread thread1 = new Thread(Test.Add);
        Thread thread2 = new Thread(Test.SubStract);
        thread1.Start();
        thread2.Start();
        thread1.Join();
        thread2.Join();
        Console.WriteLine("Main Thread Finish!");
    }
}

（7）线程的同步

线程同步的定义

Thread1没有执行完临界区代码，分配的时间片结束，这时Thread2执行临界区代码，可能会产生错误。通常要求Thread1执行完临界区代码后，Thread2才能执行临界区代码。

当两个或多个线程需要访问同一资源时，它们需要以某种顺序来确保该资源某一时刻只能被一个线程使用的方式称为 线程同步。

【例子】有共享资源的情况下不同步的例子。

共享资源类：

public class Resource
{
    private int context = 0;
    public void Write()
    {
        context++;
        Console.WriteLine("Writer:{0}", context);
    }
    public void Read()
    {
        Console.WriteLine("Reader{0}", context);
    }
}

写线程执行的类：

public class Writer
{
    private Resource rec;
    public Writer(Resource r)
    {
        rec = r;
    }
    public void Run()
    {
        for (int i = 0; i < 10; i++)
            rec.Write();
    }
}

读线程执行的类：

public class Reader
{
    private Resource rec;
    public Reader(Resource r)
    {
        rec = r;
    }
    public void Run()
    {
        for (int i = 0; i < 10; i++)
            rec.Read();
    }
}

客户端代码：

public class Program
{
    static void Main(string[] args)
    {
        Resource r = new Resource();
        Writer writer1 = new Writer(r);
        Reader reader1 = new Reader(r);

        Thread rThread = new Thread(writer1.Run);
        Thread wThread = new Thread(reader1.Run);

        wThread.Start();
        rThread.Start();
    }
}

利用lock关键字进行线程同步。

用法：

private static object obj = new object();
public void Funciton()
{
    lock (obj)
    {
        //需要同步的代码段
    }
}

改进：

public class Resource
{
    private int context = 0;
    private static object obj = new object();
    public void Write()
    {
        lock (obj)
        {
            context++;
            Console.WriteLine("Writer:{0}", context);
        }
    }
    public void Read()
    {
        lock (obj)
        {
            Console.WriteLine("Reader{0}", context);
        }
    }
}

利用Monitor类进行线程同步。

用法：

private static object obj = new object();
public void Funtion()
{
    Monitor.Enter(obj);//在指定对象上获取排他锁。
    //需要同步的代码段
    Monitor.Exit(obj);//释放指定对象上的排他锁。
}

该结构与lock关键字结构等价。

public class Resource
{
    private int context = 0;
    private static object obj = new object();
    public void Write()
    {
        Monitor.Enter(obj);
        context++;
        Console.WriteLine("Writer:{0}", context);
        Monitor.Exit(obj);
    }
    public void Read()
    {
        Monitor.Enter(obj);
        Console.WriteLine("Reader{0}", context);
        Monitor.Exit(obj);
    }
}

【例子】wThread线程写入数据后，rThread线程读取数据，交替进行。

public class Resource
{
    private int context = 0;
    private bool readFlag = false;
    public void Write()
    {
        while (readFlag == true)//true:只能读,不能写(处于读状态).
            ;
        context++;
        Console.WriteLine("Writer:{0}", context);
        readFlag = true;
    }
    public void Read()
    {
        while (readFlag == false)//false:只能写,不能读(处于写状态).
            ;
        Console.WriteLine("Reader{0}", context);
        readFlag = false;
    }
}

以下代码与上面代码等价：

public class Resource
{
    private int context = 0;
    private bool readFlag = false;
    private static object obj = new object();

    public void Write()
    {
        Monitor.Enter(obj);
        if (readFlag == true)//true:只能读,不能写(处于读状态).
            Monitor.Wait(obj);//线程进入堵塞队列

        context++;
        Console.WriteLine("Writer:{0}", context);
        readFlag = true;

        Monitor.Pulse(obj);//从堵塞队列中出队
        Monitor.Exit(obj);
    }

    public void Read()
    {
        Monitor.Enter(obj);
        if (readFlag == false)//false:只能写,不能读(处于写状态).
            Monitor.Wait(obj);

        Console.WriteLine("Reader:{0}", context);
        readFlag = false;

        Monitor.Pulse(obj);
        Monitor.Exit(obj);
    }
}

6. 队列的应用

目前，在以银行营业大厅为代表的窗口行业中大量使用排队（叫号）系统，该系统完全模拟了人群排队全过程，通过取票进队、排队等待、叫号服务等功能，代替了人们站队的辛苦。

1. 问题描述

排队叫号软件的具体操作流程为：

顾客取服务序号

当顾客抵达服务大厅时，前往放置在入口处旁的取号机，并按一下其上的相应服务按钮，取号机会自动打印出一张服务单。单上显示服务号及该服务号前面正在等待服务的人数。

服务员工呼叫顾客

服务员工只需按一下其柜台上呼叫器的相应按钮，则顾客的服务号就会按顺序的显示在显示屏上，并发出“叮咚”和相关语音信息，提示顾客前往该窗口办事。当一位顾客办事完毕后，柜台服务员工只需按呼叫器相应键，即可自动呼叫下一位顾客。

2. 问题分析

编写程序模拟上面的工作过程，主要要求如下：

程序运行后，当看到“请点击触摸屏获取号码：”的提示时，只要按回车键，即可显示“您的号码是：XXX，您前面有YYY位”的提示，其中XXX是所获得的服务号码，YYY是在XXX之前来到的正在等待服务的人数。
用多线程技术模拟服务窗口（可模拟多个），具有服务员呼叫顾客的行为，假设每个顾客服务的时间是5000ms，时间到后，显示“请XXX号到ZZZ号窗口！”的提示。其中ZZZ是即将为客户服务的窗口号。

3. 代码实现

using System.Threading;
using LinearStruct;

namespace BankQueue
{
    public class BankQueue : LinkQueue<int>
    {
        public int Callnumber { get; private set; }
        public int GetCallnumber()
        {
            Callnumber++;
            return Callnumber;
        }

        public BankQueue()
        {
            Callnumber = 0;
        }
    }

    public class ServiceWindow
    {
        private BankQueue _bankQueue;
        public ServiceWindow(BankQueue bankQueue)
        {
            _bankQueue = bankQueue;
        }
        public void Service()
        {
            while (true)
            {
                lock (_bankQueue)
                {
                    Thread.Sleep(5000);
                    if (_bankQueue.Length != 0)
                    {
                        Console.WriteLine();
                        Console.WriteLine("请{0}号到{1}号窗口!",
                            _bankQueue.QueueFront, Thread.CurrentThread.Name);
                        _bankQueue.DeQueue();
                    }
                }
            }
        }
    }
}

客户端代码：

class Program
{
    public static void Main(string[] args)
    {
        int windowCount = 3;
        BankQueue bankQueue = new BankQueue();
        ServiceWindow[] serviceWindows = new ServiceWindow[windowCount];
        Thread[] serviceThread = new Thread[windowCount];
        for (int i = 0; i < windowCount; i++)
        {
            serviceWindows[i] = new ServiceWindow(bankQueue);
            serviceThread[i] = new Thread(serviceWindows[i].Service)
            {
                Name = (i + 1).ToString()
            };
            serviceThread[i].Start();
        }
        while (true)
        {
            Console.WriteLine("请点击触摸屏获取号码：");
            Console.ReadLine();
            int callnumber = bankQueue.GetCallnumber();
            Console.WriteLine("您的号码是：{0}，你前面有{1}位，请等待！",
                callnumber, bankQueue.Length);
            bankQueue.EnQueue(callnumber);
        }
    }
}