Skip to content

Instantly share code, notes, and snippets.

@MaxWellHays
Created October 27, 2020 19:21
Show Gist options
  • Save MaxWellHays/82b451b9298378061e5cb98ef05e9fb8 to your computer and use it in GitHub Desktop.
Save MaxWellHays/82b451b9298378061e5cb98ef05e9fb8 to your computer and use it in GitHub Desktop.
C# Dequeue implementation
using System;
public class Dequeue<T>
{
public Dequeue(int capacity)
{
this.array = new T[capacity];
}
public Dequeue() : this(5)
{ }
T[] array;
public int Capacity => this.array.Length;
public int Count { get; private set; }
int _offset = 0;
public int Offset
{
get
{
return _offset;
}
set
{
_offset = NormalizeIndex(value);
}
}
public T PeekLast()
{
EnsureIsNotEmpty();
return array[NormalizeIndex(Offset + Count - 1)];
}
public T PopLast()
{
EnsureIsNotEmpty();
return array[NormalizeIndex(Offset + Count-- - 1)];
}
public T PeekFirst()
{
EnsureIsNotEmpty();
return array[NormalizeIndex(Offset)];
}
public T PopFirst()
{
EnsureIsNotEmpty();
Count--;
return array[NormalizeIndex(Offset++)];
}
public void PushLast(T last)
{
if (Count == Capacity)
{
Relocate();
}
array[NormalizeIndex(Offset + Count++)] = last;
}
public void PushFirst(T first)
{
if (Count == Capacity)
{
Relocate();
}
Count++;
array[NormalizeIndex(--Offset)] = first;
}
private int NormalizeIndex(int index)
{
return (index + Capacity) % Capacity;
}
private void EnsureIsNotEmpty()
{
if (Count == 0)
{
throw new InvalidOperationException("Dequeue is empty");
}
}
private void Relocate()
{
var newArray = new T[Capacity * 2];
for (int i = 0; i < Count; i++)
{
newArray[i] = array[NormalizeIndex(Offset + i)];
}
array = newArray;
Offset = 0;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment