.NET源码Stack<T>和Queue<T>的实现
作者:网络转载 发布时间:[ 2015/4/17 9:40:38 ] 推荐标签:.NET 源码 函数
首先通过下面的图来看一下数组容量足够的时候,循环队列的执行过程:
基于上面这张图的执行过程,来看一下Dequeue函数的实现。第一步判断的是_size是否为0,是的话抛出异常。如果当前入队个数大于0,则获取_array[_head]元素作为出队元素,之后调用default(T)填充_array[_head]的位置。由于是一个循环队列的设计,所以不能简单地将_head+=1,而必须这样_head=(_head+1)%_array.Length,如上图所示,_head有可能指向下标为3的位置,假如这时直接_head += 1变为4的话,跳出了数组的小标范围,而_head=(_head+1)%_array.Length变为0,则指向了数组前的位置,实现了循环队列的功能,更好地利用了内存。
接下来看一下Enqueue(T item)函数的实现。承接上图的Queue的状态,假如现在要执行q.Enqueue("f")的入队操作,但是很明显数组_array已经满了,那么要怎么办呢?其实原理和Stack的实现类似,也是要通过数组扩容的方式,不过比Stack的数组复制要复杂一些。来继续看图:
与Stack<T>一样,影响Queue<T>性能大因素是数组扩容以及相应的数组复制操作,同样Queue也提供了一个带初始化容量的构造函数Queue(int capacity),如果我们能估算到队列可能同时存在元素的大值,尽量调用这个带capacity的构造函数。
相关推荐
更新发布
功能测试和接口测试的区别
2023/3/23 14:23:39如何写好测试用例文档
2023/3/22 16:17:39常用的选择回归测试的方式有哪些?
2022/6/14 16:14:27测试流程中需要重点把关几个过程?
2021/10/18 15:37:44性能测试的七种方法
2021/9/17 15:19:29全链路压测优化思路
2021/9/14 15:42:25性能测试流程浅谈
2021/5/28 17:25:47常见的APP性能测试指标
2021/5/8 17:01:11