数据结构——队列、优先队列

共计 1629 个字符，预计需要花费 5 分钟才能阅读完成。

概述

队列是是一种受限的线性表，特点为 FIFO（先进先出）;

特点

• 受限之处在于它只允许在表的前端（front）进行删除操作
• 在表的后端（rear）进行插入操作

常见操作

• enqueue（element）：向队列尾部添加一个（或多个）新的项；
• dequeue（）：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素；
• front（）：返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与 Stack 类的 peek 方法非常类似）；
• isEmpty（）：如果队列中不包含任何元素，返回 true，否则返回 false；
• size（）：返回队列包含的元素个数，与数组的 length 属性类似；

代码实现

interface QueueItem {value: string | number | Function}
class Queue {public items: QueueItem[];

    constructor() {this.items = []
    }

    /**
     * 队列添加 item
     * @param StackItem
     */
    public enqueue(stackItem: StackItem): void {this.items.push(stackItem);
    }

    /**
     * 队列删除 item
     */
    public dequeue(): StackItem {return this.items.shift()
    }

    /**
     * 产看队列的起始 item
     */
    public front(): StackItem {return this.size() > 0 ? this.items[0]: undefined
    }

    /**
     * 队列是否为空
     */
    public isEmpty(): boolean {return this.items.length == 0}

    /**
     * 队列的 itemg 个数
     */
    public size(): number {return this.items.length}
}

优先队列

interface PriorityQueueItem {
    value: string | number | Function;
    priority: number;
}

class PriorityQueue {public items: PriorityQueueItem[];

    constructor() {this.items = []
    }

    /**
     * 队列添加 item
     * @param StackItem
     */
    public enqueue(priorityQueueItem: PriorityQueueItem): void {if(this.items.length == 0){this.items.push(priorityQueueItem)
        }else{
            let added = false;
            for(let index = 0; index < this.items.length; index++) {if(priorityQueueItem.priority < this.items[index].priority){this.items.splice(index, 0, priorityQueueItem);
                    added = true;
                    break;
                }
            }
            if(!added){this.items.push(priorityQueueItem);
            }
        }
    }

    /**
     * 队列删除 item
     */
    public dequeue(): PriorityQueueItem {return this.items.shift();
    }

    /**
     * 产看队列的起始 item
     */
    public front(): PriorityQueueItem {return this.size() > 0 ? this.items[0]: undefined
    }

    /**
     * 队列是否为空
     */
    public isEmpty(): boolean {return this.items.length == 0}

    /**
     * 队列的 itemg 个数
     */
    public size(): number {return this.items.length}
}