算法：基于 RingBuffer 的 Queue 实现

背景

如果基于数组实现队列，常见的选择是采用 RingBuffer，否则就需要移动数组元素。

RingBuffer

很容易看出 RingBuffer 的思想，这里就不赘述了。

您可以思考一个问题：图中表示的场景是一个空队列？还是一个满队列？答案是：单单维护 _header 和 _tail 还不足以判断，必须维护一个 _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 ArrayQueue<T>
10     {
11         private readonly int _maxSize;
12         private readonly T[] _items;
13         private int _count = 0;
14         private int _header = 0;
15         private int _tail;
16 
17         public ArrayQueue(int size)
18         {
19             _maxSize = size;
20             _items = new T[size];
21             _tail = _maxSize - 1;
22         }
23 
24         public void EnQueue(T item)
25         {
26             if (this.IsFull())
27             {
28                 throw new InvalidOperationException("队列已满");
29             }
30 
31             if (_tail == _maxSize - 1)
32             {
33                 _tail = -1;
34             }
35 
36             _items[++_tail] = item;
37 
38             _count++;
39         }
40 
41         public T DeQueue()
42         {
43             if (this.IsEmpty())
44             {
45                 throw new InvalidOperationException("队列已空");
46             }
47 
48             T item = _items[_header++];
49 
50             if (_header == _maxSize)
51             {
52                 _header = 0;
53             }
54 
55             _count--;
56 
57             return item;
58         }
59 
60         public T Peek()
61         {
62             if (this.IsEmpty())
63             {
64                 throw new InvalidOperationException("队列已空");
65             }
66 
67             return _items[_header];
68         }
69 
70         public bool IsFull()
71         {
72             return _count == _maxSize;
73         }
74 
75         public bool IsEmpty()
76         {
77             return _count == 0;
78         }
79     }
80 }

测试

 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 Program
10     {
11         static void Main(string[] args)
12         {
13             var queue = new Queues.ArrayQueue<int>(5);
14 
15             queue.EnQueue(1);
16             queue.EnQueue(2);
17             queue.EnQueue(3);
18             queue.EnQueue(4);
19             queue.EnQueue(5);
20             while (!queue.IsEmpty())
21             {
22                 Console.WriteLine(queue.DeQueue());
23             }
24 
25             queue.EnQueue(1);
26             queue.EnQueue(2);
27             queue.EnQueue(3);
28             queue.EnQueue(4);
29             queue.EnQueue(5);
30             while (!queue.IsEmpty())
31             {
32                 Console.WriteLine(queue.DeQueue());
33             }
34         }
35     }
36 }

备注

真正的基于数组的队列还需要考虑扩容，一般的策略是：成本的扩容。