恋上数据结构与算法三（栈、队列）

• 栈
  一种特殊的线性表，只能在一端进行操作，后进先出原则

struct Stack<Element> {
    private var stack = [Element]()
    var isEmpty: Bool {
        return stack.isEmpty
    }
    var size: Int {
        return stack.count
    }
    mutating func push(item: Element) {
        stack.append(item)
    }
    mutating func pop() -> Element {
        return stack.removeLast()
    }
    //栈顶元素
    var peek: Element? {
        return stack.last
    }
}

队列

一种特殊的线性表，只能头尾两端操作，先进先出原则
双端队列：能在头尾两端添加、删除的队列

class Queue<Element> {
    var array: [Element]
    init() {
        array = []
    }
    var isEmpty: Bool {
        return array.isEmpty
    }
    var size: Int {
        return array.count
    }
    //队尾入队
    func enQueueRear(_ x: Element) {
        array.append(x)
    }
    //队头入队
    func enQueueFront(_ x: Element) {
        array.insert(x, at: 0)
    }
    //队尾出队
    func deQueueRear() -> Element {
        return array.removeLast()
    }
    //队头出队
    func deQueueFront() -> Element {
        return array.removeFirst()
    }
    //队列头元素
    var front: Element? {
        return array.first
    }
    //队尾元素
    var rear: Element? {
        return array.last
    }
}

循环队列：用数组实现并且优化之后的队列

练习

1.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串

/*
 1.遇见左字符，将左字符入栈
 2.遇见右字符
 如果栈是空的，说明括号无效
 如果栈不为空，将栈顶字符出栈，与右字符匹配
 如果左右字符不匹配，说明括号无效
 如果左右字符匹配，继续下一个字符
 3.所有字符遍历完
 栈为空，说明括号有效
 栈不为空，说明括号无效
 */
let mapper = ["(":")","[":"]","{":"}"]
func isValid(_ s: String) -> Bool {
    //栈
    var stack = [String]()
    for chr in s {
        //遇见左字符
        if mapper.keys.contains(chr.description) {
            stack.append(chr.description)
        }
        //遇见右字符
        else {
            if stack.isEmpty {
                return false
            } else {
                //stack出栈
                let element = stack.removeLast()
                if mapper[element] != chr.description {
                    return false
                }
            }
        }
    }
    return stack.isEmpty
}

2.括号的分数

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
"(())" 输出： 2
"()()" 输出： 2
"(()(()))" 输出： 6

/*
 用栈记录下方便查上次遍历的
 (()) level = 1 val = 1<<1 = 2
 ((())) level = 2 val = 1<<2 = 4
 (((()))) level = 3 val = 1<<3 = 8
 遍历后放入栈，遇到")"的时候看上一个是否是"("再计算值
 */
func scoreOfParentheses(_ S: String) -> Int {
    var level = 0
    var stack = [String]()
    var amount = 0
    for chr in S {
        if chr.description == "(" {
            level += 1
            stack.append(chr.description)
        } else {
            level -= 1
            print(stack.last)
            if stack.last == "(" {
                amount += (1<<level)
            }
            stack.append(chr.description)
        }
    }
    return amount
}

3.逆波兰表达式求值
4.基本计算器
5.用栈实现队列

/*
 准备2个栈 inStack outStack
 入队时，push到inStack
 出队时
 outStack为空，将inStack所有元素逐一弹出，push到outStack，outStack弹出栈顶元素
 outStack不为空，outStack弹出栈顶元素
 */
class MyQueue {
    var inStack: Stack<Int>
    var outStack: Stack<Int>
    /** Initialize your data structure here. */
    init() {
        inStack = Stack()
        outStack = Stack()
    }
    /** Push element x to the back of queue. */
    func push(_ x: Int) {
        inStack.push(item: x)
    }
    /** Removes the element from in front of queue and returns that element. */
    func pop() -> Int {
        if outStack.isEmpty {
            while !inStack.isEmpty {
                let element = inStack.pop()
                outStack.push(item: element)
            }
        }
        return outStack.pop()
    }
    /** Get the front element. */
    func peek() -> Int {
        if outStack.isEmpty {
            while !inStack.isEmpty {
                let element = inStack.pop()
                outStack.push(item: element)
            }
        }
        return outStack.peek!
    }
    /** Returns whether the queue is empty. */
    func empty() -> Bool {
        return inStack.isEmpty && outStack.isEmpty
    }
}

6.用队列实现栈

class MyStack {
    var queue = Queue()
    /** Initialize your data structure here. */
    init() {}
    /** Push element x onto stack. */
    func push(_ x: Int) {
        queue. enQueueRear(x)
    }
    /** Removes the element on top of the stack and returns that element. */
    func pop() -> Int {
        var queue2 = Queue()
        while queue.size > 1 {
            queue2. enQueueRear(queue. deQueueFront())
        }
        var temp = queue
        queue = queue2
        queue2 = temp
        return queue2.front!
    }
    /** Get the top element. */
    func top() -> Int {
        var queue2 = Queue()
        while queue.size > 1 {
            queue2. enQueueRear(queue. deQueueFront())
        }
        var val = queue.front
        queue2.push(queue. deQueueFront())
        queue = queue2
        return val!
    }
    /** Returns whether the stack is empty. */
    func empty() -> Bool {
        return queue.isEmpty
    }
}