剑指offer—面试题9: 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

在Swift中是没有栈的，但我们可以通过用数组实现一个栈，如下面代码：

public struct Stack<T> {
    fileprivate var array = [T]()
    
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    public var count: Int {
        return array.count
    }
    
    public mutating func push(_ element: T){
        array.append(element)
    }
    
    public mutating func pop() -> T? {
        return array.popLast()
    }
    
    public var top: T? {
        array.last
    }
}

栈的特性在于FILO(先进后出)，栈顶的数据总是先弹出来。队列则是FIFO(先进先出)。我们每次往第一个栈里插入元素后，第一个栈的底部元素是最后插入的元素，第一个栈的顶部元素是下一个待删除的元素。为了维护队列先进先出的特性，我们引入第二个栈，用第二个栈维护待删除的元素，在执行删除操作的时候我们首先看下第二个栈是否为空。如果为空，我们将第一个栈里的元素一个个弹出插入到第二个栈里，这样第二个栈里元素的顺序就是待删除的元素的顺序，要执行删除操作的时候我们直接弹出第二个栈的元素返回即可。

下面是代码实现：

class CQueue {

    var stack1 : Stack<Int>
    var stack2 : Stack<Int>
    
    init() {
        stack1 = Stack<Int>()
        stack2 = Stack<Int>()
    }
    
    func appendTail(_ value: Int) {
        stack1.push(value)
    }
    
    func deleteHead() -> Int {
        if stack1.isEmpty && stack2.isEmpty {
            return -1
        }
        
        if stack2.isEmpty {
            while !stack1.isEmpty {
                let temp = stack1.pop()!
                stack2.push(temp)
            }
        }
        
        let res = stack2.pop()!
         
         return res
    }
}