队列（Queue）

首发于：2020-08-03

概念

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

队列的数据元素又称为队列元素。在队列中插入一个元素称为入队，删除一个元素称为出队。因为队列只允许在一端进行插入，在另一端进行删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出线性表（FIFO——first in first out）

顺序队列

下面是一个以数组方式实现的一个简单的顺序队列，功能是实现了但是我认为这与队列的定义还是有些区别，因为没有指针的体现：

const Queue = (function () {
    let items = []
    class Queue {
        constructor() {
            // 队列的数据
            items = []
        }
    
        // 向队列的尾部添加新的项
        enqueue(item) {
            items.push(item)
        }
    
        // 移除队列头部项并返回
        dequeue() {
            return items.shift()
        }
    
        // 返回队列最前面的项
        front() {
            return items[0]
        }
    
        // 返回队尾项
        rear() {
            return items[items.length - 1]
        }
    
        // 队列是否为空
        isEmpty() {
            return items.length === 0
        }
    
        // 队列长度
        size() {
            return items.length
        }
    
        // 清空队列
        clear() {
            items = []
        }
    
        // 查看队列中所有元素
        toString() {
            return items.toString()
        }
    }
    return Queue
})()

const queue = new Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.front()
queue.rear()
queue.size()
queue.isEmpty()
queue.toString()
queue.dequeue()
queue.clear()

下面是一个完全按照定义来实现的队列：

class Queue {
    constructor(n) {
        // 队列的数据
        this.items = []
        // 队头下标
        this.head = 0
        // 队尾下标
        this.tail = 0
        // 队列大小
        this.n = n
    }

    // 向队列的尾部添加新的项
    enqueue(item) {
        // tail 等于 size 代表队列已满
        // if (this.tail === this.n) return false
        // this.items[this.tail] = item
        // this.tail++
        // return true

        // 数据搬移进行优化，避免数组还有空闲但无法添加数据的情况
        if (this.tail === this.n) {
            // 队列到末尾了，没有空间了
            if (this.head === 0) return false // 整个队列都占满了
            // 数据搬移
            for (let i = this.head; i < this.tail; i++) {
                this.items[i - this.head] = this.items[i]
                delete this.items[i]
            }
            // 数据搬移完成之后重新更新 head 和 tail
            this.tail -= this.head
            this.head = 0   
        }
        this.items[this.tail] = item
        this.tail++
        return true
    }

    // 移除队列头部项并返回
    dequeue() {
        // head 等于 tail 代表队列为空
        if (this.head === this.tail) return null
        let res = this.items[this.head]
        delete this.items[this.head]
        this.head++
        return res
    }

    // 返回队列最前面的项
    front() {
        return this.items[this.head]
    }

    // 返回队尾项
    rear() {
        return this.items[this.tail]
    }

    // 队列是否为空
    isEmpty() {
        return this.tail === this.head
    }

    // 队列长度
    size() {
        return this.n
    }

    // 清空队列
    clear() {
        this.items = []
        this.head = 0
        this.tail = 0
    }

    // 查看队列中所有元素
    toString() {
        return this.items.toString()
    }
}

const queue = new Queue(10)
queue.enqueue(1)
queue.enqueue(2)
queue.front()
queue.rear()
queue.size()
queue.isEmpty()
queue.toString()
queue.dequeue()
queue.clear()

当front = rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。虽然数据搬移是一种解决方案，但是入队性能会受到影响，在实际使用队列时，为了使队列空间能高效的重复使用，一般使用循环队列。

循环队列

循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

在循环队列中，当队列为空时，有 front = rear，而当所有队列空间全占满时，也有 front = rear。为了区别这两种情况，规定循环队列最多只能有MaxSize - 1 个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front = rear，而队列判满的条件是 front =（rear + 1) % MaxSize。

class CircularQueue {
    constructor(n) {
        // 队列的数据
        this.items = []
        // 队头下标
        this.head = 0
        // 队尾下标
        this.tail = 0
        // 队列大小
        this.n = n
    }

    // 向队列的尾部添加新的项
    enqueue(item) {
        // 队列满了
        if ((this.tail + 1) % this.n === this.head) {
            return false
        } else {
            this.items[this.tail] = item
            this.tail = (this.tail + 1) % this.n
            return true
        }
    }

    // 移除队列头部项并返回
    dequeue() {
        if (this.tail === this.head && !this.items[this.head]) {
            // 队列为空
            return false
        } else {
            let res = this.items[this.head]
            delete this.items[this.head]
            this.head = (this.head + 1) % this.n
            return res
        }
    }

    // 返回队列最前面的项
    front() {
        return this.items[this.head]
    }

    // 返回队尾项
    rear() {
        let rear = this.tail - 1
        return this.items[rear < 0 ? this.n - 1 : rear]
    }

    // 队列是否为空
    isEmpty() {
        return this.tail === this.head
    }

    // 队列长度
    size() {
        return this.n
    }

    // 清空队列
    clear() {
        this.items = []
        this.head = 0
        this.tail = 0
    }

    // 查看队列中所有元素
    toString() {
        return this.items.toString()
    }
}

const queue = new CircularQueue(10)
queue.enqueue(1)
queue.enqueue(2)
queue.front()
queue.rear()
queue.size()
queue.isEmpty()
queue.toString()
queue.dequeue()
queue.clear()

链表队列

基于链表实现的队列，我们同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。

/**
 * 单向链表顺序队列
 */
class LinkedListQueue {
    constructor(n) {
        // 队列的数据
        this.list = new SinglyLinkedList() // 见链表单链表代码实现
        // 队头下标
        this.head = this.list.head
        // 队尾下标
        this.tail = this.list.head
        // 队列大小
        this.n = n
    }

    // 向队列的尾部添加新的项
    enqueue(item) {
        if (this.list.getLength() === this.n) return false
        this.list.append(item)
        this.tail = this.list.findLast()
        return true
    }

    // 移除队列头部项并返回
    dequeue() {
        // head 等于 tail 代表队列为空
        if (this.head === this.tail) return null
        let data = this.head.next.data
        this.head = this.head.next
        this.list.remove(data)    
        return true
    }

    // 返回队列最前面的项
    front() {
        return this.head
    }

    // 返回队尾项
    rear() {
        return this.tail
    }

    // 队列是否为空
    isEmpty() {
        return this.tail === this.head
    }

    // 队列长度
    size() {
        return this.n
    }

    // 清空队列
    clear() {
        this.list = new SinglyLinkedList()
        this.head = this.list.head
        this.tail = this.list.head
    }

    // 查看队列中所有元素
    toString() {
        return this.list.display()
    }
}

const llq = new LinkedListQueue(2)
llq.enqueue(1)
llq.enqueue(2)
llq.enqueue(3)
llq.toString()
llq.dequeue()
llq.dequeue()
llq.dequeue()
llq.toString()

队列（Queue） ​

概念 ​

顺序队列 ​

循环队列 ​

链表队列 ​

队列（Queue）

概念

顺序队列

循环队列

链表队列