实现一个线程安全的栈

这里使用数组来存储栈的数据。不足之处在于本例中的Stack可以无限扩容，更好的是初始化时候指定一个最大容量，防止不断扩容申请内存导致内存不够的问题。这里的线程安全使用一个串行队列来保证，实际上也可以通过加锁或者信号量甚至自旋锁来解决。

struct Stack<Element> {

    private var items: [Element]

    private var queue = DispatchQueue(label: "StackOperationQueue")

    public init(capacity: Int = 10) {

        items = [Element]()

        items.reserveCapacity(capacity)

    }

    mutating public func push(item: Element) {

        queue.sync {

            items.append(item)

        }

    }

    mutating public func pop() -> Element? {

        var item: Element?

        queue.sync {

            item = items.removeLast()

        }

        return item

    }

}

实现一个线程安全的队列

// 存储数据的双向链表节点

class DoubleLinkNode<Element> {

    var previous: DoubleLinkNode?

    var next: DoubleLinkNode?

    let val: Element?

    init(val: Element?) {

        self.val = val

    }

    //声明==运算符，便于判断两个节点是否相等

    static func ==(left: DoubleLinkNode<Element>, right: DoubleLinkNode<Element>) -> Bool {

        //最准确的做法是判断内存地址是否相同

        let leftPointValue = Unmanaged<AnyObject>.passUnretained(left).toOpaque()

        let rightPointValue = Unmanaged<AnyObject>.passUnretained(right).toOpaque()

        return leftPointValue == rightPointValue

    }

}

/*

 1.使用双向链表实现队列结构，声明空的head/last哨兵节点简化双向链表操作；

 2.使用串行队列保证线程安全，实际上也可以通过加锁的方式实现线程安全；

 3.对于生产者-消费者模型，这里可以使用semaphore来实现，当队列为空的时候，让线程休眠，当有元素入队的时候唤醒一个线程继续执行任务。

 */

struct Queue<Element> {

    //声明串行队列，将操作放在串行队列中，保证线程安全

    private var queue = DispatchQueue(label: "QueueOperationQueue")

    let firstNode: DoubleLinkNode<Element>

    let lastNode: DoubleLinkNode<Element>

    public init(capacity: Int = 20) {

        firstNode = DoubleLinkNode(val: nil)

        lastNode = DoubleLinkNode(val: nil)

        firstNode.next = lastNode

        lastNode.previous = firstNode

    }

    /// 入队操作

    mutating public func enqueue(item: Element) {

        queue.sync {

            let node = DoubleLinkNode<Element>(val: item)

            let tmp = firstNode.next

            firstNode.next = node

            node.previous = firstNode

            node.next = tmp

            tmp?.previous = node

        }

    }

    /// 出队操作

    mutating public func dequeue() -> Element? {

        guard let previous = lastNode.previous, !(firstNode == previous) else { return nil }

        var node: DoubleLinkNode<Element>? = nil

        queue.sync {

            node = lastNode.previous

            node?.next = nil

            node?.previous = nil

            let tmp = node?.previous

            lastNode.previous = tmp

            tmp?.next = lastNode

        }

        return node?.val

    }

}

巴特西

swift实现线程安全的栈和队列

实现一个线程安全的栈

实现一个线程安全的队列

最新文章

热门文章