.NET源码Stack<T>和Queue<T>的实现

发表于:2015-4-16 10:48

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:teroy    来源:51Testing软件测试网采编

  首先通过下面的图来看一下数组容量足够的时候,循环队列的执行过程:
  基于上面这张图的执行过程,来看一下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的构造函数。
33/3<123
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号