算法：基于 RingBuffer 的 Queue 实现《续》

背景

上篇实现了一个简单的队列，内部使用了 _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<T>
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             return
67                (_header + _maxSize - 2 == _tail)
68                ||
69                (_tail + 2 == _header);
70         }
71 
72         public bool IsEmpty()
73         {
74             return
75                (_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             else
87             {
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 Program
10     {
11         static void Main(string[] args)
12         {
13             var queue = new Queues.ArrayQueue2<int>(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 }