1、数组元素在内存上连续存放，可以通过下标查找元素；插入、删除需要移动大量元素，比较适用于元素很少变化的情况
2、静态数组(NSArray)，内容不可改变，从栈中分配空间，不能存放基础类型， 自由度小
3、静态数组的变量本身就是数组第一个元素的地址

NSDictionary（字典）是使用 hash表来实现key和value之间的映射和存储的， hash函数设计的好坏影响着数据的查找访问效率。数据在hash表中分布的越均匀，其访问效率越高。而在Objective-C中，通常都是利用NSString 来作为键值，其内部使用的hash函数也是通过使用 NSString对象作为键值来保证数据的各个节点在hash表中均匀分布。

队列是一种特殊的线性表，特殊之处在于它只允许在表的 前端(head) 进行删除操作，而在表的后端(tail) 进行插入操作，队列是一种操作受限制的线性表。进行插入操作的端称为队尾 ，进行删除操作的端称为队头 。

队列特点是先进先出,后进后出。

比如 NSOpeartionQueue 和 GCD 的 各种队列 ,其特点都是先进先出(First In First out), 在多线程执行执行多个任务时候, 放进同一队列的任务是顺次从队列里取出任务并执行的。

队列在我们生活中也很常见,比如排队购票 去银行办理业务排队办理业务,都是队首的办理完业务后,离开柜台 下一个人接着办理业务

最简单的队列实现就是一个数组，实现一个进队列 和 一个出队列的方法(头部移除)

数组：数组元素在内存上连续存放，可以通过下标查找元素；插入、删除需要移动大量元素，比较适用于元素很少变化的情况

链表：链表中的元素在内存中不是顺序存储的，查找慢，插入、删除只需要对元素指针重新赋值，效率高

单向链表是最简单的链表形式。我们将链表中最基本的数据称为节点(node)，每一个节点包含了数据块和指向下一个节点的指针。

带头节点

不带头节点

OC:

.h文件
///////链表存放对象
@interface Person : NSObject
@property (nonatomic, strong) NSString *name;
@end
///////链表节点
@interface LinkedNode : NSObject
@property (nonatomic, strong) Person *data;
@property (nonatomic, strong) LinkedNode *next;
@end
///////链表
@interface LinkedList : NSObject
@property (nonatomic, strong) LinkedNode *head;
@property (nonatomic, strong) LinkedNode *tail;
@end

.m文件

///////链表节点
@implementation LinkedNode
- (instancetype)initWithData:(Person *) data
{
    self = [super init];
    if (self) {
        self.data = data;
        self.next = nil;
    }
    return self;
}
@end
///////链表
@implementation LinkedList
///////初始化带头部链表
- (instancetype)init
{
    self = [super init];
    if (self) {
        self.head = [[LinkedNode alloc]init];
        self.head.next = nil;
        self.tail= self.head;
    }
    return self;
}
///////添加链表，头部添加
- (void)appendToHeadWithData:(Person *)data {
    LinkedNode *node = [[LinkedNode alloc]initWithData:data];
    
    node.next = self.head.next;
    self.head.next = node;
}
///////添加链表，尾部添加
- (void)appendToTailWithData:(Person *)data {
    LinkedNode *node = [[LinkedNode alloc]initWithData:data];
    node.next = self.tail.next;
    self.tail.next = node;
    self.tail = node;
}
///////删除指定位置节点
- (Person *)deleteWithHead:(LinkedNode *)head andNum:(int)num {
    if (head.next == nil || num < 1) { return nil; }
    int i = 0;
    LinkedNode *node = head;
    LinkedNode *p;
    Person *data;
    
    while (i++ < num - 1) { node = node.next; }
    p = node.next;
    if (p == NULL ) { return nil; }
    data = p.data;
    node.next = node.next.next;
    return data;
}
///////判断链表是否为空
- (BOOL)isEmpty { return self.head.next == NULL; }

- (void)print {
    LinkedNode *head = self.head;
    while (head != nil) {
        if (head.data != NULL) {
            NSLog(@"%@",head.data.name);
        }
        head = head.next;
    }
}
@end


Swift: 枚举写链表

枚举可以实现了一个只能增加不能删减的链表

indirect enum LinkedList<Element: Comparable> {
    case Empty
    case Head
    case Node(Element, LinkedList<Element>)
    
    static func start() -> LinkedList {
        return LinkedList.Head
    }
    func append(data: Element) -> LinkedList {
        return   LinkedList.Node(data, self)
    }
    func description() {
        var list = self
        while case let LinkedList.Node(element, next) = list {
            print(element)
            list = next
        }
    }
}

如果要实现完整的逻辑还是得用class

class LinkedList<T>: NSObject {
    class LinkedNode<T>: NSObject {
        var data: T?
        var next: LinkedNode<T>?
        override init() {
            super.init()
        }
        init(withData data: T) {
            super.init()
            self.data = data
        }
    }
    var head: LinkedNode<T>
    var tail: LinkedNode<T>
    
    override init() {
        let node = LinkedNode<T>()
        node.next = nil
        head = node
        tail = head
        super.init()
    }
    
    func appendToHead(withData data: T) {
        let node = LinkedNode<T>(withData: data)
        node.next = self.head.next
        self.head.next = node
    }
    func appendToTail(withData data: T) {
        let node = LinkedNode<T>(withData: data)
        node.next = self.tail.next
        self.tail.next = node
        self.tail = node
    }
    func description() {
        var node: LinkedNode<T>? = self.head
        while node != nil {
            print(node?.data)
            node = node?.next
        }
    }
}

1、数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系

2、能够具备数组的快速查询的优点又能融合链表方便快捷的增加删除元素的优势，简单的说就是散列，即将输入的数据通过hash函数得到一个key值，输入的数据存储到数组中下标为key值的数组单元中去，我们发现，不相同的数据通过hash函数得到相同的key值。这时候，就产生了hash冲突。解决hash冲突的方式有两种。一种是挂链式，也叫拉链法。挂链式的思想在产生冲突的hash地址指向一个链表，将具有相同的key值的数据存放到链表中。另一种是建立一个公共溢出区。将所有产生冲突的数据都存放到公共溢出区，也可以使问题解决。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        
        var res: [Int] = []
        var stack: [TreeNode] = []
        var node: TreeNode? = root
    
        while node != nil || !stack.isEmpty {

            if node != nil {
                res.append(node!.val)
                stack.append(node!)
                node = node?.left
            } else {
                node = stack.removeLast().right
            }
        }

        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
            var res: [Int] = []
    var stack: [TreeNode] = []
    var node: TreeNode? = root
    
    while node != nil || !stack.isEmpty {
        
        if node != nil {
            stack.append(node!)
            node = node?.left
        } else {
            let _node = stack.removeLast()
            res.append(_node.val)
            node = _node.right
        }
    }
    
    return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
            var res: [Int] = []
    var stack: [TreeNode] = []
    var node: TreeNode? = root
    var last: TreeNode? = root
    
    while node != nil || !stack.isEmpty {
        
        while node != nil {
            stack.append(node!)
            node = node?.left
        }
        node = stack.last!
        if node?.right == nil || node?.right?.val == last?.val {
            last = stack.last!
            res.append(stack.removeLast().val)
            node = nil
        } else {
            node = node?.right
        }
    }
    
    return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
   
    var res: [[Int]] = []
    var stack: [TreeNode] = []
    
    guard let root = root else {
        return []
    }
    
    stack.append(root)
    
    while !stack.isEmpty {
        var level: [Int] = []
        
        for _ in 0..<stack.count {
            
            let removeNode = stack.removeFirst()
            level.append(removeNode.val)
            if let leftNode = removeNode.left {
                stack.append(leftNode)
            }
            
            if let rightNode = removeNode.right {
                stack.append(rightNode)
            }
        }

        res.append(level)
    }
    
    return res
    }
}