ES6的JavaScript数据结构实现之队列

目的：ES6标准下的JS数据结构的一些实现代码。（作为记录和启发）

内容：队列和双端队列。（未完成，待继续）

所有源码在我的Github上（如果觉得不错记得给星鼓励我哦）：ES6的JavaScript数据结构实现之队列

一、基础数据结构

1、队列（FIFO）

 1 class Queue{
 2 constructor(){
 3 this.count = 0;
 4 this.lowestCount = 0;
 5 this.items ={};
 6 }
 7 
 8 
 9 enqueue(element) {
10 this.items[this.count] = element;
11 this.count++;
12 }
13 
14 dequeue() {
15 if (this.isEmpty()) {
16 return undefined;
17 }
18 const result = this.items[this.lowestCount];
19 delete this.items[this.lowestCount];
20 this.lowestCount++;
21 return result;
22 }
23 
24 peek() {
25 if (this.isEmpty()){
26 return undefined;
27 }
28 return this.items[this.lowestCount];
29 }
30 
31 isEmpty() {
32 return this.size() === 0;
33 }
34 size() {
35 return this.count - this.lowestCount;
36 }
37 clear(){
38 this.items = {};
39 this.count = 0;
40 this.lowestCount = 0;
41 }
42 toString(){
43 if (this.isEmpty()){
44 return '';
45 }
46 let objString = `${this.items[this.lowestCount]}`
47 for (let i= this.lowestCount + 1; i < this.count;i++){
48 objString = `${objString},${this.items[i]}`;
49 }
50 return objString;
51 }
52 }
53 
54 const queue = new Queue();
55 console.log(queue.isEmpty());
56 queue.enqueue('a');
57 queue.enqueue('b');
58 queue.enqueue('c');
59 console.log(queue);
60 console.log(queue.size());
61 console.log(queue.toString());
62 queue.dequeue();
63 console.log(queue);
64 console.log(queue.peek());
65 queue.clear();
66 console.log(queue);

Queue

2、双端队列（相当于是队列和栈的结合）

 1 class Deque {
 2 constructor() {
 3 this.count = 0;
 4 this.lowestCount = 0;
 5 this.items = {};
 6 }
 7 addFront(element){
 8 if (this.isEmpty()){
 9 this.addBack(element);
10 } else if (this.lowestCount > 0){
11 this.lowestCount--;
12 this.items[this.lowestCount] = element;
13 } else {
14 for (let i = this.count; i >0 ; i--){
15 this.items[i] = this.items[i-1];
16 }
17 this.count++;
18 this.items[0] = element;
19 }
20 }
21 addBack(element) {
22 this.items[this.count] = element;
23 this.count++;
24 }
25 
26 removeFront() {
27 if (this.isEmpty()) {
28 return undefined;
29 }
30 const result = this.items[this.lowestCount];
31 delete this.items[this.lowestCount];
32 this.lowestCount++;
33 return result;
34 }
35 removeBack() {
36 if (this.isEmpty()) {
37 return undefined;
38 }
39 this.count--;
40 const result = this.items[this.count];
41 delete this.items[this.count];
42 return result;
43 }
44 
45 peekFront() {
46 if (this.isEmpty()) {
47 return undefined;
48 }
49 return this.items[this.lowestCount];
50 }
51 peekBack() {
52 if (this.isEmpty()) {
53 return undefined;
54 }
55 return this.items[this.count - 1];
56 }
57 isEmpty() {
58 return this.size() === 0;
59 }
60 
61 clear() {
62 this.items = {};
63 this.count = 0;
64 this.lowestCount = 0;
65 }
66 
67 size() {
68 return this.count - this.lowestCount;
69 }
70 
71 toString() {
72 if (this.isEmpty()) {
73 return '';
74 }
75 let objString = `${this.items[this.lowestCount]}`;
76 for (let i = this.lowestCount + 1; i < this.count; i++) {
77 objString = `${objString},${this.items[i]}`;
78 }
79 return objString;
80 }
81 }
82 
83 const deque = new Deque();
84 console.log(deque.isEmpty());
85 deque.addBack('a');
86 deque.addBack('b');
87 console.log(deque);
88 console.log(deque.toString());
89 deque.addBack('c');
90 deque.removeFront();
91 console.log(deque);
92 deque.removeBack();
93 console.log(deque);
94 deque.addFront('d');
95 console.log(deque);

Deque

二、简单应用：击鼓传花，回文检测器。

1、击鼓传花游戏（hot potato），即实现循环队列

 1  
 2 function hotPotato(elementList, num){
 3 const queue = new Queue;
 4 const elimitatedList = [];
 5 for (let i = 0; i < elementList.length; i++){
 6 queue.enqueue(elementList[i]);
 7 }
 8 while (queue.size() > 1 ){
 9 for (let i = 0; i < num; i++){
10 queue.enqueue(queue.dequeue());
11 }
12 elimitatedList.push(queue.dequeue());
13 }
14 return {
15 elimitatedList: elimitatedList,
16 winner: queue.dequeue()
17 };
18 }
19 const names = ['a','b','c','d','e'];
20 const result = hotPotato(names, 7);
21 result.elimitatedList.forEach(name => {
22 console.log(`${name} lost the game.`)
23 });
24 console.log(`The winner is ${result.winner}`)
25 
26 /*
27 
28 c lost the game.
29 b lost the game.
30 e lost the game.
31 d lost the game.
32 The winner is a
33 
34 */

hotPotato

2、回文检查器，用双端队列。

 1 function palindromeChecker(aString){
 2 if (
 3 aString === undefined 
 4 || aString === null 
 5 || (aString !== null && aString.length === 0)
 6 ) {
 7 return false;
 8 }
 9 const deque = new Deque;
10 const lowerString = aString.toLocaleLowerCase().split(' ').join('');
11 let firstChar;
12 let lastChar;
13 
14 for (let i = 0; i <lowerString.length; i++){
15 deque.addBack(lowerString.charAt(i));
16 }
17 while (deque.size() > 1){
18 firstChar = deque.removeFront();
19 lastChar = deque.removeBack();
20 if (firstChar !== lastChar) {
21 return false;
22 }
23 }
24 return true;
25 }
26 console.log(palindromeChecker(''))
27 console.log(palindromeChecker('a'))
28 console.log(palindromeChecker(' a'))
29 console.log(palindromeChecker('aba'))
30 console.log(palindromeChecker('12a21'))
31 
32

palindromeChecker