c井Queue源碼解析

Queue<T>是c#的泛型隊列類，跟Stack、List等容器一樣，它的內部也是由數組來實現的，主要為使用者提供了Enqueue()、Peek()、Dequeue()、Contains()、GetElement()等介面來進行使用。下面我們會逐個來進行分析，先來看下Queue的類頭：

public class Queue<T> : IEnumerable<T>,

System.Collections.ICollection,

IReadOnlyCollection<T> {

private T[] _array;

private int _head; // First valid element in the queue

private int _tail; // Last valid element in the queue

private int _size; // Number of elements.

private int _version;

#if !SILVERLIGHT

[NonSerialized]

#endif

private Object _syncRoot;

private const int _MinimumGrow = 4;

private const int _ShrinkThreshold = 32;

private const int _GrowFactor = 200; // double each time

private const int _DefaultCapacity = 4;

static T[] _emptyArray = new T[0];

// Creates a queue with room for capacity objects. The default initial

// capacity and grow factor are used.

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Queue"]/*" />

public Queue() {

_array = _emptyArray;

}

// Creates a queue with room for capacity objects. The default grow factor

// is used.

//

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Queue1"]/*" />

public Queue(int capacity) {

if (capacity < 0)

ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);

_array = new T[capacity];

_head = 0;

_tail = 0;

_size = 0;

}

可以看到定義了一個泛型數組_array，_head為隊列頭部在數組中的索引 ，_tail為尾部索引看， _size為隊列大小，_version用來記錄版本號(用來在foreach的時候進行判斷，任何對棧的更改都會使版本號+1，如果循環中版本號有變化，會拋出異常)。_DefaultCapacity為默認在第一次為棧添加元素時創建的數組大小。Queue默認的無參構造函數會將數組_array指向靜態數組_emptyArray，也可以在創建Queue時指定棧數組的初始大小，這樣Queue會直接創建相應大小的數組元素(這樣的好處是：在已知隊列大小的情況下，指定隊列數組的大小，可以減少數組空間不夠時，重新創建新的數組和拷貝的消耗)。

接下來我們先來看看Enqueue函數：

public void Enqueue(T item) {

if (_size == _array.Length) {

int newcapacity = (int)((long)_array.Length * (long)_GrowFactor / 100);

if (newcapacity < _array.Length + _MinimumGrow) {

newcapacity = _array.Length + _MinimumGrow;

}

SetCapacity(newcapacity);

}

_array[_tail] = item;

_tail = (_tail + 1) % _array.Length;

_size++;

_version++;

}

private void SetCapacity(int capacity) {

T[] newarray = new T[capacity];

if (_size > 0) {

if (_head < _tail) {

Array.Copy(_array, _head, newarray, 0, _size);

} else {

Array.Copy(_array, _head, newarray, 0, _array.Length - _head);

Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);

}

}

_array = newarray;

_head = 0;

_tail = (_size == capacity) ? 0 : _size;

_version++;

}

添加到隊列末時會先進行判斷，如果當前隊列已滿則分配兩倍大小新內存塊，_GrowFactor值為200（感覺有點蠢，跟List<T>一樣直接*2不就完了嗎？而且計算結束後還得判斷是否小於最小值，因為如果第一次的話0*2=0，其實完全可以這樣寫：int newcapacity = _size == 0 ? _DefaultCapacity : _size * 2;）。接著把item放入_array的「尾」部，尾部索引的值等於自增再對_array長度進行取余，並對_size，_version自增。

SetCapacity函數重新申請分配了capacity大小的內存，並對原有數據進行了拷貝。

看到這裡你可能會有點疑惑，_tail+1後為什麼要對_array進行取余？Setcapacity函數為什麼要判斷_head和_tail的大小，難道隊列頭索引還會大於隊列尾索引？

沒錯！這是為了最大化的利用數組_array。因為隊列是個先進先出的容器，而且數組的大小又是固定的，所以意味著每次取出隊列頭部數據那麼對應的_array[_head]就是垃圾數據了，這時候會把這塊內存重置為默認數據。之所以不採用取出頭數據就數組整體前移的操作是因為當隊列的數據比較大時，數組的前移代價有可能是非常大的。而用索引的方式靈活的指向，對性能幾乎沒影響，唯一要做的就是處理好隊列頭尾索引_head、_tail之間的關係。因為其有序性，所以我們在_head<_tail和在_head>_tail進行不同的處理：當_head<_tail時，隊列有效數據為_array數組中一塊有序連續空間，所以直接從_head處拷貝_szie個有效元素到新內存空間。當_head>_tail時，說明添加元素時，_array的末尾已滿，但是_array頭卻還有空間可用於存放，如圖：

所以複製的時候要分兩部，先複製_head到_array尾的數據，再複製_array頭到_tail的數據。

接下來再看看Dequeue函數：

public T Dequeue() {

if (_size == 0)

ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);

T removed = _array[_head];

_array[_head] = default(T);

_head = (_head + 1) % _array.Length;

_size--;

_version++;

return removed;

}

public T Peek() {

if (_size == 0)

ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);

return _array[_head];

}

了解了上面說的數據存儲後再看這些操作就很簡單了：取出隊列頭，內存數據初始化，_head自增並對_array長度取余，長度減一，版本號自增並返回隊列頭數據。

Peek函數的區別就是只是取出隊列頭的數據，但是並不做刪除操作。

最後附上Queue全部源碼：

namespace System.Collections.Generic {

using System;

using System.Diagnostics;

using System.Diagnostics.CodeAnalysis;

using System.Security.Permissions;

// A simple Queue of generic objects. Internally it is implemented as a

// circular buffer, so Enqueue can be O(n). Dequeue is O(1).

[DebuggerTypeProxy(typeof(System_QueueDebugView<>))]

[DebuggerDisplay("Count = {Count}")]

#if !SILVERLIGHT

[Serializable()]

#endif

[System.Runtime.InteropServices.ComVisible(false)]

public class Queue<T> : IEnumerable<T>,

System.Collections.ICollection,

IReadOnlyCollection<T> {

private T[] _array;

private int _head; // First valid element in the queue

private int _tail; // Last valid element in the queue

private int _size; // Number of elements.

private int _version;

#if !SILVERLIGHT

[NonSerialized]

#endif

private Object _syncRoot;

private const int _MinimumGrow = 4;

private const int _ShrinkThreshold = 32;

private const int _GrowFactor = 200; // double each time

private const int _DefaultCapacity = 4;

static T[] _emptyArray = new T[0];

// Creates a queue with room for capacity objects. The default initial

// capacity and grow factor are used.

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Queue"]/*" />

public Queue() {

_array = _emptyArray;

}

// Creates a queue with room for capacity objects. The default grow factor

// is used.

//

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Queue1"]/*" />

public Queue(int capacity) {

if (capacity < 0)

ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);

_array = new T[capacity];

_head = 0;

_tail = 0;

_size = 0;

}

// Fills a Queue with the elements of an ICollection. Uses the enumerator

// to get each of the elements.

//

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Queue3"]/*" />

public Queue(IEnumerable<T> collection)

{

if (collection == null)

ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);

_array = new T[_DefaultCapacity];

_size = 0;

_version = 0;

using(IEnumerator<T> en = collection.GetEnumerator()) {

while(en.MoveNext()) {

Enqueue(en.Current);

}

}

}

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Count"]/*" />

public int Count {

get { return _size; }

}

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.IsSynchronized"]/*" />

bool System.Collections.ICollection.IsSynchronized {

get { return false; }

}

Object System.Collections.ICollection.SyncRoot {

get {

if( _syncRoot == null) {

System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);

}

return _syncRoot;

}

}

// Removes all Objects from the queue.

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Clear"]/*" />

public void Clear() {

if (_head < _tail)

Array.Clear(_array, _head, _size);

else {

Array.Clear(_array, _head, _array.Length - _head);

Array.Clear(_array, 0, _tail);

}

_head = 0;

_tail = 0;

_size = 0;

_version++;

}

// CopyTo copies a collection into an Array, starting at a particular

// index into the array.

//

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.CopyTo"]/*" />

public void CopyTo(T[] array, int arrayIndex)

{

if (array==null) {

ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);

}

if (arrayIndex < 0 || arrayIndex > array.Length) {

ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_Index);

}

int arrayLen = array.Length;

if (arrayLen - arrayIndex < _size) {

ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);

}

int numToCopy = (arrayLen - arrayIndex < _size) ? (arrayLen - arrayIndex) : _size;

if (numToCopy == 0) return;

int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;

Array.Copy(_array, _head, array, arrayIndex, firstPart);

numToCopy -= firstPart;

if (numToCopy > 0) {

Array.Copy(_array, 0, array, arrayIndex+_array.Length - _head, numToCopy);

}

}

void System.Collections.ICollection.CopyTo(Array array, int index)

{

if (array == null) {

ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);

}

if (array.Rank != 1) {

ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);

}

if( array.GetLowerBound(0) != 0 ) {

ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);

}

int arrayLen = array.Length;

if (index < 0 || index > arrayLen) {

ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);

}

if (arrayLen - index < _size) {

ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);

}

int numToCopy = (arrayLen-index < _size) ? arrayLen-index : _size;

if (numToCopy == 0) return;

try {

int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;

Array.Copy(_array, _head, array, index, firstPart);

numToCopy -= firstPart;

if (numToCopy > 0) {

Array.Copy(_array, 0, array, index+_array.Length - _head, numToCopy);

}

}

catch(ArrayTypeMismatchException) {

ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);

}

}

// Adds item to the tail of the queue.

//

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Enqueue"]/*" />

public void Enqueue(T item) {

if (_size == _array.Length) {

int newcapacity = (int)((long)_array.Length * (long)_GrowFactor / 100);

if (newcapacity < _array.Length + _MinimumGrow) {

newcapacity = _array.Length + _MinimumGrow;

}

SetCapacity(newcapacity);

}

_array[_tail] = item;

_tail = (_tail + 1) % _array.Length;

_size++;

_version++;

}

// GetEnumerator returns an IEnumerator over this Queue. This

// Enumerator will support removing.

//

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.GetEnumerator"]/*" />

public Enumerator GetEnumerator()

{

return new Enumerator(this);

}

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.IEnumerable.GetEnumerator"]/*" />

/// <internalonly/>

IEnumerator<T> IEnumerable<T>.GetEnumerator()

{

return new Enumerator(this);

}

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()

{

return new Enumerator(this);

}

// Removes the object at the head of the queue and returns it. If the queue

// is empty, this method simply returns null.

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Dequeue"]/*" />

public T Dequeue() {

if (_size == 0)

ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);

T removed = _array[_head];

_array[_head] = default(T);

_head = (_head + 1) % _array.Length;

_size--;

_version++;

return removed;

}

// Returns the object at the head of the queue. The object remains in the

// queue. If the queue is empty, this method throws an

// InvalidOperationException.

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Peek"]/*" />

public T Peek() {

if (_size == 0)

ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);

return _array[_head];

}

// Returns true if the queue contains at least one object equal to item.

// Equality is determined using item.Equals().

//

// Exceptions: ArgumentNullException if item == null.

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.Contains"]/*" />

public bool Contains(T item) {

int index = _head;

int count = _size;

EqualityComparer<T> c = EqualityComparer<T>.Default;

while (count-- > 0) {

if (((Object) item) == null) {

if (((Object) _array[index]) == null)

return true;

}

else if (_array[index] != null && c.Equals(_array[index], item)) {

return true;

}

index = (index + 1) % _array.Length;

}

return false;

}

internal T GetElement(int i)

{

return _array[(_head + i) % _array.Length];

}

// Iterates over the objects in the queue, returning an array of the

// objects in the Queue, or an empty array if the queue is empty.

// The order of elements in the array is first in to last in, the same

// order produced by successive calls to Dequeue.

/// <include file="docQueue.uex" path="docs/doc[@for="Queue.ToArray"]/*" />

public T[] ToArray()

{

T[] arr = new T[_size];

if (_size==0)

return arr;

if (_head < _tail) {

Array.Copy(_array, _head, arr, 0, _size);

} else {

Array.Copy(_array, _head, arr, 0, _array.Length - _head);

Array.Copy(_array, 0, arr, _array.Length - _head, _tail);

}

return arr;

}

// PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity

// must be >= _size.

private void SetCapacity(int capacity) {

T[] newarray = new T[capacity];

if (_size > 0) {

if (_head < _tail) {

Array.Copy(_array, _head, newarray, 0, _size);

} else {

Array.Copy(_array, _head, newarray, 0, _array.Length - _head);

Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);

}

}

_array = newarray;

_head = 0;

_tail = (_size == capacity) ? 0 : _size;

_version++;

}

public void TrimExcess() {

int threshold = (int)(((double)_array.Length) * 0.9);

if( _size < threshold ) {

SetCapacity(_size);

}

}

// Implements an enumerator for a Queue. The enumerator uses the

// internal version number of the list to ensure that no modifications are

// made to the list while an enumeration is in progress.

/// <include file="docQueue.uex" path="docs/doc[@for="QueueEnumerator"]/*" />

#if !SILVERLIGHT

[Serializable()]

#endif

[SuppressMessage("Microsoft.Performance", "CA1815:OverrideEqualsAndOperatorEqualsOnValueTypes", Justification = "not an expected scenario")]

public struct Enumerator : IEnumerator<T>,

System.Collections.IEnumerator

{

private Queue<T> _q;

private int _index; // -1 = not started, -2 = ended/disposed

private int _version;

private T _currentElement;

internal Enumerator(Queue<T> q) {

_q = q;

_version = _q._version;

_index = -1;

_currentElement = default(T);

}

/// <include file="docQueue.uex" path="docs/doc[@for="QueueEnumerator.Dispose"]/*" />

public void Dispose()

{

_index = -2;

_currentElement = default(T);

}

/// <include file="docQueue.uex" path="docs/doc[@for="QueueEnumerator.MoveNext"]/*" />

public bool MoveNext() {

if (_version != _q._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);

if (_index == -2)

return false;

_index++;

if (_index == _q._size) {

_index = -2;

_currentElement = default(T);

return false;

}

_currentElement = _q.GetElement(_index);

return true;

}

/// <include file="docQueue.uex" path="docs/doc[@for="QueueEnumerator.Current"]/*" />

public T Current {

get {

if (_index < 0)

{

if (_index == -1)

ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);

else

ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);

}

return _currentElement;

}

}

Object System.Collections.IEnumerator.Current {

get {

if (_index < 0)

{

if (_index == -1)

ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);

else

ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);

}

return _currentElement;

}

}

void System.Collections.IEnumerator.Reset() {

if (_version != _q._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);

_index = -1;

_currentElement = default(T);

}

}

}

}

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！