本文主要是如何使用swift数组来实现队列和栈：

栈：

• 数据先进后出，最后推进的元素是即将被推出的第一个元素；
• 一般一个栈主要实现一下三个方法：
  • push 将对象推入栈；
  • pop 将对象弹出栈；
  • peek 只查看栈的顶层元素；
    如下所示：

//栈：数据先进后出，犹如弹夹
class FMStack<T> {
    
    var dataArray:[T] = [T]()
    //Push  将对象推入堆栈相对比较简单。 在Stack中添加以下方法：
    func push(para:T) {
        dataArray.append(para)
    }
    //Peek 查看堆栈只能查看堆栈的顶层元素。 Swift数组有一个最后一个属性。
    func peek() ->T?{
        return dataArray.last
    }
    //弹出堆栈也很简单。 只需在push方法下，在Stack中添加以下方法：
    func pop() -> T?{
        return dataArray.popLast()
        
    }
    public var isEmpty:Bool {
        return dataArray.count == 0
    }
}

队列：

• 队列提供先进先出或先入先出的顺序。 首先插入的元素也是第一个出来的元素
• 同样一个栈也要实现三个基本的操作：
  • push 入队方法；
  • pop 出队方法；
  • peek 查看下一个出队对象，而不删除它；
    如下所示：

//队列：先进先出，好似排队
class FMQueue<T> {
    var dataArray:[T] = [T]()
    
    public var isEmpty:Bool {
        return dataArray.count == 0
    }
    public var size:NSInteger {
        return dataArray.count
    }
    func push(para:T) {
        self.dataArray.append(para)
    }
    func peek() -> T? {
        return dataArray.first
    }
    func pop() -> T? {
        if dataArray.count > 0 {
            let first = dataArray.first
            dataArray.remove(at: (0))
            return first
        }
        return nil
    }
}

注意：swift的数组中提供了方便获取第一个元素first、最后一个元素last、获取并删除popLast最后一个元素等方法，可以合理利用.
popLast与removeLast还是有区别的，popLast当数组为空使返回nil，而removeLast则要求数组必须不为空

    /// Removes and returns the last element of the collection.
    ///
    /// Calling this method may invalidate all saved indices of this
    /// collection. Do not rely on a previously stored index value after
    /// altering a collection with any operation that can change its length.
    ///
    /// - Returns: The last element of the collection if the collection is not
    /// empty; otherwise, `nil`.
    ///
    /// - Complexity: O(1)
    @inlinable public mutating func popLast() -> Element?

    /// Removes and returns the last element of the collection.
    ///
    /// The collection must not be empty.
    ///
    /// Calling this method may invalidate all saved indices of this
    /// collection. Do not rely on a previously stored index value after
    /// altering a collection with any operation that can change its length.
    ///
    /// - Returns: The last element of the collection.
    ///
    /// - Complexity: O(1)
    @inlinable public mutating func removeLast() -> Element

如何设计一个栈，要求在基本功能的基础上，再实现返回栈中最小元素的功能，要求push、pop、getMin的操作时间复杂度都是O(1)

思路：

• 在原有栈的基础上，再加一个栈，同步存储当前状态下数据的最小值；

  
  
  image.png
  
  

  代码如下：

class FMMinStack: NSObject {
    var data:FMStack = FMStack<Int>()
    var minData:FMStack = FMStack<Int>()
    func push(para: Int) {
        if minData.isEmpty {
            minData.push(para: para)
        }else{
            minData.push(para: getMin(para, minData.peek()!))
        }
        data.push(para: para)
    }
    func pop() -> Int? {
        _ = minData.pop()
        return data.pop()
    }
    func getMin() -> Int?{
        return minData.peek()
    }
    func peek() ->Int?{
        return data.peek()
    }
    private func getMin<T: Comparable>(_ a: T, _ b: T) -> T {
        return a < b ? a : b
    }
}

如何用栈结构实现队列结构

思路：

• 准备一个周转栈；
• 取：每次取的时候都从周转栈中取，每次取之前都要判断周转栈中是否有值，无值则从data原栈中导数据到周转栈中。
• 存：存数据则是存到data原栈；
• 看：每次看的时候也是都从周转栈中peek,单在没数据的时候优先从data原栈中导数据过来。

class FMStackToQueue: NSObject {
    var data:FMStack = FMStack<Int>()
    var zhouzhuanData:FMStack = FMStack<Int>()
    func push(para:Int){
        self.turnOverData()
        data.push(para: para)
    }
    func pop() -> Int? {
        self.turnOverData()
        return zhouzhuanData.pop()
    }
    func peek() -> Int? {
        self.turnOverData()
        return zhouzhuanData.peek()
    }
    var isEmpty:Bool {
        return zhouzhuanData.isEmpty && data.isEmpty
    }
    func turnOverData(){
        if zhouzhuanData.isEmpty {
            while data.peek() != nil {
                zhouzhuanData.push(para: data.pop()!)
            }
        }
    }
}

如何用队列结构实现栈结构

思路：

• 准备一个周转队列；
• 取：由于队列是先进先出，所以每次取的时候都把数据从原始data队列导入到周转队列中，但是要注意保留最后一个元素；并且将最后一个元素返回，为使存取方便，元素返回前，将原始data队列与周转队列交换（此时周转队列中存放的是原始数据，原始data队列此时无数据）；
• 存：存数据则是存到data原队列中；
• 看：由于队列是先进先出，所以每次peek的时候也是都把数据从原始data队列导入到周转队列中，也是要注意保留最后一个元素；并且将最后一个元素返回，但是此处又要注意由于是查看，所以查看完后要把该元素在push回周转队列，然后再做交换。

代码如下：

//[1,2,3,4,5,6,7,8,9]  ->
class FMQueueToStack:NSObject{
    var data:FMQueue = FMQueue<Int>()
    var zhouzhuanData:FMQueue = FMQueue<Int>()
    
    func push(para:Int){
        data.push(para: para)
    }
    func pop() -> Int? {
        while data.size > 1 {
            zhouzhuanData.push(para: data.pop()!)
        }
        let val = data.pop()
        let middleData = data
        data = zhouzhuanData
        zhouzhuanData = middleData
        return val
    }
    func peek() -> Int? {
        while data.size > 1 {
            zhouzhuanData.push(para: data.pop()!)
        }
        let val = data.pop()
        if val != nil {
            zhouzhuanData.push(para: val!)
        }
        let middleData = data
        data = zhouzhuanData
        zhouzhuanData = middleData
        return val
    }
}