棧

• 特性： LIFO, 后進(jìn)先出。比較形象點(diǎn)的比喻就是：洗盤(pán)子。你會(huì)將洗干凈的盤(pán)子放在最上面，而你需要用盤(pán)子的時(shí)候，也是拿最上面的。
• 實(shí)現(xiàn)：可以用數(shù)組，向量，鏈表等方式實(shí)現(xiàn)
• 操作：
  1. push: 將元素X放入棧頂
  2. pop: 將棧頂元素移除棧
  3. top: 獲取棧頂元素

用數(shù)組實(shí)現(xiàn)棧

數(shù)組S，top為數(shù)組最后一個(gè)元素的下標(biāo)。

• push操作： ++top; S[top] = X;
• pop操作： --p; (每次進(jìn)行pop操作之前，必須判斷數(shù)組是否為空，則：top == -1)

swift 用數(shù)組實(shí)現(xiàn)棧

struct Stack<T> {
    // 對(duì)數(shù)組進(jìn)行初始化
    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? {
        // 數(shù)組不為空時(shí)，返回并移除最后一個(gè)元素；空時(shí)，返回nil
        return array.popLast()
    }
    
    public var top: T? {
        //數(shù)組不為空時(shí)，返回最后一個(gè)元素；空時(shí)，返回nil
        return array.last
    }
}

// 使用時(shí)，指定 T 的類(lèi)型
var stackStr = Stack<Character>()
let stackInt = Stack<Int>()

隊(duì)列

• 特性：FIFO，先進(jìn)先出。

• 實(shí)現(xiàn)： 可以用數(shù)組，向量，鏈表，雙編隊(duì)列等實(shí)現(xiàn)。但是難度比較大，還是推薦用語(yǔ)言現(xiàn)有的隊(duì)列。

• 操作：

  1. push: 在隊(duì)尾添加一個(gè)元素。
  2. pop: 彈出隊(duì)首元素。
  3. empty: 空隊(duì)列
  4. full: 滿隊(duì)列

用數(shù)組實(shí)現(xiàn)隊(duì)列

用有限大小的緩沖區(qū)來(lái)做例子，用Q數(shù)組實(shí)現(xiàn)緩沖區(qū)。隊(duì)首front, 隊(duì)尾nail(指向最后一個(gè)元素的下一個(gè)位置)

• push操作：將元素X放到隊(duì)尾, nail 指向下一個(gè)位置。如果說(shuō)原本nail就指向數(shù)組最后一個(gè)位置，添加了元素后，則應(yīng)該指向數(shù)組第一個(gè)位置，用來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列。

Q[nail] = X;

// 用判斷比取模運(yùn)行更快，nail = (nail + 1) % Q.size()
++nail; 
if (nail == Q.size())  nail = 0;  

• pop操作： 彈出隊(duì)首元素

// 用判斷比取模運(yùn)行更快，front = (front + 1) % Q.size()
++front; 
if (front == Q.size())  front = 0;

• empty判斷：如果數(shù)組中只剩下一個(gè)元素，然后執(zhí)行pop操作，就是空隊(duì)列了，也就是說(shuō)front 與nail 指向同一個(gè)位置。

bool func isEmpty {
    return front == nail;
}

• full判斷：如果數(shù)組中還差一個(gè)元素就滿了，然后再執(zhí)行push操作，就是滿隊(duì)列了，也就是說(shuō)nail 與front指向同一個(gè)位置。但是，這個(gè)條件與空隊(duì)列的判斷條件一致。
  原因：
  出現(xiàn)這種情況可以用抽屜原理來(lái)解釋?zhuān)杭僭O(shè)確定了frant的值，而nail的取值情況有Q.size()種可能，而隊(duì)列有Q.size() + 1中狀態(tài)。將N+ 1種狀態(tài)放置在N種可能中，必然會(huì)造成有兩種狀態(tài)出現(xiàn)重復(fù)的情況。
  解決:
  1. 采用空一個(gè)元素的方式，也就是當(dāng)數(shù)組還有一個(gè)空置位置的時(shí)候，nail + 1 == front 就宣布隊(duì)列已經(jīng)滿了，讓隊(duì)列減少一個(gè)狀態(tài)。

bool func isFull {
    return front == (nail + 1 == Q.size() ? 0 : nail + 1);
}

2. 設(shè)置計(jì)數(shù)器count, 計(jì)算隊(duì)列的元素個(gè)數(shù)。在push操作時(shí)，++count; 在pop操作時(shí), --count。所以，count == 0時(shí)，為空隊(duì)列。當(dāng)count == Q.size()時(shí)，為滿隊(duì)列。

func push(int x) {
    Q[nail] = x;

    // 用判斷比取模運(yùn)行更快，nail = (nail + 1) % Q.size()
    ++nail; 
    if (nail == Q.size())  nail = 0;  
        ++count;
}

func  pop() {
    ++front; 
    if (front == Q.size())  front = 0;
        --count;
}

bool func isFull() {
    return (count == Q.size());
}

bool func isEmpty () {
    return (count == 0);
}

Swift 用數(shù)組實(shí)現(xiàn)隊(duì)列

struct Queue<T> {
    public var count: Int   // 計(jì)數(shù)器，用來(lái)判斷隊(duì)列是否已滿
    fileprivate var array = [T]()
    
    public var isEmpty: Bool {
        // 數(shù)組是空時(shí)，隊(duì)列為空
        return array.count == 0
    }
    
    public var isFull: Bool {
        return count == array.count
    }

    public mutating func push(_ element: T) {
        if !isFull {
            // 數(shù)組沒(méi)有滿時(shí)，可添加元素
            array.append(element)
        }
    }
    
    public mutating func pop() -> T? {
        if !isEmpty {
            //數(shù)組非空時(shí)，可移除元素
            let first = array.first!
            array.removeFirst()
            
            return first
        }
        
        return nil
    }
    
    public var front: T? {
        return array.first
    }
    
    // 需要初始化 count 
    init(_ queueCount: Int) {
        self.count = queueCount
    }
}

// 使用queue 
var queueInt = Queue<Int>(10)
var queueStr = Queue<String>(20)