lijianfei.com

Swift语言中没有内设的栈和队列， 可通过数组或链表模拟栈和队列（链表的加入和删除的时间复杂度是O(1)，但因为Swift没有现成的链表，而数组又有很多的API可以直接使用，所以下面用数组实现）

栈

• 栈是后进先出的结构。你可以理解成有好几个盘子要垒成一叠，哪个盘子最后叠上去，下次使用的时候它就最先被抽出去
• 在iOS开发中，如果你要在你的App中添加撤销操作（比如删除图片，恢复删除图片），那么栈是首选数据结构
• 几个基本操作：push、pop、isEmpty、peek、size

队列

• 队列是先进先出的结构。这个正好就像现实生活中排队买票，谁先来排队，谁先买到票
• iOS开发中多线程的GCD和NSOperationQueue就是基于队列实现的
• 几个基本操作：enqueue、dequeue、isEmpty、peek、size

playground 代码实现

// 栈
class Stack<Element> {
    var stack:[Element]
    
    /// 检查栈空
    var isEmpty:Bool { return stack.isEmpty}
    
    /// 栈顶元素
    var peek: Element {return stack.last!}
    
    /// 栈大小
    var size: Int {return stack.count}
    
    /// 初始化
    init(){
        stack = [Element]()
    }
    
    /// push 压入
    func push(obejct:Element){
        stack.append(obejct)
    }
    
    /// pop 弹出
    func pop() -> Element? {
        return stack.popLast()
    }
    
    func print(){
        Swift.print("Stack = \(stack)")
    }
}

// 队列
var myStack:Stack = Stack<Any>()

myStack.push(obejct: "1")
myStack.push(obejct: "2")
myStack.push(obejct: "3")

myStack.print()

myStack.pop()

myStack.print()

class Queue<Element> {
    var left:[Element]
    var right:[Element]
    /// 队列是否为空
    var isEmpty:Bool { return left.isEmpty && right.isEmpty }
    /// 队列长度
    var size:Int { return left.count + right.count }
    /// 队列顶元素
    var peek : Element? {return left.isEmpty ? left.first : right.last}
    
    init(){
        left = [Element]()
        right = [Element]()
    }
    
    /// 入队
    func enqueue(object: Element){
        right.append(object)
    }
    
    /// 出队
    func dequeue() -> Element? {
        if left.isEmpty {
            left = right.reversed()
            right.removeAll()
        }
        
        return left.popLast()
    }
    
    func print(){
        let tempQ = left.reversed()+right
        Swift.print("Queue = \(tempQ)")
    }
}

var myQueue = Queue<Any>()
myQueue.enqueue(object: "1")
myQueue.enqueue(object: "2")
myQueue.enqueue(object: "3")

myQueue.print()

myQueue.dequeue()
myQueue.print()
myQueue.enqueue(object: "4")
myQueue.print()
myQueue.dequeue()
myQueue.print()

Stack = ["1", "2", "3"]
Stack = ["1", "2"]
Queue = ["1", "2", "3"]
Queue = ["2", "3"]
Queue = ["2", "3", "4"]
Queue = ["3", "4"]