数据结构中的栈、队列和链表应该是最基础的了，还有像是图、树、二叉树、最优二叉树/解等等也很重要，前端也要会数据结构是我没想到的，总结一下用JavaScript实现数据结构中的栈、队列和链表中的双向链表。
面试的时候被问到的数据结构题，当时是脑袋有点蒙的，用纸笔不知道怎么下手，过后自己写了一下其实并不难，尤其是栈和队列，可以直接直接用原生Array的pop()、push()、shift()、unshift()方法来实现，之前做JSON数据的时候还专门记录过这几个方法，真的是猪油蒙了心居然没写出来。
栈、队列
首先是栈和队列的实现，栈的核心思想是“先进后出”，队列的核心思想是“先进先出”，上课那会老师就不停得强调他们的区别，队列就像排队，先进先出；而栈是不讲道理的，先进后出。如果你当销售，先生产的产品堆压在仓库而把最新生产的产品拿来卖，到最后你可能会被老板批成PPT。
先是栈的实现，看一下主要要实现的方法：
- pop()：栈顶元素出栈并返回
- push(el)：新元素入栈
- peek()：返回栈顶元素
- size()：返回栈的长度
- isEmpty()：返回栈是否为空
- clear()：清空栈
- print()：打印栈
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
| class Stack {
constructor(...val){
this.values = [...val]
}
pop(){
return this.values.pop()
}
push(val){
this.values.push(val)
}
peek(){
return this.values[this.values.length-1]
}
size(){
return this.values.length
}
isEmpty(){
return this.values.length == 0
}
clear(){
this.values = []
}
print(){
console.log(this.values.toString())
}
}
|
然后是队列的实现，和栈的实现非常相似：
- dequeue()：头元素出列
- enqueue(el)：新元素入列
- front()：返回队列头
- size()：返回队列的长度
- isEmpty()：返回是否为空队列
- clear()：清空队列
- print()：打印队列
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
| class Queue {
constructor(...val){
this.values = [...val]
}
dequeue(){
return this.values.shift()
}
enqueue(val){
this.values.push(val)
}
front(){
return this.values[0]
}
size(){
return this.values.length
}
isEmpty(){
return this.values.length == 0
}
clear(){
this.values = []
}
print(){
console.log(this.values.toString())
}
}
|
双向链表
相比较于栈和队列，双向链表就稍微复杂一点。双向链表是没有顺序的，但是每个结点（Node）都会有指针（Pointer）指向该结点的前结点（Previous）和后结点（Next），还有一个头指针（Head）和尾指针（Tail）分别指向链表的头结点和尾结点，如果没有则指向Null，也即是空指针（Null Pointer），理论可能说不太清楚，还是图解比较条理清晰
然后是实现，首先我们得有一个结点类Node，包含前指针、后指针和数据：
1
2
3
4
5
6
7
8
9
10
| class Node {
constructor(el) {
this.element = el
this.previous = null
this.next = null
}
toString(){
return this.element
}
}
|
然后是链表的实现：
- append(el)：添加结点元素
- insert(position, el)：指定位置插入结点元素
- getNode(position)：得到指定位置结点元素
- get(position)：得到指定位置结点数据
- indexOf(el)：返回指定结点的下标
- update(position, el)：更新指定位置的结点
- removeAt(position)：删除指定位置的结点
- isEmpty()：返回链表是否为空
- size()：返回链表的长度
- toString()：重写toString()方法（因为数据结构是自定义的Node）
- backwardString()：反序遍历输出结点数据
- forwardString()：顺序遍历输出结点数据
该有的注释都解释在代码里面了。
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
| class DoubleLinkList {
head = null
tail = null
size = 0
append(el) {
if (this.size == 0) {
this.head = this.tail = el
this.size++
return
}
el.previous = this.tail
this.tail.next = el
this.tail = el
this.size++
}
insert(position, el) {
let current = null
if(position >= this.size)
return this.append(el)
if(position <= 0){
current = this.head
current.previous = el
el.next = current
this.head = el
this.size++
return
}
current = this.getNode(position)
el.previous = current.previous
el.next = current
current.previous.next = el
current.previous = el
this.size++
}
getNode(position) {
let index = 0
let current = null
if (this.isEmpty())
return
if(position >= this.size || position < 0)
return
if((this.size / 2) > position){
current = this.head
while (index++ < position) {
current = current.next
}
} else {
current = this.tail
index = this.size - 1
while (index-- > position) {
current = current.previous
}
}
return current
}
get(position) {
let index = 0
let current = null
if (this.size == 0)
return
if(position >= this.size || position < 0)
return
if((this.size / 2) > position){
current = this.head
while (index++ < position) {
current = current.next
}
} else {
current = this.tail
index = this.size - 1
while (index-- > position) {
current = current.previous
}
}
return current.element
}
indexOf(el) {
let current = this.head
let index = 0
while(current){
if(el.element == current.element)
return index
current = current.next
index++
}
return -1
}
update(position, el) {
if(position >= this.size || position < 0)
return
let current = this.getNode(position)
current.element = el.element
}
removeAt(position) {
if(position >= this.size || position < 0)
return
if(this.size == 1){
this.head = this.tail = null
this.size--
return
}
if(position == 0){
this.head = this.head.next
this.head.previous = null
this.size--
return
}
if(position == this.size - 1){
this.tail = this.tail.previous
this.tail.next = null
this.size--
return
}
let current = this.getNode(position)
current.previous.next = current.next
current.next.previous = current.previous
this.size--
}
isEmpty() {
return this.size == 0
}
size(){
return this.size
}
toString() {
return this.forwardString()
}
forwardString() {
let result = []
let current = this.head
while(current){
result.push(current.element)
current = current.next
}
return result.join(',')
}
backwardString() {
let result = []
let current = this.tail
while(current){
result.push(current.element)
current = current.previous
}
return result.join(',')
}
}
|
本文由adiynil原创编写，转载请尽量保留版权网址，感谢您的理解与分享!
