Tag: Queue

Simple dynamic implementation of generic QUEUE in C#

using System;

public class LinkedQueue<T>
{
	private LinkedQueueNode<T> start;
	private LinkedQueueNode<T> end;

	public LinkedQueue()
	{
		this.Count = 0;
	}

	public int Count { get; private set; }

	public void Enqueue(T element)
	{
		var newElement = new LinkedQueueNode<T>(element);

		if (this.Count == 0)
		{
			this.start = this.end = newElement;
		}
		else
		{
			this.end.Next = newElement;
			this.end = newElement;
		}

		this.Count++;
	}

	public T Dequeue()
	{
		if (this.Count <= 0)
		{
			throw new InvalidOperationException("Queue is empty.");
		}

		var elementToReturn = this.start;
		this.start = this.start.Next;
		this.Count--;

		return elementToReturn.Value;
	}

	public T Peak()
	{
		if (this.Count <= 0)
		{
			throw new InvalidOperationException("Queue is empty.");
		}

		var currentElement = this.start.Value;

		return currentElement;
	}

	public T[] ToArray()
	{
		var arrToReturn = new T[this.Count];
		var currentNode = this.start;
		var arrIndex = 0;
		while (currentNode != null)
		{
			arrToReturn[arrIndex] = currentNode.Value;
			arrIndex++;
			currentNode = currentNode.Next;
		}

		return arrToReturn;
	}
	
	private class LinkedQueueNode<T>
	{
		public LinkedQueueNode(T value)
		{
			this.Value = value;
		}

		public T Value { get; private set; }

		public LinkedQueueNode<T> Next { get; set; }
	}
}

Simple static implementation of generic QUEUE in C#

public class CircularQueue<T>
{
	private const int InitialCapacity = 16;

	private T[] storage;

	private int capacity;
	private int startIndex;
	private int endIndex;

	public CircularQueue(int capacity = InitialCapacity)
	{
		this.Capacity = capacity;
		this.storage = new T[this.Capacity];
	}

	public int Count { get; private set; }

	private int Capacity
	{
		get
		{
			return this.capacity;
		}

		set
		{
			if (value <= 0)
			{
				throw new ArgumentOutOfRangeException(
					nameof(value),
					"Queue capacity should be a positive integer");
			}

			this.capacity = value;
		}
	}

	public void Enqueue(T element)
	{
		if (this.GrowNeeded())
		{
			this.Grow();
		}

		this.storage[this.endIndex] = element;
		this.endIndex = (this.endIndex + 1) % this.Capacity;
		this.Count++;
	}

	public T Dequeue()
	{
		if (this.Count <= 0)
		{
			throw new InvalidOperationException("Queue is empty.");
		}

		var element = this.storage[this.startIndex];
		this.storage[this.startIndex] = default(T);
		this.startIndex = (this.startIndex + 1) % this.Capacity;
		this.Count--;

		return element;
	}

	public T[] ToArray()
	{
		var resultArray = new T[this.Count];
		this.ResizeArrayStorage(resultArray);

		return resultArray;
	}

	private bool GrowNeeded()
	{
		var result = this.Count >= this.Capacity;

		return result;
	}

	private void Grow()
	{
		var newStorage = new T[this.Capacity * 2];
		this.ResizeArrayStorage(newStorage);
		this.startIndex = 0;
		this.endIndex = this.Capacity;
		this.Capacity *= 2;

		this.storage = newStorage;
	}

	private void ResizeArrayStorage(T[] array)
	{
		for (int i = 0; i < this.Count; i++)
		{
			var currentIndex = (this.startIndex + i) % this.Capacity;
			array[i] = this.storage[currentIndex];
		}
	}
}