swift数据结构

一、栈

//
//  Stack.swift
//  DataStructure
//
//  Created by dzq_mac on 2020/8/26.
//  Copyright © 2020 dzq_mac. All rights reserved.
//

import Foundation

struct Stack<T> {
    fileprivate var array:[T] = []
    
    public var isEmpty:Bool{
        return array.isEmpty
    }
    
    public var count:Int{
        return array.count
    }
    
    public mutating func push(_ element :T) {
        array.append(element)
    }
    @discardableResult
    public mutating func pop() ->T?{
        return array.popLast()
        
    }
    
    public var top:T?{
        return array.last
    }
        
}
extension Stack:Sequence{
    func makeIterator() -> AnyIterator<T> {
        var cul = self
        return AnyIterator{
            cul.pop()
        }
    }
}

二、队列

//
//  Queue.swift
//  DataStructure
//
//  Created by dzq_mac on 2020/8/26.
//  Copyright © 2020 dzq_mac. All rights reserved.
//

import Foundation

/*
 //简单的队列
 struct Queue<T> {
     fileprivate var array:[T] = []
     
     public var count:Int{
         return array.count
     }
     
     public var isEmpty:Bool{
         return array.isEmpty
     }
     
     public mutating func enqueue(_ element:T){
         array.append(element)
     }
     public mutating func dequeue()->T?{
         if isEmpty{
             return nil
         }else{
             return array.first
         }
     }
     
     public var front:T?{
         return array.first
     }
     
 }
 */

/*
 优化的队列，以数组为基础创建队列，出队的时候都是最前边的元素移除
 数组的特性，移除元素它后边的所有元素都要移动位置，性能较低
 队列每次出队都移除数组元素导致性能低下，
 优化方案，出队到一定数量再移动元素，一次移动可满足多次出队
 */
struct Queue<T> {
    fileprivate var array:[T?] = []
    fileprivate var head:Int = 0
    
    public var count:Int{
        return array.count - head
    }
    
    public var isEmpty:Bool{
        return count == 0
    }
    
    public mutating func enQueue(_ element:T){
        array.append(element)
    }
    public mutating func deQueue()->T?{
        guard let element = array[guarded:head] else {
            return nil
        }
        array[head] = nil
        head += 1
        
        let persent = Double(array.count - head)/Double(array.count)
        if array.count > 50 && persent > 0.25 {
            array.removeFirst(head)
            head = 0
        }
        
        return element
    }
    
    public var front:T?{
        return array[head]
    }
    
}
extension Array {
    subscript(guarded idx : Index) ->Element?{
        if (startIndex...endIndex).contains(idx) {
            return self[idx]
        }else{
            return nil
        }
    }
}

//stack implement queue
struct QueueImlStark<T> {
    
    private var stackA = Stack<T>()
    private var stackB = Stack<T>()

    public var count:Int{
        return stackA.count + stackB.count
    }
    
    public var isEmpty: Bool{
        return stackA.isEmpty && stackB.isEmpty
    }
    /**
     * 入队操作
     * @Param element
     */
    public mutating func enQueue(_ element:T){
        stackA.push(element)
    }

    /**
     *
     * 出队操作
     */
    public mutating func deQueue() ->T?{
        if (stackB.isEmpty){
            if (stackA.isEmpty){
                return nil
            }
            fetchFormStackA();
        }

        return stackB.pop();
    }

    /**
     * 从stackA栈中拿到出栈元素压入栈B
     */
    private mutating func fetchFormStackA() {
        while (!stackA.isEmpty){
            stackB.push(stackA.pop()!);
        }
    }
}

三、二叉树

//
//  Tree.swift
//  DataStructure
//
//  Created by dzq_mac on 2020/8/26.
//  Copyright © 2020 dzq_mac. All rights reserved.
//

import Foundation

class TreeNode<T> {
    public var value:T
    public var leftNode:TreeNode<T>?
    public var rightNode:TreeNode<T>?
    
    init(_ value:T) {
        self.value = value
    }
}

class Tree<T> {
    var rootNode:TreeNode<T>?
    
    init(head:TreeNode<T>) {
        self.rootNode = head
    }
    
    /// depth,递归方法获取最大深度
    /// - Parameter root: node
    /// - Returns: tree depth
    func maxDepth(root :TreeNode<T>? = nil) -> Int{
        guard let rNode = root else{
            return 0
        }
        
        return max(maxDepth(root: rNode.leftNode), maxDepth(root: rNode.rightNode)) + 1
    }
    
    
    /*
    //1.s型顺序访问二叉树,默认先左后右；利用两个栈来实现；如果先右后左的话，改变一下入栈的顺序就行
    //2.注意s1 s2插入栈的顺序是不同的
    void S_LevelOrderPrint(TreeNode t)
    {
        stack<TreeNode> s1;
        stack<TreeNode> s2;
        s1.push(t);//S
        while(!s1.empty() || !s2.empty())
        {
            if(!s1.empty())
            {
                while(!s1.empty())
                {
                    TreeNode tn = s1.top();
                    cout<<tn.val<<"";
                    s1.pop();
                    if(tn.right != null)
                    {
                        s2.push(tn.right);
                    }
                    if(tn.left != null)
                    {
                        s2.push(tn.left);
                    }
                }
            }
            else
            {
                while(!s2.empty())
                {
                    TreeNode tn = s2.top();
                    cout<<tn.val<<" ";
                    s2.pop();
                    if(tn.left != null)
                    {
                        s1.push(tn.left);
                    }
                    if(tn.right != null)
                    {
                        s1.push(tn.right);
                    }
                }
            }
     
        }
    }
 */
}
//MARK:- 递归实现遍历
func preOrderTraversal<T>(rootNode:TreeNode<T>) ->[T] {
    var arr = [T]()
    
    func traversal(node:TreeNode<T>?){
        guard let root = node else{
            return
        }
        arr.append(root.value)
        traversal(node: root.leftNode)
        traversal(node: root.rightNode)
    }
    traversal(node: rootNode)
    
    return arr
}

func midOrderTraversal<T>(rootNode:TreeNode<T>) ->[T] {
    var arr = [T]()
    
    func traversal(node:TreeNode<T>?){
        guard let root = node else{
            return
        }
        traversal(node: root.leftNode)
        arr.append(root.value)
        traversal(node: root.rightNode)
    }
    traversal(node: rootNode)
    
    return arr
}

func aftOrderTraversal<T>(rootNode:TreeNode<T>) ->[T] {
    var arr = [T]()
    
    func traversal(node:TreeNode<T>?){
        guard let root = node else{
            return
        }
        traversal(node: root.leftNode)
        traversal(node: root.rightNode)
        arr.append(root.value)
    }
    traversal(node: rootNode)
    
    return arr
}
//MARK: stack imp traversal
func preOrderTraversalWithStack<T>(rootNode:TreeNode<T>) ->[T]{
    var res = [T]()
    var stack = Stack<TreeNode<T>>()
    var node :TreeNode<T>? = rootNode
   
    while !stack.isEmpty || node != nil {
        if node != nil {
            res.append(node!.value)
            stack.push(node!)
            node = node!.leftNode
        } else {
            node = stack.pop()?.rightNode
        }
    }
    
    return res
}

func midOrderTraversalWithStack<T>(rootNode:TreeNode<T>) ->[T]{
    var res = [T]()
    var stack = Stack<TreeNode<T>>()
    var node :TreeNode<T>? = rootNode
    
    while !stack.isEmpty || node != nil {
        if node != nil {
            stack.push(node!)
            node = node!.leftNode
        } else {
            node = stack.pop()
            res.append(node!.value)
            node = node?.rightNode
            
        }
    }
    
    return res
}
/*
 后序遍历时由于访问完左右子树后才能访问根结点，因此需要将根结点在栈内保留到左右子树被访问后，但同时会出现一个问题，当右子树弹出后遇到根结点又会将右子树结点压入栈中，造成死循环，因此我们需要在定义一个变量last代表最后一个访问的结点，当last与栈顶结点的右子树结点相同时，则不再将右子树结点压入栈中。
 */
func aftOrderTraversalWithStack<T>(rootNode:TreeNode<T>) ->[T]{
    var res = [T]()
    var stack = Stack<TreeNode<T>>()
    var node :TreeNode<T>? = rootNode
    var last:TreeNode<T>? = nil
    
    while !stack.isEmpty || node != nil {
        if node != nil {
            stack.push(node!)
            node = node!.leftNode
            
        } else {
            
            node = stack.top
            if let right = node?.rightNode,right !== last{//考虑栈顶结点的右子树结点。存在且没被访问过，将右子树结点压入栈中
                node = right
            }else{
                res.append(node!.value)
                last = node
                //node置空作用在于当原栈顶结点被访问并弹出后，下一层while是将当前栈顶结点的左子树入栈，当前栈顶结点的左子树已经被遍历过
                //因此会造成死循环，所以将node置空，直接考虑当前栈顶结点的右子树
                //一旦某个结点入栈，首先会遍历这个结点的左子树，然后考虑右子树的情况
                stack.pop()
                node = nil
            }
                
            
        }
    }
    
    return res
}

//按层遍历
func layerTraversal<T>(rootNode:TreeNode<T>) ->[T]{
    
    var arr = [T]()
    var queue = Queue<TreeNode<T>>()
    let node:TreeNode<T>? = rootNode
    queue.enQueue(node!)
    while !queue.isEmpty {
        if let cur = queue.deQueue() {
            arr.append(cur.value)
            if let left = cur.leftNode{
                queue.enQueue(left)
            }
            if let right = cur.rightNode {
                queue.enQueue(right)
            }
        }
        
        
    }
    return arr
}
//S遍历
func sLayerTraversal<T>(rootNode:TreeNode<T>) ->[T] {
    var arr = [T]()
    var stack1 = Stack<TreeNode<T>>()
    var stack2 = Stack<TreeNode<T>>()
    stack2.push(rootNode)
    
    while !stack1.isEmpty || !stack2.isEmpty {
        if !stack1.isEmpty {
            while !stack1.isEmpty {
                let node = stack1.pop()!
                arr.append(node.value)
                
                if let right = node.rightNode {
                    stack2.push(right)
                }
                
                if let left = node.leftNode {
                    stack2.push(left)
                }
            }
        }else{
            while !stack2.isEmpty {
                let node = stack2.pop()!
                arr.append(node.value)
                
                if let left = node.leftNode{
                    stack1.push(left)
                }
                
                if let right = node.rightNode {
                    stack1.push(right)
                }
                
            }
        }
    }
    
    
    
    return arr
}

四、链表

//
//  Link.swift
//  DataStructure
//
//  Created by dzq_mac on 2020/8/29.
//  Copyright © 2020 dzq_mac. All rights reserved.

import Foundation
class LinkNode<T> {
    var value:T
    var nextNode:LinkNode<T>?
    init(_ value:T) {
        self.value = value
    }
}

public struct LinkTable<T> {
    private var headNode:LinkNode<T>?
    
    private(set) var count:Int  = 0 //内部可写，外部只读
    
    
    var valueArray : [T] {
        get {
            var arr = [T]()
            var node = headNode
            while node != nil {
                arr.append(node!.value)
                node = node?.nextNode
            }
            return arr
        }
    }
    
    public mutating func append(_ element :T) {
        let node = LinkNode<T>(element)
        if self.headNode != nil{
            var tamp = self.headNode
            while tamp?.nextNode != nil {
                tamp = tamp?.nextNode
            }
            tamp?.nextNode = node
        }else{
            headNode = node
        }
        count += 1
        
    }
    
    @discardableResult
    public mutating func insert(_ element: T,at index:Int) -> Bool{
        guard index >= 0 else{
            return false
        }
//        if index > count{
//            //插入失败，越界
//            return false
//        }
    
        
        if index == 0 {
            let new = LinkNode<T>(element)
            new.nextNode = headNode
            headNode = new
            count += 1
            return true
        }
        var lenth = 0
        var node = headNode
        while node != nil {
            lenth += 1
            if lenth == index {
                let new = LinkNode<T>(element)
                new.nextNode = node?.nextNode
                node?.nextNode = new
                count += 1
                return true
            }
            node = node?.nextNode
            
        }
        
        return false
    }
    
    
    public mutating func removeAll(){
        guard headNode != nil else{
            count = 0
            return
        }
        var node = headNode
        headNode = nil
        while node != nil {
            let tamp = node?.nextNode
            node?.nextNode = nil
            node = tamp
        }
        count = 0
    }
    @discardableResult
    public mutating func removeObject(at index:Int) -> Bool{
        guard index >= 0 && headNode != nil else{
            return false
        }
        if index == 0{
            headNode = headNode?.nextNode
            return true
        }
        var lenth = 0
        var node = headNode
        while node != nil {
            lenth += 1
            
            if lenth == index {
                node?.nextNode = node?.nextNode?.nextNode
                return true
            }
            node = node?.nextNode
            
        }
        
        return false
    }
    
    
    
    public mutating func reverse(){
        var node = headNode
        var nextNode = headNode?.nextNode
        node?.nextNode = nil
        while node != nil && nextNode != nil{
            let tamp = nextNode?.nextNode
            nextNode?.nextNode  = node

            node = nextNode
            nextNode = tamp
        }
        headNode = node
        //
        
    }
    
    public mutating func reverseWithStack(){
           var node = headNode
           
           var stack = Stack<LinkNode<T>>()
           
           while node != nil {
               stack.push(node!)
               node = node?.nextNode
           }
           
           headNode = stack.pop()
           node = headNode
           while stack.top != nil {
               node?.nextNode = stack.pop()
               node = node?.nextNode
           }
           node?.nextNode = nil//原来的头节点，现在的尾节点，next置空
           
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}
public extension LinkTable where T : Comparable {
    
    mutating func remove(element:T) {
        
        while let val = headNode?.value,val == element{
            headNode = headNode?.nextNode
        }
        var node = headNode
        while node != nil {
            if node?.nextNode?.value == element {
                node?.nextNode = node?.nextNode?.nextNode
            }
            node = node?.nextNode
        }
        
    }
}