Circular Queue

Definition
An implementation of a limited collection with specified a fixed numbers of items in which only the earliest added item may be accessed using an array.
Basic operations are add (to the tail; or the last item of list) or enqueue; and throw (from the head; or the first item of a list) or dequeue. Also known as “first-in, first-out” or FIFO. And list is a collection of items accessible one after another beginning at the head and ending at the tail.

Above visually shows that the queue has no real end and it can loop around the queue. However, since memory is never physically created as a ring, a linear representation is generally used as is done below.

Illustrations
1. A circular queue first starts empty and of some predefined length. For example, circular queue with length 7.

2. Enqueue the defined circular queue until 7 times, then it is completely full.

3. The head is first element; tail is last element.
4. When dequeue was execute, the first element “6” will throw; and head index will increment.
5. Head index will increment and back to first when equals with defined length of circular queue.

Implementations (with C# .NET 3.5)
Defined length of circular queue directly when instantiate the object.

  1: /// <summary>Default constructor.</summary>
  2: /// <exception cref="System.ArgumentOutOfRangeException"></exception>
  3: /// <param name="capacity">The number of elements that the new list can initially store.</param>
  4: public clsCircularQueue(int capacity)
  5: {
  6:      if (capacity < 0)
  7:          throw new ArgumentOutOfRangeException("capacity", "Cannot create an array with a negative size.");
  8:
  9:      //...other code.
 10: }

Enqueue implementation or add member/ element.

  1: /// <summary>Adds the integer value to the tail of Circular Queue.</summary>
  2: /// <exception cref="System.IndexOutOfRangeException"></exception>
  3: /// <param name="value"></param>
  4: public void Enqueue(int value)
  5: {
  6:     if (this.Length == 0)
  7:         throw new IndexOutOfRangeException();
  8:
  9:     if (this.tail >= this.items.Length)
 10:         this.tail = 0;
 11:            
 12:     this.items[this.tail] = value;
 13:     this.tail++;
 14: }

Dequeue implementation or throw member/ element.

  1: /// <summary>Returns the integer value at the head positon of Circular Queue.</summary>
  2: /// <exception cref="System.MissingMemberException"></exception>
  3: /// <returns></returns>
  4: public int Dequeue()
  5: {
  6:     int? result = this.items[this.head];
  7:
  8:     if (!result.HasValue)
  9:         throw new MissingMemberException();
 10:
 11:     this.head++;
 12:     if (this.head >= this.Length)
 13:         this.head = 0;
 14:
 15:     return result.Value;
 16: }

Because that class was inherit from IEnumerable<T>, so we must implemented the IEnumerator<T>. In this case, we implemented own IEnumerator<T>, called clsEnumeratorCircularQueue.

The MoveNext implementation of that custom IEnumerator.

  1: /// <summary>Advances the enumerator to the next element of the collection.</summary>
  2: /// <returns></returns>
  3: public bool MoveNext()
  4: {
  5:     try
  6:     {
  7:         this.counter++;
  8:         if (counter > this.circularQueue.Length)
  9:         {
 10:             this.current = null;
 11:             this.counter = 0;
 12:             return false;
 13:         }
 14:
 15:         this.current = this.circularQueue.Dequeue();
 16:         return true;
 17:     }
 18:     catch
 19:     {
 20:         return false;
 21:     }
 22: }

Lets test!

  1: ...
  2: int capacity = 8;
  3: Console.WriteLine("Capacity: " + capacity);
  4: clsCircularQueue circularQueue = new clsCircularQueue(capacity);
  5: for (int i = 1; i <= 10; i++)
  6:     circularQueue.Enqueue(i);
  7:
  8: Console.WriteLine("Iteration with foreach.");
  9: foreach (int value in circularQueue)
 10:     Console.Write(value + " | ");
 11: ...

The result:

The complete source-code:

  1: using System;
  2: using System.Collections.Generic;
  3:
  4: namespace Ronald.CircularQueue
  5: {
  6:     /// <summary>Represent circular queue.</summary>
  7:     public sealed class clsCircularQueue : IEnumerable<Int32>
  8:     {
  9:         #region Declarations
 10:
 11:         private readonly int?[] items = null;
 12:         private int head = 0;
 13:         private int tail = 0;
 14:
 15:         #endregion
 16:
 17:         #region Constructors
 18:
 19:         /// <summary>Private constructor.</summary>
 20:         /// <exception cref="System.NotSupportedException"></exception>
 21:         private clsCircularQueue()
 22:         {
 23:             throw new NotSupportedException("Use constructor with parameter that pass the capacity.");
 24:         }
 25:
 26:         /// <summary>Default constructor.</summary>
 27:         /// <exception cref="System.ArgumentOutOfRangeException"></exception>
 28:         /// <param name="capacity">The number of elements that the new list can initially store.</param>
 29:         public clsCircularQueue(int capacity)
 30:         {
 31:             if (capacity < 0)
 32:                 throw new ArgumentOutOfRangeException("capacity", "Cannot create an array with a negative size.");
 33:
 34:             this.items = new int?[capacity];
 35:         }
 36:
 37:         #endregion
 38:
 39:         /// <summary>Gets a 32-bit integer that represents 
 40:         /// the total number of elements in all the dimensions of the System.Array.</summary>
 41:         public int Length { get { return this.items.Length; } }
 42:
 43:         /// <summary>Adds the integer value to the tail of Circular Queue.</summary>
 44:         /// <exception cref="System.IndexOutOfRangeException"></exception>
 45:         /// <param name="value"></param>
 46:         public void Enqueue(int value)
 47:         {
 48:             if (this.Length == 0)
 49:                 throw new IndexOutOfRangeException();
 50:
 51:             if (this.tail >= this.items.Length)
 52:                 this.tail = 0;
 53:            
 54:             this.items[this.tail] = value;
 55:             this.tail++;
 56:         }
 57:
 58:         /// <summary>Returns the integer value at the head positon of Circular Queue.</summary>
 59:         /// <exception cref="System.MissingMemberException"></exception>
 60:         /// <returns></returns>
 61:         public int Dequeue()
 62:         {
 63:             int? result = this.items[this.head];
 64:
 65:             if (!result.HasValue)
 66:                 throw new MissingMemberException();
 67:
 68:             this.head++;
 69:             if (this.head >= this.Length)
 70:                 this.head = 0;
 71:
 72:             return result.Value;
 73:         }
 74:
 75:         #region IEnumerable<Int32> Members
 76:
 77:         /// <summary>Returns an enumerator that iterates through the Circular Queue.</summary>
 78:         /// <returns></returns>
 79:         public IEnumerator<Int32> GetEnumerator()
 80:         {
 81:             return new clsEnumeratorCircularQueue(this);
 82:         }
 83:
 84:         #endregion
 85:
 86:         #region IEnumerable Members
 87:
 88:         /// <summary>
 89:         /// 
 90:         /// </summary>
 91:         /// <returns></returns>
 92:         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
 93:         {
 94:             throw new Exception("The method or operation is not implemented.");
 95:         }
 96:
 97:         #endregion
 98:
 99:         /// <summary>Supports a circular iteration over a collection.</summary>
100:         public sealed class clsEnumeratorCircularQueue : IEnumerator<Int32>
101:         {
102:             #region Declarations
103:
104:             private readonly clsCircularQueue circularQueue = null;
105:             private int? current = null;
106:             private int counter = 0;
107:
108:             #endregion
109:
110:             #region Constructors
111:
112:             /// <summary>Private constructor.</summary>
113:             /// <exception cref="System.NotSupportedException"></exception>
114:             private clsEnumeratorCircularQueue()
115:             {
116:                 throw new NotSupportedException("Use constructor with parameter that pass the capacity.");
117:             }
118:
119:             /// <summary>Default constructor.</summary>
120:             /// <exception cref="System.ArgumentNullException"></exception>
121:             /// <param name="circularQueue"></param>
122:             public clsEnumeratorCircularQueue(clsCircularQueue circularQueue)
123:             {
124:                 if (circularQueue == null)
125:                     throw new ArgumentNullException("circularQueue");
126:
127:                 this.circularQueue = circularQueue;
128:                 this.current = this.circularQueue.items[this.circularQueue.head];
129:             }
130:
131:             #endregion
132:
133:             #region IEnumerator<Int32> Members
134:
135:             /// <summary>Gets the element in the collection at 
136:             /// the current position of the enumerator.</summary>
137:             /// <exception cref="System.MissingMemberException"></exception>
138:             public int Current
139:             {
140:                 get
141:                 {
142:                     if (!this.current.HasValue)
143:                     {
144:                         this.counter = 0;
145:                         throw new MissingMemberException();
146:                     }
147:
148:                     return this.current.Value;
149:                 }
150:             }
151:
152:             #endregion
153:
154:             #region IDisposable Members
155:
156:             /// <summary>Performs application-defined tasks associated with 
157:             /// freeing, releasing, or resetting unmanaged resources.</summary>
158:             public void Dispose()
159:             { }
160:
161:             #endregion
162:
163:             #region IEnumerator Members
164:
165:             /// <summary>
166:             /// 
167:             /// </summary>
168:             object System.Collections.IEnumerator.Current
169:             {
170:                 get { throw new Exception("The method or operation is not implemented."); }
171:             }
172:
173:             /// <summary>Advances the enumerator to the next element of the collection.</summary>
174:             /// <returns></returns>
175:             public bool MoveNext()
176:             {
177:                 try
178:                 {
179:                     this.counter++;
180:                     if (counter > this.circularQueue.Length)
181:                     {
182:                         this.current = null;
183:                         this.counter = 0;
184:                         return false;
185:                     }
186:
187:                     this.current = this.circularQueue.Dequeue();
188:                     return true;
189:                 }
190:                 catch
191:                 {
192:                     return false;
193:                 }
194:             }
195:
196:             /// <summary>Sets the enumerator to its initial position, 
197:             /// which is before the first element in the collection.</summary>
198:             public void Reset()
199:             {
200:                 this.circularQueue.head = 0;
201:                 this.circularQueue.tail = 0;
202:             }
203:
204:             #endregion
205:         }
206:        
207:     }
208: }
209: 

References:
http://en.wikipedia.org/wiki/Circular_buffer
http://www.itl.nist.gov/div897/sqg/dads/