栈
- 特性： LIFO, 后进先出。比较形象点的比喻就是：洗盘子。你会将洗干净的盘子放在最上面，而你需要用盘子的时候，也是拿最上面的。
- 实现：可以用数组，向量，链表等方式实现
- 操作：
- push: 将元素X放入栈顶
- pop: 将栈顶元素移除栈
- 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，先进先出。
实现： 可以用数组，向量，链表，双编队列等实现。但是难度比较大，还是推荐用语言现有的队列。
-
操作：
- push: 在队尾添加一个元素。
- pop: 弹出队首元素。
- empty: 空队列
- 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种可能中，必然会造成有两种状态出现重复的情况。
解决:- 采用空一个元素的方式，也就是当数组还有一个空置位置的时候，nail + 1 == front 就宣布队列已经满了，让队列减少一个状态。
bool func isFull {
return front == (nail + 1 == Q.size() ? 0 : nail + 1);
}
- 设置计数器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)
