Stack and Query structures in computing are extremely fundamental and important. Then interviewing I expect candidate to fully understand this data structures and have experience using them.
As usual, a little bit of theory:
Push (T) – saves item in the stack
Pop() – takes item from the stack
EnQueue(T) - save item into the query
DeQueue() -takes item from the query
Microsoft provides both Stack and Queue object in its .NET System.Collections namespace. So let’s use reflector to pick on the way Microsoft .NET team implemented both this data structures. This is very common interview question, so knowing .NET implementation is extremely helpful.
In .NET both Stack and Queue are implemented with arrays:
The array implementation is simple and straight forward. The cursor called size indicates the last element in array which is current element of the stack. One thing worth mentioning is array reallocation which happens inside Push method. Initially Stack starts with array size of 10 elements : private const int _defaultCapacity = 10.
Every time stack reaches the size of the array, the array is recreated and the size is doubled.
This implementation is quite interesting. Firs of all, instead simply doubling size of the internal array Queue class gives you the ability to control array size grow via growFactor variable which can be passed through the constructor
public Queue(int capacity, float growFactor).
growFactor can have values between 1 and 10 with default value of 2, which give’s default value of internal variable _growFactor equalt to 200:
private int _growFactor = (int)(growFactor * 100);
So, with the default settings Queue starts with internal array size of 20 elements:
private const int _ShrinkThreshold = 20;
Every time queue cursor reaches array size internal array is recreated and size is increased on 200 elements. However there is minimal array grow size of 4 elements. This is enforces with the check on line 7 of Enqueue function: if (capacity < (this._array.Length + _MinimumGrow)).
Secondly, two internal variables:
private int _tail;private int _head;
are used to control access to the elements of the array. This is done to optimize performace and don’t shift all array on one element for each dequeue. Instead array reallocation happends only then array size changes and method setCapacity is called (line 10 of Enqueue method):