栈与队列

栈

• 特性： LIFO, 后进先出。比较形象点的比喻就是：洗盘子。你会将洗干净的盘子放在最上面，而你需要用盘子的时候，也是拿最上面的。
• 实现：可以用数组，向量，链表等方式实现
• 操作：
  1. push: 将元素X放入栈顶
  2. pop: 将栈顶元素移除栈
  3. top: 获取栈顶元素

用数组实现栈

数组S，top为数组最后一个元素的下标。

• push操作： ++top; S[top] = X;
• pop操作： --p; (每次进行pop操作之前，必须判断数组是否为空，则：top == -1)

swift 用数组实现栈

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? {
        // 数组不为空时，返回并移除最后一个元素；空时，返回nil
        return array.popLast()
    }
    
    public var top: T? {
        //数组不为空时，返回最后一个元素；空时，返回nil
        return array.last
    }
}

// 使用时，指定 T 的类型
var stackStr = Stack<Character>()
let stackInt = Stack<Int>()

队列

• 特性：FIFO，先进先出。

• 实现： 可以用数组，向量，链表，双编队列等实现。但是难度比较大，还是推荐用语言现有的队列。

• 操作：

  1. push: 在队尾添加一个元素。
  2. pop: 弹出队首元素。
  3. empty: 空队列
  4. full: 满队列

用数组实现队列

用有限大小的缓冲区来做例子，用Q数组实现缓冲区。队首front, 队尾nail(指向最后一个元素的下一个位置)

• push操作：将元素X放到队尾, nail 指向下一个位置。如果说原本nail就指向数组最后一个位置，添加了元素后，则应该指向数组第一个位置，用来实现循环队列。

Q[nail] = X;

// 用判断比取模运行更快，nail = (nail + 1) % Q.size()
++nail; 
if (nail == Q.size())  nail = 0;  

• pop操作： 弹出队首元素

// 用判断比取模运行更快，front = (front + 1) % Q.size()
++front; 
if (front == Q.size())  front = 0;

• empty判断：如果数组中只剩下一个元素，然后执行pop操作，就是空队列了，也就是说front 与nail 指向同一个位置。

bool func isEmpty {
    return front == nail;
}

• full判断：如果数组中还差一个元素就满了，然后再执行push操作，就是满队列了，也就是说nail 与front指向同一个位置。但是，这个条件与空队列的判断条件一致。
  原因：
  出现这种情况可以用抽屉原理来解释：假设确定了frant的值，而nail的取值情况有Q.size()种可能，而队列有Q.size() + 1中状态。将N+ 1种状态放置在N种可能中，必然会造成有两种状态出现重复的情况。
  解决:
  1. 采用空一个元素的方式，也就是当数组还有一个空置位置的时候，nail + 1 == front 就宣布队列已经满了，让队列减少一个状态。

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

2. 设置计数器count, 计算队列的元素个数。在push操作时，++count; 在pop操作时, --count。所以，count == 0时，为空队列。当count == Q.size()时，为满队列。

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

    // 用判断比取模运行更快，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 用数组实现队列

struct Queue<T> {
    public var count: Int   // 计数器，用来判断队列是否已满
    fileprivate var array = [T]()
    
    public var isEmpty: Bool {
        // 数组是空时，队列为空
        return array.count == 0
    }
    
    public var isFull: Bool {
        return count == array.count
    }

    public mutating func push(_ element: T) {
        if !isFull {
            // 数组没有满时，可添加元素
            array.append(element)
        }
    }
    
    public mutating func pop() -> T? {
        if !isEmpty {
            //数组非空时，可移除元素
            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)