[数据结构与算法-iOS 实现] 链表，栈，队列及demo和例子

demo

1.单链表和双链表相关

相关 api。

@interface SCXLinkList<ObjectType> : NSObject

/// 头插法
/// @param object 插入的节点
- (ObjectType)addToHead:(ObjectType)object;

/// 尾插法
/// @param object 插入的节点
- (ObjectType)addToTail:(ObjectType)object;

/// 移除某个位置的元素
/// @param index 位置
- (ObjectType)removeObjectAtIndex:(NSInteger)index;

/// 某个额位置的元素
/// @param index 位置
- (ObjectType)objectAtIndex:(NSInteger)index;

/// 移除头结点
- (ObjectType)removeFirstObject;

/// 移除尾结点
- (ObjectType)removeLastObject;

/// 添加到某个位置
/// @param object 元素
/// @param index 位置
- (ObjectType)addObject:(ObjectType)object atIndex:(NSInteger)index;

/// 更新某个位置的元素
/// @param object 元素
/// @param index 位置
- (ObjectType)setObject:(ObjectType)object atIndex:(NSInteger)index;

/// 删除某个值
/// @param object 要删除的值
- (void)deleteObject:(ObjectType)object;

/// 是否包含某个值
/// @param object 检测s的值
- (BOOL)containObject:(ObjectType)object;

/// 某个元素在链表中的位置
/// @param object 查找的元素
- (NSInteger)indexOfObject:(ObjectType)object;

/// 清空链表
- (void)clear;

/// 反转链表
- (void)reverseList;

/// 链表是否有环
- (BOOL)hasCircle;

@end

    双向链表相比于单向链表，所谓的O(1)是指删除、插入操作。

       单向链表要删除某一节点时，必须要先通过遍历的方式找到前驱节点（通过待删除节点序号或按值查找）。若仅仅知道待删除节点，是不能知道前驱节点的，故单链表的增删操作复杂度为O(n)。 双链表（双向链表）知道要删除某一节点p时，获取其前驱节点q的方式为 q = p->prior，不必再进行遍历。故时间复杂度为O(1)。而若只知道待删除节点的序号，则依然要按序查找，时间复杂度仍为O(n)。

       单、双链表的插入操作，若给定前驱节点，则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点，时间复杂度为O(n)。至于查找，二者的时间复杂度均为O(n)。 对于最基本的CRUD操作，双链表优势在于删除给定节点。但其劣势在于浪费存储空间（若从工程角度考量，则其维护性和可读性都更低）。

       双链表本身的结构优势在于，可以O(1)地找到前驱节点，若算法需要对待操作节点的前驱节点做处理，则双链表相比单链表有更加便捷的优势。    

参考

2.栈

栈是一种先进后出的数据结构。

1. 比如我们的浏览器前进后退的功能，我们打开了三个网页，让这三个网页一次入栈，当我们点击后退的按钮的时候，我们出栈一个网页然后放到另一个栈里面入栈，然后再点后退，再出栈，另一个入栈，当我们点击前进的时候，从第二个栈里面出栈一个放到第一个栈里面，就做到了这个功能。
2. 再比如我们的匹配括号的需求“[({})]”,判断括号是否匹配，我们将左元素放到一个栈里面，也就是[({,发现有左元素我们就入栈，当发现有右元素的时候})]，我们就出栈，如果第一个匹配，},匹配，然后{出栈，然后去比较下一个，如果都匹配的话，最后栈应该为空，这样就做到了我们的需求。

其实在我们 iOS 可以用数组来实现栈，入栈就插入到数组的尾部，出栈就移除数组的尾部，就相当于后进先出。

3.队列

队列是一种先进先出的数据结构，入队(enQueue)和出对(deQueue)，从队列尾部进入，从对头出对，可以来选择我们的双向链表来实现队列，因为如果选择动态数组，虽然队尾入队是O(1)，但是对头出对是O(N)，所以我们选择双向链表，都为O(1).当我们入队的时候，插入到双向链表的尾部，出对的时候移除头结点，这样就是先进先出了，iOS 双向链表可以看我的demo。

如果用栈来实现队列，因为栈为先进后出，而队列为先进先出，比如我们入队，1，2，3，4，出对应该为1，2，3，4，但是我们的栈出栈顺序为4，3，2，1，那怎么来实现呢？我们准备两个栈，in和out，当我们入队的时候，就入栈到in这个栈里面，将1，2，3，4入栈，栈的顺序为4，3，2，1，然后这时候出对，应该出来1，这时候，我们检查out这个栈是否为空，如果为空，将in这个栈里面所有的元素都出栈到out里面，这时候in为空，out为为，1，2，3，4，这时候从out出栈，出来的为1，就和我们出栈的顺序一样了，如果这时候再有5，6，入栈，应该怎么做呢，这时候in为空，将5，6，入栈，然后这时候如果出栈，按照队列的顺序，1，2，3，4，入栈出去1，还剩下2，3，4然后入栈5，6，这时候队列应为2，3，4，5，6，这时候如果出栈应该为2，而这时候我们的in栈为6，5，我们的out栈为2，3，4，所以这时候如果发现out不为空，继续从out出栈，知道out都出栈为空位置，这样就能实现队列的功能。原理就是两个栈，出栈的时候先看out是否为空，如果不为空，out继续出栈，如果out为空，in所有元素出栈放到out里面。

其实队列也可以用数组来实现，从数组的尾部添加，然后从数组的头部移除，实现先进先出即可。

4.双端队列（Deque）

我们的单端队列，只能在尾部添加，头部删除，我们的双端队列，能在头尾添加和删除,使用我们的双向链表再好不过了。