# 【数据结构基础】队列简介（使用ES6）

• 什么是队列
• 如何用代码实现队列
• 什么是双端队列
• 如何用代码实现双端队列
• 实际应用举例

## 如何用代码实现队列

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

• enqueue(element)：此方法用于在队尾添加元素。
• dequeue(): 此方法用于删除队列的队头元素。
• peek():此方法用于队列的队头元素。
• isEmpty(): 此方法用于判断队列是否为空，是的话返回True,否的话返回False。
• size(): 此方法返回队列的大小，类似数组length属性。
• clear():清空队列所有元素。
• toString()：打印队列中的元素。

### enqueue(element)

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

### dequeue()

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

### peek()

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

### size()与isEmpty()

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

isEmpty()的实现方式更为简单了，只需要判断size()是否返回为0即可，实现代码如下：

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

### clear()

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

### toString()

```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类

```export default class Queue {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}

enqueue(element) {
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;
}
}```

### 如何使用Queue类

```const queue = new Queue();
console.log(queue.isEmpty()); // outputs true
queue.enqueue('John');
queue.enqueue('Jack');
console.log(queue.toString()); // John,Jack
queue.enqueue('Camila');
console.log(queue.toString()); // John,Jack,Camila
console.log(queue.size()); // outputs 3
console.log(queue.isEmpty()); // outputs false
queue.dequeue(); // remove John
queue.dequeue(); // remove Jack
console.log(queue.toString()); // Camila```

## 双端队列

### 如何用代码实现双端队列

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

• removeFront()：此方法用于删除双端队列的“队头”元素。
• removeBack()：此方法用于删除双端队列的“队尾”元素。
• peekFront()：此方法用于返回双端队列的“队头”元素
• peekBack()：此方法用于返回双端队列的“队尾”元素

```addFront(element) {
if (this.isEmpty()) {
} 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;
}
}```

### 最终实现的Deque类

```export default class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}

if (this.isEmpty()) {
} 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;
}
}

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

### 如何使用Deque类

```const deque = new Deque();
console.log(deque.isEmpty()); // outputs true
console.log(deque.toString()); // John,Jack
console.log(deque.toString()); // John,Jack,Camila
console.log(deque.size()); // outputs 3
console.log(deque.isEmpty()); // outputs false
deque.removeFront(); // remove John
console.log(deque.toString()); // Jack,Camila
deque.removeBack(); // Camila decides to leave
console.log(deque.toString()); // Jack
deque.addFront('John'); // John comes back for information
console.log(deque.toString()); // John,Jack”```

## 实际应用举例1：击鼓传花

```function hotFlower(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()
};
}```

• 我们声明了一个队列queue和数组elimitatedList（出局者信息）。
• 通过迭代的方式填充给定的对象elementsList并赋值给queue。
• 然后在给定的变量num之下，不断的删除队列的头元素，并插入到队尾，相当保持队列数目不变，循环依次移动队列；（循环队列）
• 到达给定数字num,删除当前队列“队头”元素，并将队头“出局者”信息，添加至数组elimitatedList。
• 直到队列的元素为1时，函数输出elimitatedList（出局者信息）和获胜者信息winner。

```const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
const result = hotFlower(names, 7);

result.eliminated.forEach(name => {
console.log(`\${name} was eliminated from the Hot Flower game.`);
});

console.log(`The winner is: \${result.winner}`);```

```Camila was eliminated from the Hot Flower game.
Jack was eliminated from the Hot Flower game.
Carl was eliminated from the Hot Flower game.
Ingrid was eliminated from the Hot Flower game.
The winner is: John```

## 实际应用举例2：验证英语回文

```function palindromeChecker(aString) {
if (aString === undefined || aString === null ||
(aString !== null && aString.length === 0)) {
return false;
}
const deque = new Deque();
const lowerString = aString.toLocaleLowerCase().split(' ').join('');
let isEqual = true;
let firstChar, lastChar;

for (let i = 0; i < lowerString.length; i++) {
}

while (deque.size() > 1 && isEqual) {
firstChar = deque.removeFront();
lastChar = deque.removeBack();
if (firstChar !== lastChar) {
isEqual = false;
}
}

return isEqual;
}```

• 首先我们需要验证输入的字符串是否有效。
• 声明实例化一个双端队列。
• 针对输入的字符串进行转成小写、删除空格的处理。
• 然后将字符串拆成字符添加至双端队列
• 然后通过removeFront()和deque.removeBack()这两个出列方法进行比较，只要不相等就返回fasle跳出方法。
• 返回布尔变量isEqual，True为回文，fasle

```console.log('a', palindromeChecker('a'));
console.log('aa', palindromeChecker('aa'));
console.log('kayak', palindromeChecker('kayak'));
console.log('level', palindromeChecker('level'));
console.log('Was it a car or a cat I saw', palindromeChecker('Was it a car or a cat I saw'));
console.log('Step on no pets', palindromeChecker('Step on no pets'));```

## 小节

【ES6基础】let和作用域

【ES6基础】const介绍

【ES6基础】默认参数值

【ES6基础】解构赋值（destructuring assignment）

【ES6基础】箭头函数（Arrow functions）

【ES6基础】模板字符串（Template String）

【ES6基础】Set 与 WeakSet

【ES6基础】Map 与 WeakMap

【ES6基础】Symbol介绍：独一无二的值

【ES6基础】Object的新方法

【数据结构基础】栈简介（使用ES6）

121 篇文章31 人订阅

0 条评论