群组
欢迎加入群组,闲聊工作&技术&问题等

        栈(stack)是限制插入和删除只能在一端进行的表,该位置称为栈顶(top).对栈的基本操作有Push(压栈)和Pop(出栈).前者相当于插入,后者相当于删除栈顶元素.栈又叫做LIFO(后进先出)表.只有栈顶元素是可访问的
stack

栈的实现

        由于栈是一个表,因此任何实现表的方法都能实现栈,其中有两个比较常用的实现方法:1)栈的链表实现;2)栈的数组实现

1.栈的链表实现

        栈可以用单链表来实现,在栈顶插入元素来实现Push操作,通过对栈顶元素移除来实现Pop操作.

1.1 栈的链表定义
private(set) var nodeList:NodeList<T>?

    // 是否为空
    var isEmpty:Bool {
        get {
            return nodeList == nil ? true : false
        }
    }

    // MARK: - 构造方法
    init() {
    }
1.2 push()压栈操作

        因为主要基于单链表来实现,所以压栈操作首先判断链表是否为空,为空先创建一个链表元素并将首元素添加到链表中;如果不为空,获取链表的最后一个节点,将最后一个节点的next指针指向压栈元素节点.

/// 压栈操作
    ///
    /// - Parameter element: 压栈元素
    func push(element:T) -> Void {
        if let node = nodeList {
            let nodeLength = node.traverse(with: node)
            let newNode = NodeList(val: element)
            let lastNode = node.find(with: node, at: nodeLength - 1)
            lastNode?.next = newNode
        } else {
            nodeList = NodeList(val: element)
        }
    }
1.3 top栈顶元素

        获取栈顶元素也就是获取链表的最后一个节点

/// 获取栈顶元素
    ///
    /// - Returns: 栈顶元素
    func top() -> T? {
        guard let nodeL = nodeList else { return nil }
        let nodeLength = nodeL.traverse(with: nodeL)
        if nodeLength > 1 {
            return nodeL.find(with: nodeL, at: nodeLength - 1)?.value
        } else {
            return nodeL.value
        }
    }
1.4 pop()移除栈顶元素

        pop操作判断链表长度是否大于1,大于1移除链表最后一个节点.

/// 获取栈顶元素
    ///
    /// - Returns: 栈顶元素
    func top() -> T? {
        guard let nodeL = nodeList else { return nil }
        let nodeLength = nodeL.traverse(with: nodeL)
        if nodeLength > 1 {
            return nodeL.find(with: nodeL, at: nodeLength - 1)?.value
        } else {
            return nodeL.value
        }
    }

2.栈的数组实现

        数组实现栈相对简单,Array已经帮我们实现了相关接口,不用自己去实现.这里不再详述了,直接贴出源码.

// MARK: - 栈的数组实现
struct StackA<T> {

    private(set) var elements:[T] = []

    /// isEmpty
    var isEmpty:Bool{
        get {
            return elements.count == 0 ? true : false
        }
    }

    /// top
    var top:T? {
        get {
            return elements.count > 0 ? elements.last : nil
        }
    }


    // MARK: - 构造函数
    init() {

    }


    /// push压栈操作
    ///
    /// - Parameter element: 压栈元素
    mutating func push(element:T) -> Void {
        elements.append(element)
    }


    /// pop出栈操作
    mutating func pop() -> Void {
        guard elements.count > 0 else {
            return
        }
        elements.removeLast()
    }
}

源码地址

        这里的实现代码已放到GitHub,测试用例详见DataStructureAlgorithmTests.swift文件

参考文献

《数据结构与算法分析C语言描述》(Data Structures and Algorithm Analysis in C:Second Edition)–译者: 冯舜玺


  转载请注明: waitwalker

 上一篇
队列 队列
群组欢迎加入群组,闲聊工作&技术&问题等 像栈一样,队列(queue)也是表.队列的操作操两端进行,一端插入,一端删除. 队列的基本操作入队(Enqueue)操作入队是在队列的末尾插入元素. 出队(Dequeue)操作出队
下一篇 
Swift_mutating Swift_mutating
群组欢迎加入群组,闲聊工作&技术&问题等         在swift中:struct,enum,class都可以定义方法和属性.但是stru
2019-04-11
  目录