队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

image.png

队列的假溢出

这里先设计一个简单的队列。
拥有头指针front:指向头部，尾指针rear。

image.png

如上图所示
当front和rear都指向了同一个元素，判为空。
当入队时，rear向后移动，指向新元素。
当出队时，front指向下一个元素。
当C4,C5,C6相继入队，C3,C4相继出队后，出现一个问题著名的假溢出问题，明明队列未满，却无法再继续入队。

要解决这个问题也很简单。
将之前的普通队列设计为循环队列。

循环队列

image.png

判断队列为空

当rear和front指向一致，判断队列为空。

判断队满

判断队满这里有个特别的设计，在队列中，空出一格空间。以防front和rear在堆满时指向一致。

image.png

顺序循环队列的实现

let MAXSIZE = 5

enum Status {
    case OK
    case Error
}

struct MyQueue<T> {
    
    private var data:[T?]
    var front:Int = 0
    var rear:Int = 0
    
    //初始化方法
    init() {
        data = Array.init(repeating: nil, count: MAXSIZE)
    }
    
    ///清空队列
    mutating func clearQueue() -> Status {
        self.front = 0
        self.rear = 0
        return .OK
    }
    
    ///判断队列是否为空
    var isEmpty:Bool {
        return front == rear
    }
    
    ///队列长度
    var length:Int {
        return (rear - front + MAXSIZE)%MAXSIZE
    }
    
    ///获取头部
    var head:T? {
        if front == rear {
            return data[front]
        }
        
        return nil
    }
    
    //入队
    mutating func enQueue(e:T) -> Status {
        
        //队列已满
        if (rear+1)%MAXSIZE == front {
            return .Error
        }
        
        //将元素e赋值给队尾
        data[rear] = e
        
        rear = (rear + 1)%MAXSIZE
        
        return .OK
    }
    
    //出队
    mutating func deQueue() -> T? {
        if front == rear {
            return nil
        }
        
        let result:T = data[front]!
        front = (front + 1) % MAXSIZE
        return result
    }
    
    //遍历
    func traverse() {
        var i = front
        while ((i%MAXSIZE) != rear) {
            if data[i] != nil {
                print("data === \(data[i]!)")
            }
            i += 1
        }
    }
}

检测一下

var queue = MyQueue<Int>()
queue.enQueue(e: 1)
queue.enQueue(e: 3)
queue.enQueue(e: 8)
queue.enQueue(e: 12)
queue.traverse()

queue.deQueue()
print("did出队")

queue.traverse()

打印结果

image.png

链式队列

image.png