数据结构算法--006：队列的顺序及链式存储 - 《数据结构算法》

1. 假溢出与循环队列
- 1.1 假溢出
- 1.2 循环队列
2. 顺序队列
3. 链式队列
总结

1. 假溢出与循环队列

队列的特点是先进先出（FIFO），只能从队列头读取元素，插入元素追加到队列尾

队列中存在两个指针，front表示队列头，rear表示队列尾

1.1 假溢出

顺序队列的操作问题：

假设队列长度为5，当front和rear都指向位置0，表示当前队列为空，当front == rear，表示当前队列已满
将C1、C2、C3相继入队，此时front位置不变，rear指向位置3
将C1、C2相继出队，此时front指向位置2，rear指向位置3
将C4、C5、C6相继入队，然后C3、C4相继出队，此时front指向位置4，rear指向位置5
此时的问题，队列中位置0 ~ 位置3都是空位，但元素无法入队

当出队速度大于入队速度，就会出现上述问题，我们称之为“假溢出”

1.2 循环队列

解决顺序队列的假溢出问题，可以将顺序队列理解成一个环

此时我们构成了一个循环队列，里面的向量称之为循环向量

在循环队列中，头尾指针和向量的关系是不变的，只是读取方式发生了一些变化

使用(rear + 1) % MAXSIZE表示队尾
当front == rear，表示当前队列为空
当队列存满时，front和rear也会指向相同位置，这会导致我们无法区分当前队列是满还是空。所以对于一个非空队列，我们永远不能让它的头尾相遇。我们可以将队列中预留一个空位，当(rear + 1) % MAXSIZE == front，表示当前队列已满

示例：

当循环队列为空时，front和rear都指向位置0
当三个元素入队，front位置不变，rear指向位置3
当一个元素出队，front指向位置1，rear位置不变
如果队列存满，就会导致头尾相遇，此时无法判断队满还是队空
正确的做法，牺牲一个存储单元。当(rear + 1) % MAXSIZE == front，表示当前队列已满

2. 顺序队列

顺序队列为了避免“假溢出”问题，从逻辑上需要设计成循环队列的形式。为了区别队空和队满的情况，需要牺牲一个存储单元，永远不能让它的头尾相遇

2.1 创建

class LinearQueue<Element>{
    fileprivate var _data : UnsafeMutablePointer<Element>;
    fileprivate var _capacity : Int;
    fileprivate var _front : Int;
    fileprivate var _rear : Int;
    var length : Int {
        get{
            return (_rear - _front + _capacity) % _capacity;
        }
    }
    init(capacity : Int){
        _capacity = capacity + 1;
        _data = UnsafeMutablePointer<Element>.allocate(capacity: _capacity);
        _front = 0;
        _rear = 0;
    }
    func clear(){
        _front = 0;
        _rear = 0;
    }
    func isEmpty() -> Bool{
        return _front == _rear;
    }
    func isFull() -> Bool{
        let last = (_rear + 1) % _capacity;
        return last == _front;
    }
    fileprivate func move(n : inout Int){
        n = (n + 1) % _capacity;
    }
}

2.2 获取元素

class LinearQueue<Element>{
    func getHead() -> Element?{
        if(isEmpty()){
            return nil;
        }
        return _data.advanced(by: _front).pointee;
    }
}

2.3 入队 & 出队

class LinearQueue<Element>{
    func enter(element : Element) -> Int{
        if(isFull()){
            return ERROR;
        }
        _data.advanced(by: _rear).pointee = element;
        move(n: &_rear);
        return OK;
    }
    func out() -> Element?{
        let data = getHead();
        if(data == nil){
            return data;
        }
        move(n: &_front);
        return data;
    }
}

2.4 元素遍历

class LinearQueue<Element>{
    func traverse() -> String {
        var str : String = "";
        if(isEmpty()){
            return str;
        }
        var n = _front;
        while(n != _rear){
            let val = _data.advanced(by: n).pointee;
            str += "\(val),"
            move(n: &n);
        }
        return str;
    }
}

3. 链式队列

链式队列不存在“假溢出”问题，因为链式队列没有存储长度的限制

链式队列本质上就是一个单向链表，逻辑比单向链表更简单，因为它只能删除队头，只能在队尾插入

front指向头结点，rear指向尾结点
创建链式队列，默认front和rear都指向头结点
当front和rear都指向头结点时，表示当前链式队列为空
出队时，删除的永远是首元结点，也就是front的后继
入队时，将rear的后继指向新结点，然后将rear指向新结点

2.1 创建

class LinkedQueue<Element>{
    fileprivate class Node<T> {
        var next : Node<T>?;
        var data : T?;
        init(){
        }
        init(data : T){
            self.data = data;
            self.next = nil;
        }
        deinit {
            print(data == nil ? "头结点释放" : "值为\(data!)的Node释放");
        }
    }
    fileprivate var _front : Node<Element>?;
    fileprivate var _rear : Node<Element>?;
    fileprivate var _count : Int;
    var length : Int {
        get{
            return _count;
        }
    }
    init(){
        _front = Node();
        _rear = _front;
        _count = 0;
    }
    func clear(){
        _front?.next = nil;
        _rear = _front;
        _count = 0;
    }
    func destory(){
        _front = nil;
        _rear = nil;
        _count = 0;
    }
    func isEmpty() -> Bool {
        return _front?.next == nil;
    }
}

2.2 获取元素

class LinkedQueue<Element>{
    func getHead() -> Element?{
        if(isEmpty()){
            return nil;
        }
        return _front?.next?.data;
    }
}

2.3 入队 &出队

class LinkedQueue<Element>{
    func enter(element : Element) -> Int {
        let node = Node(data: element);
        _rear?.next = node;
        _rear = node;
        _count += 1;
        return OK;
    }
    func out() -> Element?{
        let data = getHead();
        if(data == nil){
            return data;
        }
        _front?.next = _front?.next?.next;
        _count -= 1;
        if(isEmpty()){
            _rear = _front;
        }
        return data;
    }
}

2.4 元素遍历

class LinkedQueue<Element>{
    func traverse() -> String {
        var str : String = "";
        if(isEmpty()){
            return str;
        }
        var node = _front?.next;
        while(node != nil){
            str += "\(node!.data!),"
            node = node?.next;
        }
        return str;
    }
}

总结

假溢出：

顺序队列有存储长度的限制。当出队速度大于入队速度，即使队列中有空位，元素也无法入队。这种问题我们称之为“假溢出”

循环队列：

解决顺序队列的假溢出问题，可以将顺序队从逻辑上设置成循环队列
为了区分队空和队满，需要牺牲一个存储单元，永远不能让它的头尾相遇
当front == rear，表示当前队列为空
当(rear + 1) % MAXSIZE == front，表示当前队列已满

链式队列：

链式队列不存在“假溢出”问题，因为链式队列没有存储长度的限制
链式队列本质上就是一个单向链表，逻辑比单向链表更简单，因为它只能删除队头，只能在队尾插入
当front和rear都指向头结点时，表示当前链式队列为空
出队时，删除的永远是首元结点，也就是front的后继 
入队时，将rear的后继指向新结点，然后将rear指向新结点