C#数据结构之一（环形缓冲区FIFO）

数组模拟环形队列（这个正在使用-效果很好）

上一章说到的数组模拟队列存在的问题，问题分析并优化

• 目前数组使用一次就不能用，没有达到复用的效果
• 将这个数组使用算法，改进成一个环形的队列

对前面的数组模拟队列的优化，充分利用数组。因此将数组看做是一个环形的。（通过去模的方式来实现即可）

分析说明：

• 尾索引的下一个为头索引时，表示队列满。即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意（rear+1）%maxsize==front 满
• rear==front 空

实现思路如下：

• front指针含义调整，front指向队列第一个元素。也就是array[front]就是队列的第一个元素。front初始值=0。
• rear变量的含义调整，rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间作为约定。rear初始值=0。
• 当队列满时，条件是(rear + 1)% maxsize = front , 位满。（PS：rear +1是预留一个位置，不牺牲这个空间会导致无法判断队列空或者满，rear一直自增，也就是说rear是很有可能大于maxsieze的，比如maxsize=5，rear=10，因为rear被加到10，此时rear的实际位置是0。取模式保证党front为0时，rear+1取模为0与front相等）
• 当队列空是，条件是rear==front 。
• 有效的数据个数，(raer + maxsize - front)%maxsize。（为什么要取模，因为是环形同时有rear可能是最大的然后跑到最前面来；假如：rear=1，front=0，maxsize=10 再套入公式中 (1+10-0)%10=1 有效数据为1）

代码实现

public class CircleArrayQueue
{
    //队列最大值
    private int _maxSize;
    //队列头部
    private int _front;
    //队列尾部
    private int _rear;
    //存储值的数组
    private int[] _tempArray;
    
    public CircleArrayQueue(int maxSize)
    {
        Console.WriteLine($"MaxSize : { maxSize }");
        _maxSize = maxSize;
        _tempArray = new int[_maxSize];
        //front指向队列第一个元素
        _front = 0;
        //rear指向队列的最后一个元素的后一个位置
        _rear = 0;
    }

    public bool IsFull()
    {
        return (_rear + 1) % _maxSize == _front;
    }

    public bool IsEmpty()
    {
        return _rear == _front;
    }

    /// <summary>
    /// 有效数据个数
    /// </summary>
    /// <returns></returns>
    public int Num() 
    {
        return (_rear + _maxSize - _front) % _maxSize;
    }

    public void EnQueue(int val)
    {
        if (IsFull())
        {
            Console.WriteLine("队列已满，无法加入数据！");
            return;
        }
        //直接插入数据
        _tempArray[_rear] = val;
        //_rear后移一位，这里必须考虑取模
        _rear = (_rear + 1) % _maxSize;
    }

    public int DeQueue()
    {
        if (IsEmpty())
        {
            throw new Exception("队列是空的，无法取出数据！");
        }
        //这里需要分析出front是指向队列的第一个元素
        //1.先把front对应的值保留到一个临时变量
        //2.将front后移
        //3.将临时保存的变量返回

        var tempVal = _tempArray[_front];
        _front = (_front + 1) % _maxSize;
        return tempVal;
    }

    public void ShowAll()
    {
        if (IsEmpty())
        {
            Console.WriteLine("队列是空的!");
            return;
        }
        Console.WriteLine("显示队列所有内容：");
        for (int i = _front; i < _front + Num(); i++)
        {
            Console.Write($"{ _tempArray[i % _maxSize] }\t");
        }
        Console.WriteLine();
    }

    public void PeekFirst()
    {
        if (IsEmpty())
        {
            Console.WriteLine("队列是空的，无法取出数据！");
            return;
        }

        Console.WriteLine($"查看第一个值:{ _tempArray[_front] }");
    }
}

代码调用

class Program
{
        static void Main(string[] args)
        {
            //MySparseArray sparseArray = new MySparseArray();
            //sparseArray.Print();    
        try
        {
            CircleArrayQueue queue = new CircleArrayQueue(4);
            queue.EnQueue(97);
            queue.EnQueue(98);
            queue.EnQueue(200);
            queue.EnQueue(1000);
            //查看第一个值
            queue.PeekFirst();
            //显示队列里所有的内容
            queue.ShowAll();
            //取出一个值
            Console.WriteLine($"取出一个值:{ queue.DeQueue() }");
            Console.WriteLine($"取出一个值:{ queue.DeQueue() }");
            Console.WriteLine($"取出一个值:{ queue.DeQueue() }");
            queue.PeekFirst();
            queue.EnQueue(200);
            queue.ShowAll();
        }
        catch (Exception ex)
        {
            Console.WriteLine(ex.Message);
        }

        Console.Read();
    }
}

运行效果

C#串口数据处理–环形缓冲区-FIFO

注意：这个FIFO无效，还不知什么原因

一、FIFO环形缓冲区初始化

static int MAX_BUFFER_LEN = 1024;//定义缓冲区大小
FIFO receiveBufferManager = new FIFO(MAX_BUFFER_LEN);

二、串口接收事件中添加写入环形缓冲

int num = serialPort1.BytesToRead;      //获取接收缓冲区中的字节数
               byte[] received_buf = new byte[num];    //声明一个大小为num的字节数据用于存放读出的byte型数据
               serialPort1.Read(received_buf, 0, num);   //读取接收缓冲区中num个字节到byte数组中
               if (num > 0)
               {
                    receiveBufferManager.WriteBuffer(received_buf, 0,num);
               }

三、开一个线程解析数据，测试中串口以10ms的周期发送大量数据，然后在线程中以1s的速度去解析数据，数据依然不会丢失。

private void serialPort1_DataReceived1(object o)
        {
            try
            {
                byte[] freame_byte = new byte[1024];
                byte[] freame_byte1 = new byte[1024];
                while (true)
                {
                    if (receiveBufferManager.GetDataCount() > 0)
                    {
                        receiveBufferManager.ReadBuffer(freame_byte, 0, 5);
                        receiveBufferManager.ReadBuffer(freame_byte1, 0,freame_byte[2]);
                        Console.Write("数据=");
                        for (int i = 0; i < freame_byte[2]; i++)
                        {
                            Console.Write("{0:X000} ", freame_byte1[i]);
                        }
                        Console.WriteLine("");
                         receiveBufferManager.Clear(freame_byte[2]);
                    }
                    else { Console.WriteLine("缓冲区没有数据"); }
                    Thread.Sleep(1000);
               }
            }
            catch
            {
 
            }
        }

四、环形缓冲区实现类

public class RingBufferManager
{
    public byte[] Buffer { get; set; } // 存放内存的数组
    public int DataCount { get; set; } // 写入数据大小
    public int DataStart { get; set; } // 数据起始索引
    public int DataEnd { get; set; }   // 数据结束索引
    public RingBufferManager(int bufferSize)
    {
        DataCount = 0; DataStart = 0; DataEnd = 0;
        Buffer = new byte[bufferSize];
    }
 
    public byte this[int index]
    {
        get
        {
            if (index >= DataCount) throw new Exception("环形缓冲区异常，索引溢出");
            if (DataStart + index < Buffer.Length)
            {
                return Buffer[DataStart + index];
            }
            else 
            {
                return Buffer[(DataStart + index) - Buffer.Length];
            }
        }
    }
 
    public int GetDataCount() // 得到当前写入的字节数
    {
        return DataCount;
    }
 
    public int GetReserveCount() // 得到剩余的字节数
    {
        return Buffer.Length - DataCount;
    }
 
    public void Clear()
    {
        DataCount = 0;
    }
 
    public void Clear(int count) // 清空指定大小的数据
    {
        if (count >= DataCount) // 若是须要清理的数据大于现有数据大小，则所有清理
        {
            DataCount = 0;
            DataStart = 0;
            DataEnd = 0;
        }
        else
        {
            if (DataStart + count >= Buffer.Length)
            {
                DataStart = (DataStart + count) - Buffer.Length;
            }
            else 
            {
                DataStart += count;
            }
            DataCount -= count;
        }
    }
 
    public void WriteBuffer(byte[] buffer, int offset, int count)
    {
        Int32 reserveCount = Buffer.Length - DataCount;
        if (reserveCount >= count)                          // 可用空间够使用
        {
            if (DataEnd + count < Buffer.Length)            // 数据没到结尾
            {
                Array.Copy(buffer, offset, Buffer, DataEnd, count);
                DataEnd += count;
                DataCount += count;
            }
            else           //  数据结束索引超出结尾 循环到开始
            {
                System.Diagnostics.Debug.WriteLine("缓存从新开始....");
                Int32 overflowIndexLength = (DataEnd + count) - Buffer.Length;      // 超出索引长度
                Int32 endPushIndexLength = count - overflowIndexLength;             // 填充在末尾的数据长度
                Array.Copy(buffer, offset, Buffer, DataEnd, endPushIndexLength);
                DataEnd = 0;
                offset += endPushIndexLength;
                DataCount += endPushIndexLength;
                if (overflowIndexLength != 0)
                {
                    Array.Copy(buffer, offset, Buffer, DataEnd, overflowIndexLength);
                }
                DataEnd += overflowIndexLength;                                     // 结束索引
                DataCount += overflowIndexLength;                                   // 缓存大小
            }
        }
        else 
        {
            // 缓存溢出，不处理
        }
    }
 
    public void ReadBuffer(byte[] targetBytes,Int32 offset, Int32 count) 
    {
        if (count > DataCount) throw new Exception("环形缓冲区异常，读取长度大于数据长度");
        Int32 tempDataStart = DataStart;
        if (DataStart + count < Buffer.Length)
        {
            Array.Copy(Buffer, DataStart, targetBytes, offset, count);
        }
        else 
        {
            Int32 overflowIndexLength = (DataStart + count) - Buffer.Length;    // 超出索引长度
            Int32 endPushIndexLength = count - overflowIndexLength;             // 填充在末尾的数据长度
            Array.Copy(Buffer, DataStart, targetBytes, offset, endPushIndexLength);
            
            offset += endPushIndexLength;
            
            if (overflowIndexLength != 0)
            {
                Array.Copy(Buffer, 0, targetBytes, offset, overflowIndexLength);
            }
        }
    }
 
 
    public void WriteBuffer(byte[] buffer)
    {
        WriteBuffer(buffer, 0, buffer.Length);
    }
 
}

---

相关链接（侵删）

1. c#环形队列
2. C#串口数据处理–环形缓冲区-FIFO

---

=================我是分割线=================

欢迎到公众号来唠嗑: