背景

上篇实现了一个简单的队列，内部使用了 _count 计数，本文采用另外一种模式，不用 _count 计数。

RingBuffer

不用 _count 计数的话，为了区分队列的满和空，需要在数组中预留一格，如下图就代表了一个满队列。

ArrayQueue

代码

1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6  7 namespace DataStuctureStudy.Queues 8 { 9     public class ArrayQueue2
     
      10     {11         private readonly int _maxSize;12         private readonly T[] _items;13         private int _header = 0;14         private int _tail = -1;15 16         public ArrayQueue2(int size)17         {18             _maxSize = size + 1;19             _items = new T[_maxSize];20         }21 22         public void EnQueue(T item)23         {24             if (this.IsFull())25             {26                 throw new InvalidOperationException("队列已满");27             }28 29             if (_tail == _maxSize - 1)30             {31                 _tail = -1;32             }33 34             _items[++_tail] = item;35         }36 37         public T DeQueue()38         {39             if (this.IsEmpty())40             {41                 throw new InvalidOperationException("队列已空");42             }43 44             T item = _items[_header++];45 46             if (_header == _maxSize)47             {48                 _header = 0;49             }50 51             return item;52         }53 54         public T Peek()55         {56             if (this.IsEmpty())57             {58                 throw new InvalidOperationException("队列已空");59             }60 61             return _items[_header];62         }63 64         public bool IsFull()65         {66             return67                (_header + _maxSize - 2 == _tail)68                ||69                (_tail + 2 == _header);70         }71 72         public bool IsEmpty()73         {74             return75                (_tail + 1 == _header)76                ||77                (_header == 0 && _tail == _maxSize - 1);78         }79 80         public int Size()81         {82             if (_tail >= _header)83             {84                 return _tail - _header + 1;85             }86             else87             {88                 return (_maxSize - _header) + (_tail + 1);89             }90         }91     }92 }
     

测试

1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6  7 namespace DataStuctureStudy 8 { 9     class Program10     {11         static void Main(string[] args)12         {13             var queue = new Queues.ArrayQueue2
     
      (5);14 15             queue.EnQueue(1);16             queue.EnQueue(2);17             queue.EnQueue(3);18             queue.EnQueue(4);19             queue.EnQueue(5);20             Console.WriteLine(queue.Size());21             while (!queue.IsEmpty())22             {23                 Console.WriteLine(queue.DeQueue());24             }25 26             queue.EnQueue(1);27             queue.EnQueue(2);28             queue.EnQueue(3);29             queue.EnQueue(4);30             queue.EnQueue(5);31             Console.WriteLine(queue.Size());32             while (!queue.IsEmpty())33             {34                 Console.WriteLine(queue.DeQueue());35             }36         }37     }38 }