数据结构（二）队列

队列是一个先进先出的数据结构

JavaScript中没有队列，但可以用Array实现队列的所有功能

队列常用操作：push、shift、queue[0]

1. 队列定义

先进先出（排队）

队列在尾部添加新元素，并从顶部移除元素

最新添加的元素必须排在队列的末尾

用途：

食堂排队打饭

JS异步中的任务队列

计算最近请求次数

……

2. 队列具体操作

创建

1
2
3
4
5
6
7
class Queue {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};  //使用对象来存储
    }
}

方法

  • enqueue(element(s))：向队列尾部添加一个（或多个）新的项

    1
    2
    3
    4
    enqueue(element(s)) {
        this.items[this.count] = element;
        this.count++;
    }

  • dequeue()：移除队列的第一项，并返回被移除的元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    dequeue() {
        if(this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
    	delete this.items[this.lowestCount];
    	this.lowestCount++;
        return result;
    }

  • peek()：返回队列中第一个元素，也将是最先被移除的元素（不移除元素，只返回元素信息）

    1
    2
    3
    4
    5
    6
    peek() {
        if(this.isEmpty()) {
            return undefined;
        }
        return this.items[this.lowestCount];
    }

  • isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false

    1
    2
    3
    4
    isEmpty() {
        return this.count - this.lowestCount === 0;
        //return this.size() === 0;
    }

  • size()：返回队列包含的元素个数，与数组的length属性类似

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

  • clear(): 清空所有元素

    1
    2
    3
    4
    5
    clear() {
        this.items = {};
        this.count = 0;
        this.lowestCount = 0;
    }

  • toString()：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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;
    }

    由于Queue 类中的第一个索引值不一定为0，所以从索引值为lowestCount 的位置开始迭代队列

3.queue类使用

同stack

4. 双端队列定义

先进先出 + 后进先出

前后都能进行添加和移除元素的特殊队列

应用：

撤销操作

5. 双端队列的具体操作

创建

1
2
3
4
5
6
7
class Deque {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
}

方法

和queue相同的： isEmpty、clear、size、toString

和queue不同的：

  • addFront(element)：在前端添加新的元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    addFront(element) {
        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.lowestCount = 0;
            this.items[0] = element;
        }
    }

  • addBack(element)：在后端添加新的元素（和enqueue()相同）

    1
    2
    3
    4
    addBack(element) {
        this.items[this.count] = element;
        this.count++;
    }

  • removeFront()：从前端移除第一个元素（和dequeue 方法相同）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    removeFront() {
        if(this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
    	delete this.items[this.lowestCount];
    	this.lowestCount++;
        return result;
    }

  • removeBack()：从后端移除第一个元素（和Stack 类中的pop 相同）

    1
    2
    3
    removeBack() {
    	return this.items.pop();
    }

  • peekFront()：返回前端的第一个元素（和peek方法相同）

    1
    2
    3
    peekFront() {
    	return this.items[this.items.length - 1];
    }

  • peekBack()：返回后端的第一个元素（和Stack 类中的peek方法相同）

    1
    2
    3
    peekBack() {
    	return this.items[this.items.length - 1];
    }

6. Deque类使用

同上

7. 解决问题

循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function hotPotato(elementsList, num) {
	const queue = new Queue();
	const elimitatedList = [];
	for (let i = 0; i < elementsList.length; i++) {
		queue.enqueue(elementsList[i]);
	}
	while (queue.size() > 1) {
		for (let i = 0; i < num; i++) {
			queue.enqueue(queue.dequeue());
		}
		elimitatedList.push(queue.dequeue());
	}
	return {
		eliminated: elimitatedList,
		winner: queue.dequeue()
	};
}

const names = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'];
const result = hotPotato(names, 10);
result.eliminated.forEach(name => {
	console.log(`${name}在击鼓传花游戏中被淘汰。`);
});
console.log(`胜利者： ${result.winner}`);

回文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function palindromeChecker(aString) {
    if (
        aString === undefined || 
        aString === null ||
        (aString !== null && aString.length === 0)
    ) {
        return false;
    }
    const deque = new Deque();
    const lowerString = aString.toLocaleLowerCase();  //转换成小写
    let isEqual = true;
    let firstChar, lastChar;
    for (let i = 0; i < lowerString.length; i++) {
        deque.addBack(lowerString.charAt(i)); //在后端添加新的元素
    }
    while (deque.size() > 1 && isEqual) {
        firstChar = deque.removeFront(); //从前端移除第一个元素
        lastChar = deque.removeBack(); //从后端移除第一个元素
        if (firstChar !== lastChar) {
            isEqual = false;
        }
    }
    return isEqual;
}

一道LeetCode题

LeetCode933

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var RecentCounter = function() {
    this.q = [];
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
   this.q.push(t);
   while(this.q[0] < t - 3000){
       this.q.shift(); // 超出这个范围的就删除
   } 
   return this.q.length;
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */