【数据结构】栈、队列、链表及其区别

写这篇是因为之前在群里看到小伙伴在讨论算法相关知识,对于前端来说,这块也是很重要嘛,正好把之前没看完的那本电子书,《学习JavaScript数据结构与算法》复习下~

栈数据结构

栈是一种遵从后进先出(LIFO, Last in First out)原则的有序集合。新添加的或待删除的元素都保存在栈的同一端,称作栈顶,另一端叫作栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。


我们只是用ES6的简化语法把Stack函数转换成类。但变量items却是公共的,ES6的类是基于原型的,虽然基于原型的类比基于函数的类更节省内存,也更适合创建多个实例,却不能够声明私有属性或方法,而且,在这种情况下,我们希望Stack类的用户只能访问暴露给类的方法,否则就有可能从栈的中间移除元素(因为我们用数组来存储其值)

以下是ES6方法,创建私有属性的方式:

  • 用ES6的限定作用域Symbol实现类
1
2
3
4
5
6
7
8
let _items = Symbol();

class Stack {
constructor() {
this[_items] = [];
}
// stack方法
}

这种方法创建了一个假的私有属性,因为 Object.getOwnPropertySymbols能够取到类里面声明的所有Symbols属性

下面是一个破坏Stack类的例子:

1
2
3
4
5
6
7
8
9
let stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1);
stack.print(); // 5, 8, 1

访问stack[objectSymbols[0]]是可以得到_items的,并且_items属性是一个数组,可以进行任意的数组操作,于是还有下面的方案:

用ES6的WeakMap实现类

有一种数据类型可以确保属性是私有的,这就是WeakMap,现在只需要知道WeakMap可以存储键值对,其中键是对象,值可以是任意数据类型。

如果用WeakMap类存储items变量,Stack类就是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const items = new WeakMap();

class Stack {
constructor() {
items.set(this, [])
}
push(element) {
let s = items.get(this);
s.push(element);
}
pop() {
let s = items.get(this);
r = s.pop();
return r;
}
// ...其他方法
}

现在我们知道items在Stack类里是真正的私有属性了,但还有一件事要做。items现在仍然是在Stack类以外声明的,因此谁都可以改动它。我们要用一个闭包(外层函数)把Stack类包起来,这样就只能在这个函数里访问WeakMap:

1
2
3
4
5
6
7
8
9
10
let Stack = (function() {
const items = new WeakMap();
class Stack {
constructor() {
items.set(this, []);
}
// 其他方法
}
return Stack;
})();

完整代码示例:

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
// 声明类
class Stack {
constructor() {
this.items = [];
}
// 向栈添加元素
push(element) {
this.items.push(element);
}
// 从栈移除元素
pop() {
return this.items.pop();
}
// 查看栈顶元素
peek() {
return this.items[this.items.length - 1];
}
// 检查栈是否为空
isEmpty() {
console.log(`当前栈是否为空:${this.items.length === 0}`)
}
// 清空栈元素
clear() {
this.items = [];
}
size() {
console.log(`当前栈的元素有${this.items.length}个`)
}
// 打印栈元素
print() {
console.log(this.items.toString())
}
}
let stack = new Stack();
// console.log(stack.isEmpty())
stack.push(5)
stack.push(8)
console.log(stack.peek())
stack.push(11)
stack.size()
stack.isEmpty()
stack.pop();
stack.pop();
stack.size()

队列数据结构

队列是遵循FIFO(First In First Out,先进先出)原则的一组有序的项。
队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。

JS任务队列

当我们在浏览器中打开新标签时,就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务,它被称为事件循环。
浏览器要负责多个任务,如渲染HTML,执行JS代码,处理用户交互(输入、点击等),执行和处理异步请求。

代码示例:

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
// 创建队列
let Queue = (function() {
const items = new WeakMap();
class Queue {
constructor() {
items.set(this, []);
}

// 向队列添加元素
enqueue(elem) {
items.push(elem);
}

// 向队列移除元素
dequeue() {
return items.shift();
}

// 查看队列头元素
front() {
console.log(items[0])
return items[0];
}

// 检查队列是否为空
isEmpty() {
console.log(`是否为空:${items.length === 0}`)
return items.length === 0;
}

size() {
console.log(`队列长度为:${items.length}`);
return items.length;
}

// 打印队列元素
print() {
console.log(items.valueOf());
}
}
})();
// 使用Queue类
let queue = new Queue();
queue.isEmpty();
queue.enqueue('John');
queue.enqueue('Jack');
queue.enqueue('Camila');
queue.print();

链表

链表是种动态的数据结构,这意味着我们可以从中任意添加或移除项,它会按需进行扩充。

要存储多个元素,数组(或列表)可能是最常用的数据结构。每种语言都实现了数组,它提供了一个便利的[]语法来访问其元素。然而这种数据结构有一种缺点,其数组大小是固定的。
从数组的起点或中间插入或移除项的成本很高,因为它需要移动元素(尽管我们知道JS的Array类可以帮我们做这类事,但情况还是相同)
链表存储有序的元素集合,但不同于数组,链表的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称为指针或链接)组成。
相对于传统的数组,链表的好处在于,添加或移除元素时不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素。而想要访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需元素。

完整代码示例:

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
function LinkedList() {
let Node = function(element) {
this.element = element
this.next = null
}
let length = 0
let head = null
// 向列表尾部添加一个新的项
this.append = function(element) {
let node = new Node(element)
let current
// 列表中第一个节点
if (head === null) {
head = node
} else {
current = node
// 循环列表,直到找到最后一项
while (current.next) {
current = current.next
}
// 找到最后一项,将其next赋为node,建立连接
current.next = node
}
// 更新列表长度
length++
}
// 向列表的特定位置插入一个新的项
this.insert = function(position, element) {
// 检查越界值
if (position >= 0 && position <= length) {
let node = new Node(element)
let current = head
let previous
let index = 0
// 在第一个位置添加
if (position === 0) {
node.next = current
head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
// 更新列表长度
length++
return true
} else {
return false
}
}
// 从列表的特定位置移除一项
this.removeAt = function(position) {
// 检查越界值
if (position > -1 && position < length) {
let current = head
let previous
let index = 0
// 移除第一项
if (position === 0) {
head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
// 将previous与current的下一项连接起来;跳过current,从而移除它
previous.next = current.next
}
length--
return current.element
} else {
return null
}
}
// 从列表中移除一项
this.remove = function(element) {
let index = this.indexOf(element)
return this.removeAt(index)
}
// 返回元素在列表中的索引,若列表中没有该元素则返回-1
this.indexOf = function(element) {
let current = head
let index = -1
while (current) {
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
this.isEmpty = function() {
return length === 0
}
// 返回链表包含的元素个数,与数组的length属性类似
this.size = function() {
return length
}
this.getHead = function() {
return head
}
// 由于列表项使用了Node类,就需要重写继承自JS默认的toString方法,让其只输出元素值
this.toString = function() {
// 首先要访问列表中的所有元素,就需要有一个起点,也就是head。我们会把current变量当作索引,控制循环访问列表
// 我们还需要初始化用于拼接元素值的变量,接下来就是循环访问列表中的每个元素
// 我们要用current来检查元素是否存在,然后得到元素内容进行拼接
// 最后迭代下一个元素,最终返回列表内容的字符串
let current = head
let string = ''
while (current) {
string += current.element + (current.next ? 'n' : '')
current = current.next
}
return string
}
this.print = function() {}
}
var md1 = `
LinkedList数据结构还需要一个Node辅助类。Node类表示要加入列表的项,它包含一个element属性,即要添加到列表的值,以及一个next属性,即指向列表中下一个节点项的指针。
LinkedList类也有存储列表项的数组的length属性(是一个私有变量)
另一个重要点是,我们还需要存储第一个节点的引用。为此,可以把这个引用存储在称为head的变量中
然后就是LinkedList类的方法
`

链表优点

  1. 使用链表数据结构可以克服数组链表需要预先知道数据大小的缺点,链表数据结构可以充分内存空间,实现灵活的内存动态管理

  2. 数据的存取往往要在不同的排列顺序中转换,而链表是一种自我指示数据类型,因为它包含指向另一个相同类型的指针。链表允许插入和移除链表上任意位置上的节点,但是不允许随机存取

链表缺点

链表失去了数组随机读取的优点,同时链表由于增加了节点的指针域,空间开销比较大


先到这里,后面再补充吧~~

Author: Fridolph
Link: http://blog.fridolph.wang/2018/07/20/【数据结构】栈、队列、链表及其区别/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.