Menu
Accessing items by index using ElementAt is obviously not a reasonable choice, as per .NET queue ElementAt performance.
Is there an alternative generic data structure that would be appropriate for this requirement?
My queue has a fixed capacity.
As per MSDN entry on the Queue class, "This class implements a queue as a circular array", yet it doesn't seem to expose any kind of indexing property.
Update: I have found C5's implementation of a CircularQueue. It seems to fit the bill, but I would prefer not to have to import another external library if possible.
213
Priority queue is a data structure in which data is stored on basis of its priority. In an Indexed Priority Queue, data is stored just like standard priority queue and along with this, the value of a data can be updated using its key.
To obtain the first element and the last element in the queue, the most straightforward way is to use indices. The first element in the queue has an index of 0. For the last item in the queue, we can use the -1 index. The minus sign indicates to Python to start counting items backward from the end of the queue.
Unlike ArrayList , there is no get(int index) method in Queue to retrieve the element at specified position.
It is used when you need a first-in, first-out access of items. When you add an item in the list, it is called enqueue, and when you remove an item, it is called deque. Queue . Contains(T) Method is used to check whether an element is in the Queue .
You can use a cyclic array. I.e. implement queue in array.
The implementation is pretty trivial, you don't need to use external library, just implement it yourself. A hint: it's easier to use m_beginIndex, m_nElements members than m_beginIndex, m_endIndex.
130
public class IndexedQueue<T>
{
T[] array;
int start;
int len;
public IndexedQueue(int initialBufferSize)
{
array = new T[initialBufferSize];
start = 0;
len = 0;
}
public void Enqueue(T t)
{
if (len == array.Length)
{
//increase the size of the cicularBuffer, and copy everything
T[] bigger = new T[array.Length * 2];
for (int i = 0; i < len; i++)
{
bigger[i] = array[(start + i) % len];
}
start = 0;
array = bigger;
}
array[(start + len) % array.Length] = t;
++len;
}
public T Dequeue()
{
var result = array[start];
start = (start + 1) % array.Length;
--len;
return result;
}
public int Count { get { return len; } }
public T this[int index]
{
get
{
return array[(start + index) % array.Length];
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
