目的：ES6标准下的JS数据结构的一些实现代码。（作为记录和启发）
内容：队列和双端队列。（未完成，待继续）
所有源码在我的Github上（如果觉得不错记得给星鼓励我哦）：ES6的JavaScript数据结构实现之队列
一、基础数据结构
1、队列（FIFO）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| 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;
}
size() {
return this.count - this.lowestCount;
}
clear(){
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
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;
}
}
const queue = new Queue();
console.log(queue.isEmpty());
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
console.log(queue);
console.log(queue.size());
console.log(queue.toString());
queue.dequeue();
console.log(queue);
console.log(queue.peek());
queue.clear();
console.log(queue);
Queue
|
2、双端队列（相当于是队列和栈的结合）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
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.items[0] = element;
}
}
addBack(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;
}
}
const deque = new Deque();
console.log(deque.isEmpty());
deque.addBack('a');
deque.addBack('b');
console.log(deque);
console.log(deque.toString());
deque.addBack('c');
deque.removeFront();
console.log(deque);
deque.removeBack();
console.log(deque);
deque.addFront('d');
console.log(deque);
Deque
|
二、简单应用：击鼓传花，回文检测器。
1、击鼓传花游戏（hot potato），即实现循环队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
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.items[0] = element;
}
}
addBack(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;
}
}
const deque = new Deque();
console.log(deque.isEmpty());
deque.addBack('a');
deque.addBack('b');
console.log(deque);
console.log(deque.toString());
deque.addBack('c');
deque.removeFront();
console.log(deque);
deque.removeBack();
console.log(deque);
deque.addFront('d');
console.log(deque);
Deque
|
2、回文检查器，用双端队列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| 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 firstChar;
let lastChar;
for (let i = 0; i <lowerString.length; i++){
deque.addBack(lowerString.charAt(i));
}
while (deque.size() > 1){
firstChar = deque.removeFront();
lastChar = deque.removeBack();
if (firstChar !== lastChar) {
return false;
}
}
return true;
}
console.log(palindromeChecker(''))
console.log(palindromeChecker('a'))
console.log(palindromeChecker(' a'))
console.log(palindromeChecker('aba'))
console.log(palindromeChecker('12a21'))
palindromeChecker
|
