数据结构之队列

这是我参与更文挑战的第12天，活动详情查看：更文挑战

什么是队列

队列是遵循FIFO先进先出原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

创建队列

首先声明最基本的类，并使用一个数组来存储队列中的元素。

function Queue() {
    let items = []
    // 这里是属性和方法
}
复制代码

接下来声明一些队列可用的方法：

• enqueue(): 向队列尾部添加一个或多个新的项。
• dequeue(): 移除队列的第一项（即排在队列最前面的）项，并返回被移除的元素。
• front(): 返回队列中第一个元素—最先被添加，也将是最先被移除的元素。队列不做任何变动。
• isEmpty(): 如果队列中不包含任何元素，则返回ture，否则返回false。
• size(): 返回队列包含的元素个数，与数组的length属性类似。

function Queue() {
    let items = []
    // 这里是属性和方法
    this.enqueue = function (ele) {
        items.push(ele)
    }
    this.dequeue = function () {
        return items.shift()
    }
    this.front = function () {
        return items[0]
    }
    this.isEmpty = function () {
        return !items.length
    }
    this.size = function () {
        return items.length
    }
    this.print = function () {
        console.log(items.toString())
    }
}
复制代码

通过上述代码，我们已将简单的实现了一个队列。那么接下来便是使用了。

队列的使用

我们将之前创建的Queue类进行实例化。

let queue = new Queue()
console.log(queue.isEmpty()) // true

queue.enqueue('John')
queue.enqueue('Tom')
queue.enqueue('Tony')

queue.print()
console.log(queue.size()) // 3
console.log(queue.isEmpty()) // false
queue.dequeue()
复制代码

从上述的代码输出我们可以验证到队列的先进先出规则。

优先队列

元素的添加和移除是基于优先级的。一个很现实的例子就是机场登机的顺序：头等舱和商务舱乘客的优先级要高于经济舱乘客。

优先队列的实现有两种选项：

• 设置优先级，然后在正确的位置添加元素。
• 用入列操作添加元素，然后按照优先级移除它们。

接下来我们来实现一个优先队列：

function PriorityQueue () {
    let items = []
    function QueueElement (element, priority) {
        this.element = element
        this.priority = priority
    }
    this.enqueue = function (element, priority) {
        let queueElement = new QueueElement(element, priority)
        if (this.isEmpty()) {
            items.push(queueElement)
        } else {
            let added = false
            for (let i = 0; i < items.length; i++) {
                if(queueElement.priority < items[i].priority) {
                    items.splice(i, 0, queueElement)
                    added = true
                    break
                }
            }
            if (!added) {
                items.push(queueElement)
            }
        }
    }
}
复制代码

默认的Queue类和PriorityQueue类实现上的区别是，要向PriorityQueue添加元素，需要创建一个特殊的元素 QueueElement。这个元素包含了要添加了要添加到队列的元素及其在队列中的优先级。

如果队列为空，可以直接将元素入列。否则，就需要比较该元素与其他元素的优先级。当找到一个比要添加的元素的priority值更大（优先级更低）的项时，就把新元素插入到它之前，并终止队列循环。

如果要添加元素的priority值大于任何已有的元素，把它添加到队列的末尾就行了。

let priorityQueue = new PriorityQueue()
priorityQueue.enqueue('John', 2)
priorityQueue.enqueue('Jack', 1)
priorityQueue.enqueue('Tom', 1)
复制代码

上述实现的优先队列称为最小优先队列，因为优先级的值较小的元素被放置在队列最前面（1代表更高的优先级）。最大优先队列与之相反，把最大的值较大的元素放置在队列最前面。