队列的特性
前进先出。
我们来大致描述下进出队列的情况。
进队列
1 进队列现在队列是 1
2 进队列现在队列是 1 ，2
4 进队列现在队列是 1 ，2，4
出队列
第一个元素出队列 是 1 现在队列里2，4
第二个元素出队列 是2 现在队列里4
有几个注意的地方。
1：如果队列里没有元素将返回nil ，可以给一个错误提示信息。
2：进队列的时间复杂度是O（1），因为随着数组的增加不会影响时间复杂度，只是在最后面添加。但是如果这个数组的容量占满了，那么我们得重新调整数组容量来获取更多的空间，这个操作是重新创建新的内存，然后再copy，这个时间复杂度是O（n） 。
3：如果队列从头部出队列，后面元素内存要移位操作。这个是一个时间复杂度为O（n）操作。所以我们不能在数组中删除第一个元素，因为删除后，数组的机制为了填充前面的空隙后面的元素会前移，所以我们只是返回要出队的元素。
先看没有优化前的队列的代码
- (void)enqueue:(id)object
{
if (object != nil) {
[self.queueArray addObject:object];
}
else {
NSAssert(object != nil, @"You can't push nil object to queue");
}
}
出队的代码
- (id)dequeue
{
if ([self.queueArray count] > 0)
{
id object = [self peek];
[self.queueArray removeObjectAtIndex:0];
return object;
}
return nil;
}
如果队列存在元素才能出去，但是如果删除第一个元素，后面元素前移（上面也说了这是数组的机制为了填充前面的空隙）影响效率，我们后面会优化这个地方。
找到影响性能的地方优化它
为了充分利用数组的空间，并且避免频繁的移动元素，不直接删除头部元素，而是置为空，通过移动索引的方式返回要出队的元素，当队列的头部索引前面的空间比较大的时候我们清理一波。看代码实现
- (id)dequeue
{
id object;
if (self.headIndex < self.queueArray.count)
{
object = self.queueArray[self.headIndex];
}
else
{
return nil;
}
self.queueArray[self.headIndex] = [NSNull null];
self.headIndex += 1;
double percentage = (double)self.headIndex/(double)(self.queueArray.count);
if (self.queueArray.count > kQueueCapacity && percentage > 0.25)
{
[self.queueArray removeObjectsInRange:NSMakeRange(0, self.headIndex)];
self.headIndex = 0;
}
return object;
}
上面计算了队首空余的元素占数组总元素的百分比，如果空余元素超过 25%，我们就进行一波清理。但是，如果队列的长度过小，我们也不想频繁地清理空间，所以在清理空间之前，队列中至少要有 一定量 的元素，比如我这个kQueueCapacity 是 100。
测试下
进队
DSQueue *queue = [[DSQueue alloc] initWithSize:5];
[queue enqueue:@"1"];
[queue enqueue:@"2"];
[queue enqueue:@"3"];
[queue enqueue:@"4”];
结果图
进队的图
出队
[queue dequeue];
出队后的图
清空前面的占位元素节省空间
清理多余空间后的图
看箭头所指的地方现在索引前面的多余的空间已经被清理了，并且索引的是0。
还有优化的空间
之前我们说栈的时候动态扩容，为了避免频繁创建内存。但是我们可以利用头部的空间，不清理它，比如队尾巴满了，头部有空间我们可以放到头部，这样加一个尾部索引，如果头部和尾部索引真相等了那么，这个队列可能真满了，再考虑创建更多的空间。由于队列的顺序性，我们要小心copy元素，比如如果头部元素大于尾部元素那么就是copy从头部元素一直到size个元素到新的数组，如果头部元素小于尾部元素就要copy两部分元素，头部元素到数组结束的元素，还有一部分数组开始到尾部索引的元素到新的数组。
总结
通过移动索引的方式来避免移动元素，通过一定的机制清理多余的空间来节省内存。现在出队操作的复杂度已经从之前的 O(n) 变为了现在的 O(1)。找到代码瓶颈并优化它吧。
网友评论