数据结构学习-队列

队列是什么

队列是一种特殊的线性表, 他只允许在表的前端进行删除操作, 在表的后端进行插入操作

只有最早进入队列的元素才能最先从队列中删除, 所以队列又称为 先进先出线性表 (FIFO)

队列的实现

数组实现的队列

class arrQueue {
    private queue: unknown[] = [];

    // 从队列尾部插入元素
    enqueue(data: unknown) {
        return this.queue.push(data);
    }

    // 从队列头部删除元素
    dequeue() {
        return this.queue.shift();
    }

    // 返回队列头部元素
    front() {
        return this.queue.at(0);
    }

    isEmpty() {
        return this.queue.length === 0;
    }
    size() {
        return this.queue.length;
    }
    clear() {
        this.queue = [];
    }
    toString() {
        return this.queue.join("-");
    }
}

const queue = new arrQueue();

数组实现的队列虽然简单, 但是由于 shift 操作消耗资源大, 所以这种队列性能不高

对象实现的队列

type QueueObj = {
    [k: number]: any;
};
// 使用对象实现
class objectQueue {
    private queue: QueueObj = {};
    // 开始的下标
    private start = 0;
    // 结束的下标
    private end = 0;

    // 从队列尾部插入元素
    enqueue(data: unknown) {
        this.queue[this.end] = data;
        this.end++;
        return this.queue[this.end - 1];
    }

    // 从队列头部删除元素
    dequeue() {
        if (this.size() > 0) {
            let item = this.queue[this.start];
            delete this.queue[this.start];
            this.start++;
            return item;
        } else return undefined;
    }

    // 返回队列头部元素
    front() {
        return this.queue[this.start];
    }

    isEmpty() {
        return this.size() === 0;
    }
    size() {
        return this.end - this.start;
    }
    clear() {
        this.queue = {};
        this.start = 0;
        this.end = 0;
    }
    toString() {
        let str = "";
        for (let index = this.start; index < this.end; index++) {
            str += this.queue[index] + " ";
        }
        return str;
    }
}

双端队列

双端队列（Double-ended queue，简称 deque）是一种具有队列和栈的性质的数据结构，它允许从两端添加和删除元素。

实现:

type DoubleQueue = {
    [k: number]: any;
};
// 使用对象实现
class doubleQueue {
    private queue: DoubleQueue = {};
    // 开始的下标
    private start = 0;
    // 结束的下标
    private end = 0;

    // 从队列头部添加元素
    addFront(data: any) {
        this.start--;
        this.queue[this.start] = data;
        return this.queue[this.start];
    }
    // 从队列尾部插入元素
    addBack(data: unknown) {
        this.queue[this.end] = data;
        this.end++;
        return this.queue[this.end - 1];
    }
    // 从队列头部删除元素
    delFront() {
        if (this.size() > 0) {
            const item = this.queue[this.start];
            delete this.queue[this.start];
            this.start++;
            return item;
        } else return undefined;
    }

    // 从队列尾部删除元素
    delBack() {
        if (this.size() > 0) {
            const item = this.queue[this.end - 1];
            delete this.queue[this.end - 1];
            this.end--;
            return item;
        } else return undefined;
    }

    // 返回队列头部元素
    peekFront() {
        return this.queue[this.start];
    }
    // 返回队列尾部元素
    peekBack() {
        return this.queue[this.end - 1];
    }

    isEmpty() {
        return this.size() === 0;
    }
    size() {
        return this.end - this.start;
    }
    clear() {
        this.queue = {};
        this.start = 0;
        this.end = 0;
    }
    toString() {
        let str = "";
        for (let index = this.start; index < this.end; index++) {
            str += this.queue[index] + " ";
        }
        return str;
    }
}

队列的应用

击鼓传花游戏

// 击鼓传花游戏
function game(list: Array<string>, num: number) {
    let queue = new objectQueue();
    // 先把人员入栈
    for (let i = 0; i < list.length; i++) {
        queue.enqueue(list[i]);
    }

    // 停止条件是 队列中只有一个元素
    while (queue.size() > 1) {
        for (let i = 0; i < num; i++) {
            // 将队列头部的元素添加到队尾
            queue.enqueue(queue.dequeue());
        }
        // 循环结束队头的就是出局者
        console.log(queue.dequeue() + "淘汰了");
    }
    // 只有一个元素的话 这就是获胜者
    console.log(queue.dequeue() + "胜利");
}

game(["tim", "tom", "jack", "nana", "tina"], 7);

检查回文数 (双端队列)

// 回文数检查
function check(str: string) {
    // 全部转小写, 去掉空格
    str = str.toLocaleLowerCase().split(" ").join("");
    console.log("处理后的字符串:" + str);
    // 将字符串加入队列
    const que = new doubleQueue();
    for (let i = 0; i < str.length; i++) {
        que.addBack(str[i]);
    }
    let tag = true;
    // 取出首尾元素进行对比
    while (que.size() > 1) {
        if (que.delFront() != que.delBack()) {
            tag = false;
            break;
        }
    }
    console.log(tag);
}

check("abc dc bA");