队列与双端队列

队列和栈非常相似，但是使用了与后进先出不同的原则。

队列的概念

队列（queue）是一种采用先进先出(FIFO)策略的抽象数据结构，它的想法来自于生活中排队的策略。顾客在付款结账的时候，按照到来的先后顺序排队结账，先来的顾客先结账，后来的顾客后结账。

创建队列

与栈类似，我们依旧需要创建一个类来表示一个队列。也需要一个数组来存储元素，也可以是对象更高效，所以队列和栈很相似，只是添加和移出元素的原则不同。

我们需要在类里面声明一下属性来帮助实现一个队列：

1. count:帮助控制队列的大小
2. lowestCount:由于要从队列前端移出元素，就需要一个变量来追踪第一个元素
3. items:使用对象作为基础数据结构存储元素，更高效

class Queue<T> {
    private count: number;
    private lowestCount: number;
    private items: any;

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

声明一些队列可用的方法

1. enqueue(element(s)):向队列尾部添加一个（或多个）新的项。
2. dequeue():移出队列的第一项（即排在队列最前面的项）并返回被移出的元素。
3. peek():返回队列中第一个元素——最先被添加，也将是最先被移出的元素。队列不做任何变动（不移出元素，只返回元素信息）。
4. isEmpty():如果队列中不包含任何元素，返回true，否则返回false。
5. size():返回队列包含的元素个数，与数组的length属性相似。

/**
 * description: Queue
 * date: 2022/4/7 21:33
 * author: xinyu
 * version: 1.0
 */
class Queue<T> {
    private count: number;
    private lowestCount: number;
    private items: any;

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

    enqueue(element: T) {
        this.items[this.count] = element;
        this.count++;
    }

    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;
    }

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

    isEmpty() {
        return this.size() === 0;
    }

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

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

    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;
    }
}

简单使用

/**
 * description: useQueue
 * date: 2022/4/7 21:53
 * author: xinyu
 * version: 1.0
 */
import Queue from "./Queue";
let queue = new Queue<string>();

console.log(queue.isEmpty()); //true

queue.enqueue("xinyu") //添加两个元素
queue.enqueue("xinyu2")

console.log(queue.toString());//xinyu,xinyu2

console.log(queue.size()); //2

console.log(queue.isEmpty()); //false

queue.dequeue() //移出第一个元素即xinyu
queue.dequeue() //移出第二个元素即xinyu2
console.log(queue.isEmpty()); //true

双端队列的概念

双端队列（deque) 是同时可以从前端和后端添加和移出元素的特殊队列。

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

由于同时遵守了先进先出和后进先出原则，所以我需要构建一个以对象来存储元素的结构，当然也可以使用数组，但是数组太过于繁琐，并不推荐。

创建队列

isEmpty，clear， size，toString等方法已经在队列中实现了，双端队列因为允许在两端添加和移出元素，还会有下面几个方法：

1. addFront:前端添加新元素
2. addBack:后端添加新元素
3. removeFront:移出前端第一个元素
4. removeBack:移出后端最后一个元素
5. peekFront:返回前端第一个元素
6. peekBack:返回后端第一个元素

class Deque<T> {
    private count: number; //帮助控制队列的大小
    private lowestCount: number; //由于要从队列前端移出元素，就需要一个变量来追踪第一个元素
    private items: any; //使用对象作为基础数据结构存储元素，更高效

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

    addFront(element: T) {
        if (this.isEmpty()) {
            this.addBack(element);
        } else if (this.lowestCount > 0) {
            this.lowestCount--;
            this.items[this.lowestCount] = element;
        } else {
            for (let i = this.count; i > 0; i--) {
                this.items[i] = this.items[i - 1];
            }
            this.count++;
            this.items[0] = element;
        }
    }

    addBack(element: T) {
        this.items[this.count] = element;
        this.count++;
    }

    removeFront() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;
    }

    removeBack() {
        if (this.isEmpty()) {
            return undefined;
        }
        this.count--;
        const result = this.items[this.count];
        delete this.items[this.count];
        return result;
    }

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

    peekBack() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.count - 1];
    }

    isEmpty() {
        return this.size() === 0;
    }

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

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

    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;
    }
}

简单使用

/**
 * description: useDeque
 * date: 2022/4/7 22:20
 * author: xinyu
 * version: 1.0
 */
import Deque from "./Deque";

let deque = new Deque<string>();

console.log(deque.isEmpty());//true

deque.addBack('xinyu');//后端添加一个元素
deque.addBack('xinyu2');//后端添加一个元素
deque.addBack('xinyu3');//后端添加一个元素

console.log(deque.toString());//xinyu,xinyu2,xinyu3

console.log(deque.size());//2

console.log(deque.isEmpty());//false

deque.removeFront(); //移出xinyu
console.log(deque.toString());//xinyu2,xinyu3

deque.addFront("xinyu");//前端添加一个元素
console.log(deque.toString()); //xinyu,xinyu2,xinyu3