100天iOS数据结构与算法实战 Day02 - 栈

人魔七七 2019-03-27 10:15:52 1105


栈的特性

栈 的特性是先进后出。

动画描述

640.gif


640 (1).gif

栈最常见的场景

  • 栈在iOS开发中常见的是导航栈,push pop 操作就是这种进栈出栈的操作。

  • 你调用函数的时候,这个返回地址被放到栈中,当函数结束时,使用该返回地址跳回调用者,这是记录函数调用过程的完美体现。

和栈有关的算法题目

  • Valid Parentheses

  • Basic Calculator

  • Evaluate Reverse Polish Notation

  • Implement Queue using Stacks

  • Implement Stack using Queues

  • Simplify Path

实现方式

主要有两种方法来实现栈:使用数组,使用链表。我们代码是用数组来实现的。

栈的基本操作方式

DSStack *testStack = [[DSStack alloc] initWithSize:4];    [testStack push:@"1"];    [testStack push:@"2"];    [testStack push:@"5"];    [testStack popLastObject];    NSLog(@"%@",testStack);

主要代码

  1. - (instancetype)initWithSize:(NSUInteger)size

  2. {

  3.    self = [super init];


  4.    if (self) {

  5.        if (size > 0) {

  6.            _stackArray = [[NSMutableArray alloc] initWithCapacity:size];

  7.            _maxStackSize = size;

  8.        }

  9.        else {

  10.            NSAssert(size != 0, @"Stack size must be > 0");

  11.        }

  12.    }

  13.    return self;

  14. }

初始化给定大小,这样是有好处的。因为如果数组容量满的时候为了增加容量,频繁的动态创建数组 copy数组会消耗一定的内存

  1. - (void)push:(id)object

  2. {

  3.    if ([self isFull] && self.maxStackSize) {


  4.        NSMutableArray *newArray = [[NSMutableArray alloc] initWithCapacity:_maxStackSize*2];

  5.        self.stackArray = [newArray mutableCopy];

  6.        _maxStackSize = _maxStackSize*2;


  7.    }

  8.    if (object != nil) {

  9.        [self.stackArray addObject:object];


  10.    }

  11.    else {

  12.        NSAssert(object != nil, @"You can't push nil object to stack");

  13.    }

  14. }

如果当前数组填充满了 则创建一个两倍容量的数组copy一份给原来的数组

  1. - (id)popLastObject


  2. {


  3.     id object = [self peek];


  4.     [self.stackArray removeLastObject];


  5.     return object;


  6. }

如果当前数组不为空,存在数组最后一个对象则直接返回 并移除掉。

优化:

提供了一个初始化传入size的值是为了预估空间比较合理。如果没有预估好,频繁扩容会造成不断申请内存然后copy。举个例子提前初始化容量和不指定容量的对比效果图看下图:

QQ截图20190327104731.png

为了避免这个问题提供一个压缩空间的方法

  1. - (void)compressedStack

  2. {

  3.    int capacitySize = (int)(_maxStackSize * 0.9);

  4.    int stackSize = (int)(self.stackArray.count);

  5.    if( stackSize < capacitySize ) {

  6.        NSMutableArray *newArray = [[NSMutableArray alloc] initWithCapacity:stackSize];

  7.        self.stackArray = [newArray mutableCopy];

  8.        _maxStackSize = stackSize;


  9.    }

  10. }

如果当前栈内元素个数小于容量的90% ,那么压缩栈把容量设置为当前栈的实际元素个数。

栈操作复杂度

压栈操作是将新元素压入数组的尾部,而不是头部。在数组的头部插入元素是一个很耗时的操作,它的时间复杂度为 O(n),因为需要将现有元素往后移位为新元素腾出空间。而在尾部插入元素的时间复杂度为 O(1);无论数组有多少元素,这个操作所消耗的时间都是一个常量。

栈的实现Demo

[https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm/tree/master/Day02]