栈是一种先进后出的特殊线性表结构,存储上分链式存储和顺序存储两种方式。
# 一、简介
栈是一种先进后出的特殊线性表结构,存储上分链式存储和顺序存储两种方式。
重点目标:
- 用数组实现一个顺序栈
- 用链表实现一个链式栈
- 编程模拟实现一个浏览器的前进、后退功能
# 二、手写
# 数组栈
function Stack() {
let stack = []
// 尾部添加
this.push = function(value) {
stack.push(value)
}
// 返回栈顶元素,并在进程中删除它
this.pop = function() {
return stack.pop()
}
// 返回栈顶元素,但不在堆栈中删除它
this.peek = function() {
console.log(stack[stack.length - 1])
return stack[stack.length - 1]
}
// 置空
this.clear = function() {
stack = []
}
// 获取长度
this.size = function() {
console.log(stack.length)
return stack.length
}
// 是否为空
this.isEmpty = function() {
return stack.length === 0
}
// 打印
this.print = function() {
console.log(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
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
# 链表栈
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
class LinkStack {
constructor() {
// 头部相当于尾巴
this.top = null
}
push(value) {
const node = new Node(value)
if (this.top === null) this.top = node
else {
node.next = this.top
this.top = node // 此时node就是最上面的元素了
}
}
pop() {
if (this.top === null) return -1
else {
const value = this.top.value
this.top = this.top.next
return value
}
}
clear() {
this.top = null
}
print() {
if (this.top !== null) {
let temp = this.top
while (temp !== null) {
console.log(temp.value)
temp = temp.next
}
}
}
}
exports.CreatedStack = LinkStack
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
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
# 三、思考题
# 1. 浏览器的前进、后退功能
const stack = require('./linkedStack')
class Browser {
constructor() {
this.normalStack = new stack.LinkedStack()
this.backStack = new stack.LinkedStack()
}
pushNormal(name) {
this.normalStack.push(name)
this.backStack.clear()
this.displayStack()
}
back() {
const name = this.normalStack.pop()
if (name !== -1) {
this.backStack.push(name)
this.displayStack()
}
}
front() {
const value = this.backStack.pop()
if (value !== -1) {
this.normalStack.push(value)
this.displayStack()
}
}
displayStack() {
console.log('---后退页面---')
this.backStack.display()
console.log('---浏览页面---')
this.normalStack.display()
}
}
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
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
# 2. 有效括号(#20)
给定一个只包括 '(',
')',
'{',
'}',
'[',
']'
的字符串, 判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
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
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
解法: 采用栈先进先出
var isValid = function(s) {
let len = s.length
if (len == 0) return true
if (len % 2 != 0 || [')', ']', '}'].indexOf(s[0]) != -1) {
return false
}
let map = {
"(": ")",
"[": "]",
"{": "}"
}
var leftArr = []
for (var ch of s) {
if (ch in map) leftArr.push(ch); //为左括号时,顺序保存
else { //为右括号时,与数组末位匹配
if (ch != map[leftArr.pop()]) return false;
}
}
return !leftArr.length //防止全部为左括号
};
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
56 ms 34. 5 MB
参考链接: https://www.cnblogs.com/pluslius/p/10327841.html https://github.com/wangzheng0822/algo