参考链接
像栈一样，队列（queue）也是一种线性表，它的特性是先进先出，插入在一端，删除在另一端。就像排队一样，刚来的人入队（push）要排在队尾(rear)，每次出队(pop)的都是队首(front)的人。如图1，描述了一个队列模型。
img
和栈一样，队列也有数组实现和链表实现两种，两种实现都能给出快速的O(1)运行时间，区别在于链表实现指针域要占用空间，频繁的new和delete会消耗不少的时间开销，数组实现唯一的缺点是建立时要确定空间大小。
假如一个队列最多只能站10个人，当占满10个人后，第11个人就不能入队，这种情况成为溢出。而如果第一个人出队了，剩下的9个人依然还在原来的位置，队列里空出了一个位置，但第11个人还是不能入队，这种情况成为假溢出。克服假溢出有效的办法是使用循环队列。
循环队列就是把队尾和队首连接起来，形成一个环，队尾的下一个位置就是队首，这样可以有效的防止假溢出现象，但队列的实际容量已然固定。
队列的实现
队列的数组实现和栈差不多，不同的是，栈用top做下标，队列用front和rear作为下标。
/// 用链表实现的队列
public class YYQueue<T> {
private var container = YYList<T>()
public var count: Int { container.length }
public var isEmpty: Bool { container.isEmpty }
public func push(node: T) {
container.append(node)
}
public func pop() -> T? {
container.pop()
}
public func front() -> T? {
container.head?.value
}
public func rear() -> T? {
container.tail?.value
}
public func cleanup() {
container.cleanup()
}
}
/// 用数组实现的队列
public class YYQueue2<T> {
private var container = [T]()
public var count: Int { container.count }
public var isEmpty: Bool { container.isEmpty }
public func push(node: T) {
container.append(node)
}
public func pop() -> T? {
container.removeFirst()
}
public func front() -> T? {
container.first
}
public func rear() -> T? {
container.last
}
public func cleanup() {
container.removeAll()
}
}
