在数组中，我们可以通过索引随机访问元素，但是在某些情况下，我们可能要限制数据的访问顺序，于是有了两种限制访问顺序的数据结构：栈（后进先出）、队列（先进先出）
# 栈
# 概念
栈是一个线性结构，在计算机中是一个相当常见的数据结构。
栈的特点是只能在某一端添加或删除数据，遵循先进后出的原则。
# 实现
class Stack {
constructor() {
this.stack = [];
}
push(item) {
this.stack.push(item);
}
pop() {
this.stack.pop();
}
peek() {
return this.stack[this.getCount() - 1];
}
getCount() {
return this.stack.length;
}
isEmpty() {
return this.getCount() === 0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 应用
var isValid = function(s) {
let map = {
"(": -1,
")": 1,
"[": -2,
"]": 2,
"{": -3,
"}": 3
};
let stack = [];
for (let i = 0; i < s.length; i++) {
if (map[s[i]] < 0) {
stack.push(s[i]);
} else {
let last = stack.pop();
if (map[last] + map[s[i]] != 0) return false;
}
}
if (stack.length > 0) return false;
return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 队列
队列是一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。
# 实现
单链队列
class Queue {
constructor() {
this.queue = [];
}
enQueue(item) {
this.queue.push(item);
}
deQueue() {
return this.queue.shift();
}
getHeader() {
return this.queue[0];
}
getLength() {
return this.queue.length;
}
isEmpty() {
return this.getLength() === 0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
因为单链队列在出队操作的时候需要 O(n)的时间复杂度，所以引入了循环队列。循环队列的出队操作平均是 O(1)的时间复杂度。