A ring buffer (a circular queue) is a FIFO data structure of a fixed size. A few properties of the ring buffer from Wikipedia:

  • it does not need to have its elements shuffled around when one is consumed
  • it is well-suited as a FIFO buffer while a standard, non-circular buffer is well suited as a LIFO buffer
  • it makes a good implementation strategy for a queue that has fixed maximum size
  • all queue operations are constant time

The following implementation uses an array with circular wrap-around. It throws an exception when the user tries to write to a full buffer or when the user tries to read from an empty buffer.

using System;

namespace ConsoleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            RingBuffer b = new RingBuffer(3);

            b.Write("A");
            Console.Write("Write A:  ");
            b.ShowItems();

            b.Write("B");
            Console.Write("Write B:  ");
            b.ShowItems();

            b.Write("C");
            Console.Write("Write C:  ");
            b.ShowItems();

            Console.Write("Read  {0}:  ", b.Read());
            b.ShowItems();

            b.Write("D");
            Console.Write("Write D:  ");
            b.ShowItems();

            Console.Write("Read  {0}:  ", b.Read());
            b.ShowItems();

            Console.Write("Read  {0}:  ", b.Read());
            b.ShowItems();

            b.Write("E");
            Console.Write("Write E:  ");
            b.ShowItems();

            Console.Write("Read  {0}:  ", b.Read());
            b.ShowItems();

            Console.Write("Read  {0}:  ", b.Read());
            b.ShowItems();

            b.Write("F");
            Console.Write("Write F:  ");
            b.ShowItems();

            b.Write("G");
            Console.Write("Write G:  ");
            b.ShowItems();

            b.Write("H");
            Console.Write("Write H:  ");
            b.ShowItems();

            Console.Write("Read  {0}:  ", b.Read());
            b.ShowItems();

            Console.Write("Read  {0}:  ", b.Read());
            b.ShowItems();

            Console.ReadKey();
        }

        class RingBuffer
        {
            private T[] a; // buffer entries
            private int N; // buffer size

            private int head; // the index of the first element
            private int tail; // the index of the last element

            public bool IsEmpty { get { return N == 0; } }
            public int Size { get { return N; } }

            public RingBuffer(int capacity)
            {
                a = new T[capacity];
                head = 0;
                tail = 0;
            }

            // Add an item to the end of buffer. 
            // Throw an exception if the buffer is full.
            public void Write(T item)
            {
                if (N == a.Length)
                    throw new IndexOutOfRangeException("Buffer is full");

                a[tail] = item;

                if (++tail > a.Length - 1)
                    tail = 0;

                ++N;
            }

            public T Read()
            {
                if (N == 0)
                    throw new IndexOutOfRangeException("Buffer is empty");

                T item = a[head];

                a[head] = default(T);

                if (++head > a.Length - 1)
                    head = 0;

                --N;

                return item;
            }

            public void ShowItems()
            {
                for (int i = 0; i < a.Length; ++i)
                {
                    Console.Write("{0} ", (a[i] != null ? a[i].ToString() : "."));
                }
                Console.WriteLine("     H={0} T={1}", head, tail);
                Console.WriteLine("");
            }
        }
    }
}

Output:

Write A:  A . .      H=0 T=1

Write B:  A B .      H=0 T=2

Write C:  A B C      H=0 T=0

Read  A:  . B C      H=1 T=0

Write D:  D B C      H=1 T=1

Read  B:  D . C      H=2 T=1

Read  C:  D . .      H=0 T=1

Write E:  D E .      H=0 T=2

Read  D:  . E .      H=1 T=2

Read  E:  . . .      H=2 T=2

Write F:  . . F      H=2 T=0

Write G:  G . F      H=2 T=1

Write H:  G H F      H=2 T=2

Read  F:  G H .      H=0 T=2

Read  G:  . H .      H=1 T=2