队列

普通队列

export namespace normalQueue {
    /**
     * @class Queue
     * @classdesc 数据结构： 队列(普通队列)
     *
     * 队列是 先进先出 的有序集合\
     * 队列在底部添加新元素，并从顶部移出元素 最新添加的元素排在队列末尾\
     * 就前端来讲，打开新标签页时，就相当于创建一个任务队列
     *
     * 普通队列实现时必须方法如下：
     *  - enqueue(element) 队尾入队
     *  - dequeue() 队首出队并返回移出元素
     *  - peek() 查看队首元素
     *  - isEmpty() 返回队列是否为空
     *  - size() 返回队列大小
     *  - clear() 清空队列
     *
     * 与 栈 类似， 队列采用 Map 存储数据
     * 用 lowestCount 指示 队首的键
     * 用 count 指示 队尾的键
     * 出队则 lowestCount ++
     * 入队则 count++
     */

    export abstract class Queue<T> {
        protected count!: number
        protected lowestCount!: number
        protected queue!: Map<number, T>

        /** 队尾入队 */
        abstract enqueue(Element: T): Map<number, T>

        /** 队首出队 */
        abstract dequeue(): T | undefined

        /** 查看队首元素 */
        abstract peek(): T | undefined

        /** 查看队列是否为空 */
        abstract isEmpty(): boolean

        /** 查看队列大小 */
        abstract size(): number

        /** 清空队列 */
        abstract clear(): boolean
    }

    export class Queue_accomplish<T> extends Queue<T> {

        constructor() {
            super()
            this.count = 0
            this.lowestCount = 0
            this.queue = new Map()
        }

        enqueue(Element: T): Map<number, T> {
            this.queue.set(this.count++, Element)
            return this.queue
        }

        dequeue(): T | undefined {
            if (this.isEmpty()) return undefined
            const result: T | undefined = this.queue.get(this.lowestCount)
            this.queue.delete(this.lowestCount)
            this.lowestCount++
            return result
        }

        peek(): T | undefined {
            if (this.isEmpty()) return undefined
            return this.queue.get(this.lowestCount)
        }

        isEmpty(): boolean {
            return this.queue.size === 0
        }

        clear(): boolean {
            this.queue.clear()
            this.count = 0
            this.lowestCount = 0
            return this.isEmpty()
        }

        size(): number {
            return this.queue.size
        }

        toString(): string {
            if (this.isEmpty()) return ''
            let objString: string = `${this.queue.get(this.lowestCount)}`
            for (let i = this.lowestCount + 1; i < this.count; i++) objString = `${objString}, ${this.queue.get(i)}`
            return objString
        }
    }
}

双端队列

export namespace dualEndQueue {
    /**
     * @class Queue
     * @classdesc 数据结构 队列(双端队列)
     *
     * 双端队列 允许同时从 队首和队尾 添加和移出元素的特殊队列
     *
     * 常见于存储一系列的可撤销操作:
     *  - 当用户操作时，该操作在双端队列 队尾入队
     *  - 当用户撤销时，该操作从双端队列 队尾出队
     *  - 当操作过多时，最先进行的操作 队首出队
     *
     * 由于双端队列同时遵守 先进先出 和 后进先出 原则
     * 可以说是 队列 和 栈 的结合
     * 必需方法如下：
     * - addBack(Element) 队尾入队
     * - removeFront() 队首出队
     * - peekFront() 查看队首元素
     * - addFront(Element) 队首入队 （ 双端队列特有 ）
     * - removeBack() 队尾出队 （ 双端队列特有 ）
     * - peekBack() 查看队尾元素 （ 双端队列特有 ）
     *
     * 与队列实现方式类似，不过在\
     * 队首入队 时 需 lowestCount--\
     * 队尾入队 时 需 count--
     */
    export abstract class Queue<T> {
        protected count!: number
        protected lowestCount!: number
        protected queue!: Map<number, T>

        /** 队尾入队 */
        abstract addBack(Element: T): Map<number, T>

        /** 队首出队 */
        abstract removeFront(): T | undefined

        /** 查看队首元素 */
        abstract peekFront(): T | undefined

        /** 队首入队 */
        abstract addFront(Element: T): Map<number, T>

        /** 队尾出队 */
        abstract removeBack(): T | undefined

        /** 查看队尾元素 */
        abstract peekBack(): T | undefined

    }

    export class DEQueue<T> extends Queue<T>{
        constructor () {
            super()
            this.count = 0
            this.lowestCount = 0
            this.queue = new Map()
        }

        addFront(Element: T): Map<number, T> {
            this.queue.set(--this.lowestCount, Element)
            return this.queue
        }

        addBack(Element: T): Map<number, T> {
            this.queue.set(this.count++, Element)
            return this.queue
        }

        removeFront(): T | undefined {
            if (this.isEmpty()) return undefined
            const result = this.queue.get(this.lowestCount)
            this.queue.delete(this.lowestCount++)
            return result
        }

        removeBack(): T | undefined {
            if (this.isEmpty()) return undefined
            const result = this.queue.get(this.count)
            this.queue.delete(this.count--)
            return result
        }

        peekFront(): T | undefined {
            if (this.isEmpty()) return undefined
            return this.queue.get(this.lowestCount)
        }

        peekBack(): T | undefined {
            if (this.isEmpty()) return undefined
            return this.queue.get(this.count - 1)
        }

        /** 查看是否为空 */
        isEmpty(): boolean {
            return this.queue.size === 0
        }

        /** 查看队列大小 */
        size(): number {
            return this.queue.size
        }

        /** 覆盖默认 toString */
        toString(): string {
            if (this.isEmpty()) return ''
            let objString = `${this.queue.get(this.lowestCount)}`
            for (let i = this.lowestCount + 1; i < this.count; i++) objString = `${objString}, ${this.queue.get(i)}`
            return objString
        }
    }
}