第五章 队列与双端队列
自我测试
本篇文章的测试用例及调试方法见前言
说明
队列是遵循先进先出(FIFO,也称为先来先服务)原则的一组有序的项.队列在尾部添加新元素,并从顶部移除元素.最新添加的元素必须排在队列的末尾.
使用
当我们在浏览器打开新标签时,就会创建一个任务队列.这是因为每个标签都是一个单线程处理所有任务,称为事件循环.浏览器要赋值多个任务,如渲染HTML,执行JavaScript代码,处理用户交互(用户输入,鼠标点击等),执行和处理异步请求.
更多事件循环
队列
简单图解
队列和栈不同,就像排队买票,先排上队的先开始买票,所以是一个先进先出(FIFO)的数据结构
一个队列的基本方法
- enqueue(element(s)) : 向队列尾部添加一个(或多个)新的项
- dequeue() :移除队列的第一项(即排在队列最前面的项)并返回被移除的元素
- peek() : 返回队列中的第一个元素---最先被添加上,也将最先被移除的元素.队列不做任何变动(不移除元素,只返回信息),该方法在其他语言中也可以叫作front
- isEmpty() : 如果队列中不包含任何元素,返回true,否则返回false
- clear() : 清除所有元素
- size() : 返回队列包含的元素个数, 与数组的length属性类似
export default class Queue<T> {
// 队列数据集
private queueList: any;
// 队列的个数
private beforeIndex: number;
// 队列当前最后一个的位置
private lastIndex: number;
constructor() {
this.queueList = {};
this.lastIndex = 1;
this.beforeIndex = 1;
}
//插入
enqueue(...items: Array<T>): void {
let newIndex = this.lastIndex;
for (let i = 0, len = items.length; i < len; i++) {
this.queueList[newIndex++] = items[i];
}
this.lastIndex = newIndex;
}
//移除
dequeue(): (T | undefined) {
if (this.isEmpty()) {
return undefined;
}
let result = this.queueList[this.beforeIndex];
delete this.queueList[this.beforeIndex];
this.beforeIndex++;
return result;
}
//队列最前一个数
peek(): (T | undefined) {
return this.queueList[this.beforeIndex];
}
//队列中是否有数据
isEmpty(): boolean {
return this.size() === 0;
}
//队列里的数据个数
size(): number {
return this.lastIndex - this.beforeIndex;
}
//清理数据
clear(): void {
this.beforeIndex = 0;
this.lastIndex = 0;
this.queueList = {};
}
}
双端队列
简单图解
双端队列与队列的不同点在于,队列是先进先出,所以是一端出口,一端进口,而双端队列,就是两边都可以进也都可以出. 这就像你和你女朋友去外面玩,看到一个烤串店排了老长的队,但是又不知道有什么好吃的,所以你女朋友叫你去后面排队(后端插入数据),她去前面看看菜品(前端插入数据),然后你女票去前面看了,发现很多好吃的,但是这个时候她不太想吃这些!所以她又退了回来(移除前端数据),然后告诉你,我们以后再来吃吧!你们就一起走了(你退出队列,尾部移除)
一个双端队列的基本方法
- addFront(element(s)) : 在双端队列前端添加新的元素
- addBack() :该方法在双端队列后端添加新的元素
- removeFront() : 该方法会从双端队列前端移除第一个元素
- removeBack() : 该方法会从双端队列后端移除第一个元素
- peekFront() : 该方法会返回双端队列前端第一个元素
- peekBack() : 该方法会返回双端队列后端第一个元素
export default class Deque<T> {
//数据源
private dequeList: any;
//起始位置
private startIndex: number;
//结束指针的后一个
private endIndex: number;
constructor() {
this.dequeList = {};
this.startIndex = 0;
this.endIndex = 0;
}
// 前面添加的时候,startIndex位置有元素
addFront(...elements: Array<T>): void {
//没有元素的情况下,我会将这个添加交给后置添加
if (this.isEmpty()) {
this.addBack(...elements);
return;
}
let index = this.startIndex;
for (let i = elements.length - 1; i >= 0; i--) {
// 因为startIndex有元素,所以先减后赋值
this.dequeList[--index] = elements[i];
}
this.startIndex = index;
}
// 后面添加的时候,endIndex位置没有元素
addBack(...elements: Array<T>): void {
let index = this.endIndex;
elements.forEach(item => {
//因为规定endIndex位置没有元素,所以先赋值再++
this.dequeList[index++] = item;
})
this.endIndex = index;
}
// 前面移除一个元素
removeFront(): (T | undefined) {
if (this.isEmpty()) {
return undefined;
}
let result = this.dequeList[this.startIndex];
delete this.dequeList[this.startIndex];
this.startIndex++;
return result;
}
//后面移除一个元素
removeBack(): (T | undefined) {
if (this.isEmpty()) {
return undefined;
}
//endIndex这个时候是没有值的
this.endIndex--;
let result = this.dequeList[this.endIndex];
delete this.dequeList[this.endIndex];
return result;
}
peekFront(): T {
return this.dequeList[this.startIndex];
}
peekBack(): T {
return this.dequeList[this.endIndex - 1];
}
isEmpty() {
return this.size() === 0;
}
size() {
return this.endIndex - this.startIndex;
}
clear() {
this.dequeList = {};
this.startIndex = 0;
this.endIndex = 0;
}
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.dequeList[this.startIndex]}`;
for (let i = this.startIndex + 1; i < this.endIndex - 1; i++) {
objString = `${objString},${this.dequeList[i]}`;
}
return objString;
}
}
书中代码
队列
export default 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;
}
}
双端队列
export default 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;
}
}
leetcode对应训练
赞 (0)