队列与双端队列的实现-灵析社区

小乔学算法

前言

队列作为一种数据结构，在现实生活中它可应用于电影院、自助餐厅等场合，排在第一个的人会先接受服务。

在计算机应用领域里，多个文档的打印就是一个队列，排在第一的文档会先执行打印操作。

本文将用TypeScript实现队列与双端队列这两种数据结构，并用其解决计算机科学领域中的两道经典题，欢迎各位感兴趣的开发者阅读本文。

队列的实现

本文主要讲解队列用代码的实现，如果对队列这种数据结构不了解的开发者可以移步我的另一篇文章：栈与队列

实现思路

队列遵循先进先出(FIFO)原则，根据队列的特性，我们可以知道要实现一个队列必须具备以下方法：

入队，将一个新元素加入队列中(往对象中添加一个key)
出队，将队首的元素取出(根据key来获取)，并返回队首的元素。
判断队列是否为空，判断队列中的元素数量是否为0(队列大小 - 队首元素位置）
队首元素，获取当前队列的队首元素并返回。
队列大小，获取队列中的元素数量并返回(队列大小 - 队首元素位置)。
清空队列，删除队列中的所有元素。（初始化队列的内部变量）。
队列内所有元素，将队列中的元素用逗号拼接成字符串并返回(遍历队列中的元素)。

实现代码

有了思路，我们就可以编码了。

接下来，我们将上述实现思路转换为代码：

新建一个Queue.ts文件
使用接口声明队列内部对象类型

interface QueueObj {
    [propName: number] : any;
}

在构造器中声明并初始化队列需要的三个变量：队列大小、队首元素、队列对象

private count: number;
private lowestCount: number;
private items: QueueObj;
constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
}

实现入队函数（enqueue），参数为任意类型的数据，将队列的大小作为队列对象的key。

enqueue(item: any) {
    // 队列的末尾添加元素: 将队列的大小作为key
    this.items[this.count] = item;
    this.count++;
}

实现出队函数（dequeue），存储队首元素，移除队列对象中的队首元素key，队首元素位置自增。

dequeue() {
    if(this.isEmpty()){
        return undefined;
    }
    const result = this.items[this.lowestCount];
    // 删除队首元素
    delete this.items[this.lowestCount];
    // 队首元素自增
    this.lowestCount++;
    return result;
}

判断队列是否为空（isEmpty），判断当前队列大小 - 当前队首元素位置是否等于0

isEmpty() {
    return this.count - this.lowestCount === 0;
}

获取队首元素（peek），以当前队首元素位置为key获取队列队对象中的值并返回。

peek() {
    if(this.isEmpty()){
        return undefined;
    }
    return this.items[this.lowestCount];
}

获取队列大小（size），当前队列大小 - 队首元素位置

size() {
    return this.count - this.lowestCount;
}

清空队列（clear），初始化构造器中的三个变量。

clear() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
}

获取队列中的所有元素，遍历对象中的元素，用逗号拼接成字符串并返回。

toString() {
    if(this.isEmpty()){
        return "";
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++){
        objString = `${objString},${this.items[i]}`;
    }
    return objString;
}

完整代码请移步：Queue.ts

编写测试代码

队列实现后，接下来我们来测试下队列中的方法是否能正常运行。

// 队列执行测试
import Queue from "./lib/Queue.ts";

const queue = new Queue();
// 入队
queue.enqueue("队列中的第一条数据");
queue.enqueue("队列中的第二条数据");
queue.enqueue("队列中的第三条数据");

// 出队
queue.dequeue();

// 获取队首元素
console.log(queue.peek());

// 获取队列大小
console.log(queue.size());

// 获取队列中的所有元素
console.log(queue.toString());

// 判断队列中是否有数据
console.log(queue.isEmpty());

// 清空队列
queue.clear();

执行结果如下：

双端队列

双端队列是一种允许我们同时从前端和后端添加和移除元素的特殊队列。

双端队列同时遵守了先进先出和后进先出的原则，所以可以说它是一种把队列和栈相结合的一种数据结构。

现实中用到双端队列的例子有很多，例如电影院、餐厅排队的队伍。排队买电影票的人当他买到电影票后，离开了队伍，此时他想咨询一些其他小问题时，他可以直接去队伍的最前面咨询问题。排在队伍后面的人，临时有其他事情无法买票，他就会从队伍的末尾离开。

在计算机科学中，存储一系列的撤销操作就用到了双端队列，每当用户在软件中进行了一个操作，该操作就会被存储在一个双端队列中，当用户点撤销操作时，该操作会从队列的末尾弹出，在进行了预先定义的一定数量的操作后，最下执行的操作就会从队首移除。

实现思路

双端队列相比队列多了两端都可以出入元素，因此普通队列中的获取队列大小、清空队列、队列判空、获取队列中的所有元素这些方法同样存在于双端队列中且实现代码与之相同。

由于双端队列两端都可以出入元素，那么我们需要实现以下函数：

队首添加元素，添加元素时需要判断队列是否为空，以及队首元素是否为0。
队尾添加元素，等同于队列的入队操作。
获取队首元素，等同于队列的获取队首元素
获取队尾元素，等同于栈的获取栈顶操作。
删除队首元素，等同于出队操作。
删除队尾元素，等同与出战操作。

观察上述我们要实现的函数后，我们发现双端队列除了队首添加元素与之前我们实现的差别很大，其他的函数我们之前都已经实现过了，所以此处仅讲解队首添加元素的实现。

想了解其他函数的具体实现请移步我的另一篇文章：数组实现栈与对象实现栈的区别

队首添加元素的实现思路如下：

如果队列为空，直接调用队尾添加元素函数。
如果队首元素key大于0，则需要将当前队首元素key-1，然后将当前元素放入队列中。
如果队首元素key等于0，则需要将队列中的元素整体向后移动一位，空出0号key出来，队首元素重新赋值为0，然后将当前元素放入0号key中。

实现代码

接下来，我们将上述思路转换为代码。

新建一个Deque.ts文件
声明双端队列内部对象的类型

interface DequeObj {
    [propName: number]: any;
}

在构造器中声明双端队列需要用到的变量并初始化

private count: number;
private lowestCount: number;
private items: DequeObj;
constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
}

实现队首添加元素函数

addFront(item: any) {
    if (this.isEmpty()){
        this.addBack(item);
    }else if(this.lowestCount > 0){
        // 队首元素大于0
        this.lowestCount--;
        this.items[this.lowestCount] = item;
    }else{
        // 队首元素为0，我们需要将将队列里的0号key空出来，其他数据整体向后移动一位。
        for (let i = this.count; i > 0; i--){
            this.items[i] = this.items[i - 1];
        }
        // 队列长度自增
        this.count++;
        // 队首元素设为0
        this.lowestCount = 0;
        // 为队首的0号key添加当前元素
        this.items[0] = item;
    }
}

完整代码请移步：Deque.ts

编写测试代码

// 双端队列测试
import Deque from "./lib/Deque.ts";

const deque = new Deque();
// 队列为空的情况下，往队首添加元素
deque.addFront("队首添加元素");
console.log(deque.peekFront());

// 队尾添加元素
deque.addBack("队尾添加元素");
console.log(deque.peekBack());

// 队首元素等于0的情况往队首添加元素
deque.addFront("队首元素等于0添加元素");
console.log(deque.peekFront());

// 队首元素大于0，往队首添加元素
deque.removeFront();
deque.addFront("队首元素大于0添加元素");
console.log(deque.peekFront());

// 获取队列大小
console.log("队列大小:",deque.size())

// 队列末尾添加元素
deque.addBack("队列末尾添加元素")

// 获取队列中的所有元素
console.log("队列中的所有元素: ",deque.toString())

// 移除队首元素
deque.removeFront();

// 移除队尾元素
deque.removeBack();

// 获取队首元素
console.log("队首元素: ",deque.peekFront());

// 获取队尾元素
console.log("队尾元素: ",deque.peekBack());

执行结果如下：

解决问题

上面我们实现了队列和双端队列，接下来我们就通过两个例子来理解这两种数据结构。

队列实现击鼓传花游戏

由于队列经常被应用在计算机领域和我们的现实生活中，就出现了一些队列的修改版本。

例如循环队列，我们通过实现一个击鼓传花游戏来理解循环队列。

游戏规则

击鼓传花游戏的规则如下：

一群人围成一个圆圈，放一朵花在任意一个人手里。
开始打鼓，拿到花的人会把花尽快的传给旁边的人。
鼓声停止，这个时候花在谁手里，谁就退出圆圈，结束游戏。
重复这个过程，直至只剩下一个人，这个人就是游戏的获胜者。

实现思路

知道游戏规则后，我们来捋一下实现思路：

声明一个函数，参数为：参与人员数组，多少次为一轮
函数内部实例化一个队列，声明淘汰人员列表变量。
将参与人员入队(参与人员围成一个圆圈)
模拟击鼓传花，以传进来的次数为条件遍历队列，将队列的队顶元素追加至队尾(如果你将花传给了旁边的人，你被淘汰的威胁就立刻解除了)。
传进来的次数遍历完成(鼓声停止)，队首元素出栈，将队首元素追加至淘汰人员列表中。
队列中只剩下一个元素时，剩余元素出队，返回胜利者和淘汰者列表。

实现代码

实现思路捋清后，我们将上述思路转换为代码：

import Queue from "./lib/Queue.ts";

/**
 * 击鼓传花函数
 * @param nameList 参与人员列表
 * @param num 多少次为一轮
 * @returns {{eliminates: [], winner: string}}
 */
const hotPotato = (nameList=[], num=0)=> {
    // 实例化一个队列
    const queue = new Queue();
    // 淘汰人员列表
    const eliminateList = [];

    // 所有参与人员入队
    for (let i = 0; i < nameList.length; i++){
        queue.enqueue(nameList[i]);
    }

    // 队列的大小大于1就继续执行
    while (queue.size() > 1){
        // 模拟击鼓传花，给定一个数字，然后遍历队列，从队列开头移除一项，再将其添加到队列末尾。
        for (let i = 0; i < num; i++){
            // 将队首元素添加至队尾(如果你将花传给了旁边的人，你被淘汰的威胁就立刻解除了)
            queue.enqueue(queue.dequeue());
        }
        // 鼓声停止，传花结束，将当前手上有花的人(队首元素)淘汰。
        eliminateList.push(queue.dequeue());
    }
    // 游戏结束，返回淘汰者和胜利者
    return {
        eliminates: eliminateList,
        winner: queue.dequeue()
    }
}

编写测试代码

上面我们实现了击鼓传花游戏的函数，接下来我们来测下我们编写的函数是否正确。

const names = ["张三","李四","王五","朱六","郝七","刘八","彭九"];
// 每隔9次淘汰一轮
const result = hotPotato(names,9);
for (let i = 0; i < result.eliminates.length; i++){
    const name = result.eliminates[i];
    console.log(`${name}，在击鼓传花游戏中被淘汰`);
}
console.log(`游戏胜利者: ${result.winner}`);

完整代码请移步：Examples.js

执行结果如下：

双端队列实现回文检查器

回文是正反都能读通的单词、词组、数或一系列字符的序列，例如madam、racecar。

实现回文检测有多种方式，最简单的方式为：将字符串反向排列并检查他与原字符是否相同。如果两者相同那么它就是一个回文。

我们也可以用栈来解决这个问题，但是如果用数据结构来解决回文问题的话，使用双端队列是最简单的。

实现思路

回文的规则是正反都能读通，那么我们可以将字符串首字母和末尾字母一一进行比较，如果都相等的话那么这个字符串就是回文。

声明一个函数，参数为：要进行检测的字符串
去除字符串的空格并将其全转为小写字母
遍历字符串，将字符串的每个字符加入双端队列中。
遍历队列，队首出队和队尾出队
判断队首和队尾的字符是否相等，如果不想等则回文结果为false
如果队列的大小大于1且会问结果为true则继续比对队首元素和队尾元素

实现代码

我们捋清了回文的实现思路后，就可以将上述思路转换为代码了：

import Deque from "./lib/Deque.ts";
/**
 * 回文函数
 * @param sourceString 需要进行判断是否为回文的参数
 * @returns {boolean}
 */
const palindromeDetection = function (sourceString) {
    // 判断参数是否有效
    if(sourceString === undefined || sourceString === null || sourceString.length === 0){
        return false;
    }
    // 实例化一个双端队列
    const deque = new Deque();
    // 去除字符串的空格并将其转为小写字母
    const lowerString = sourceString.toLocaleLowerCase().split(" ").join("");
    // 回文校验结果
    let isEqual = true;
    let firstChar,lastChar;

    // 字符串入队
    for (let i = 0; i < lowerString.length; i++){
        // charAt获取指定索引处的字符
        deque.addBack(lowerString.charAt(i));
    }

    // 队列大小大于1且回文校验结果为true则继续执行校验
    while (deque.size() > 1 && isEqual){
        // 队首和队尾元素出队
        firstChar = deque.removeFront();
        lastChar = deque.removeBack();
        // 比较队尾元素和队首元素是否相等
        if(firstChar !== lastChar){
            isEqual  = false;
        }
    }

    // 返回验证结果
    return isEqual;
}

编写测试代码

上述代码实现了回文函数，接下来我们来试下上述代码是否能正常运行

const testString = "madam";
const testStr = "admin";
const results = palindromeDetection(testString);
const testStrResult = palindromeDetection(testStr);
if (results){
    console.log(`${testString}是回文`)
}else{
    console.log(`${testString}不是回文`);
}

if(testStrResult){
    console.log(`${testStr}是回文`);
}else{
    console.log(`${testStr}不是回文`);

完整代码请移步：Examples.js

执行结果如下

阅读量：2008

点赞量：0

收藏量:0