栈

LIFO（后进先出）

struct Stack<T>{
    var items = [T]()
    var top:T?{
        get
        {
            return items.last
        }
    }
    var isEmpey:Bool {
        get {
            return items.isEmpty
        }
    }
    var size:Int {
        get {
            return items.count
        }
    }
    
   mutating func push(_ newItem: T){
        items.append(newItem)
    }
    
    mutating func pop() ->T?{
        return items.popLast()
    }
}

//  test.stack
var stack = Stack<String>()
print(stack.isEmpey)
print(stack.size)
print(stack.top as Any)

stack.push("l")
stack.push("o")
stack.push("v")
stack.push("e")
print(stack.isEmpey)
print(stack.size)
print(stack.pop()!)
print(stack.size)

队列

FIFO（先进先出）

struct Queue{
    var queue = [Any]()
    var isEmpty:Bool  {
        get {
            return queue.isEmpty
        }
    }
    var size:Int {
        get {
            return queue.count
        }
    }
    
    var peek:Any?{
        get{
            return queue.first
        }
    }
    
    mutating func enqueue(_ newItem:Any){
        queue.append(newItem)
    }
    
    mutating func dequeue() -> Any?{
        return queue.removeFirst()
    }
}

var queue = Queue()
print(queue.isEmpty)
print(queue.size)
print(queue.peek as Any)
queue.enqueue(1)
queue.enqueue("love")
queue.enqueue(2)
queue.dequeue()
print(queue)

队列与栈相互的实现

栈 - 队列实现

struct Q_stack{
    var queueA:Queue //主操作队列 用来入栈  出栈先出队只保留最先进入队列的数，即栈顶元素
    var queueB:Queue //协助队列 用来装未操作的栈元素
    init(){
        queueA = Queue()
        queueB = Queue()
    }
    
    mutating func shift(){
        while queueA.size != 1 {
            queueB.enqueue(queueA.dequeue()!)
        }
    }
    mutating func swap(){
        (queueB,queueA) = (queueA,queueB);
    }
    
    var isEmpty:Bool{
        get{
            return queueB.isEmpty && queueA.isEmpty
        }
    }
    
    var size:Int{
      mutating get{
            return queueA.size
        }
    }
    
    var top:Any?{
      mutating get{
            shift()
            let peekVal = queueA.peek
            queueB.enqueue(queueA.dequeue()!)
            swap()
            return peekVal
        }
    }
    
   mutating func push(_ newItem: Any)  {
        queueA.enqueue(newItem)
    }
    
    mutating func pop() -> Any?{
        shift()
        let popVal = queueA.dequeue()
        swap()
        return popVal
    }
}

var q_stack = Q_stack()
print(q_stack.isEmpty)
print(q_stack.size)
q_stack.push(10)
print(q_stack.size)
q_stack.push("sss")
print(q_stack.top as Any)
print(q_stack.pop() as! String)
print(q_stack.pop() as Any)

队列 - 栈实现

struct S_queue<T>{
    var stackA:Stack<T>
    var stackB:Stack<T>
    
    init() {
        stackA = Stack<T>()
        stackB = Stack<T>()
    }
    
    mutating func shift(){
        while !stackB.isEmpey {
            stackA.push(stackB.pop()!)
        }
    }
    
    var isEmpty :Bool{
        get{
            return stackA.isEmpey && stackB.isEmpey
        }
    }
    var size:Int {
        get{
            return stackA.size + stackB.size
        }
    }
    var peek:Any?{
       mutating get{
            shift()
        return stackA.top
        }
    }
    
   mutating func enqueue(_ newItem:T){
        stackB.push(newItem)
    }
    
    mutating func dequeue() -> T?{
        shift()
        return stackA.pop()
    }
}

var s_queue = S_queue<String>()
print(s_queue.isEmpty)
print(s_queue.size)
print(s_queue.peek as Any)
s_queue.enqueue("love")
s_queue.enqueue("i")
s_queue.enqueue("you")
print(s_queue.dequeue()!)
print(s_queue.size)
print(s_queue.peek!)
print(s_queue.dequeue()!)
print(s_queue.dequeue()!)

相关算法题

简化文件路径 "/a/./b/../../c/" -> "/c"

func simplifyPath(_ pathStr:String) -> String{
    var pathStack = Stack<String>()
    let pathArr = pathStr.components(separatedBy: "/")
    for path in pathArr{
        guard path != "." else {
            continue
        }
        if path == ".." {
            if pathStack.size > 0 {
                pathStack.pop()
            }
        }
        else if path != ""{
            pathStack.push(path)
        }
    }
    
//    let res = pathStack.items.reduce("") { (total, dir) -> String  in
//        return "\(total)/\(dir)"
//    }
    let res = pathStack.items.reduce("") { 
        return "\($0)/\($1)"
    }


    return res.isEmpty ? "/": res
}
print(simplifyPath("/a/./b/./../c/"))
print(simplifyPath("/a/./b/../../../c/"))

iOS面试之道学习笔记