栈 | waitwalker

数据结构与算法

发布日期: 2019-04-11

文章字数: 796

阅读时长: 3 分

阅读次数:

群组
Flutter,iOS,Android,Python等,闲聊工作&技术&问题;
个人主页:https://waitwalker.cn
telegram群链接:https://t.me/joinchat/Ej0o0A1ntlq5ZFIMzzO5Pw

栈(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()
    }
}