Stack [栈]
# 介绍
堆栈(英语:stack)又称为栈或堆叠,是计算机科学中的一种抽象资料类型,只允许在有序的线性资料集合的一端(称为堆栈顶端,英语:top)进行加入数据(英语:push)和移除数据(英语:pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作,堆栈常用一维数组或链表来实现。常与另一种有序的线性资料集合队列相提并论。
# 操作
堆栈使用两种基本操作:推入(压栈,push)和弹出(弹栈,pop):
- 推入:将资料放入堆栈顶端,堆栈顶端移到新放入的资料。
- 弹出:将堆栈顶端资料移除,堆栈顶端移到移除后的下一笔资料。
# 特点
堆栈的基本特点:
- 先入后出,后入先出。
- 除头尾节点之外,每个元素有一个前驱,一个后继。
# 分类
- 顺序栈:采用顺序存储的栈称为顺序栈,它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶的位置。
- 共享栈:一种特殊的顺序栈,利用栈底位置相对不变的特性,可以让两个顺序栈共享一个一维数据空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。
- 链栈:采用链式存储的栈称为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点,top 指向栈顶元素,
# 实现
# JavaScript
class Stack {
/**
* Creates a stack.
* @param {array} [elements]
*/
constructor(elements) {
this._elements = Array.isArray(elements) ? elements : [];
}
/**
* Checks if the stack is empty.
* @public
* @returns {boolean}
*/
isEmpty() {
return this._elements.length === 0;
}
/**
* Returns the number of elements in the stack.
* @public
* @returns {number}
*/
size() {
return this._elements.length;
}
/**
* Returns the top element in the stack.
* @public
* @returns {object}
*/
peek() {
if (this.isEmpty()) return null;
return this._elements[this._elements.length - 1];
}
/**
* Adds an element to the top of the stack.
* @public
* @param {object} element
*/
push(element) {
this._elements.push(element);
return this;
}
/**
* Removes and returns the top element in the stack.
* @public
* @returns {object}
*/
pop() {
if (this.isEmpty()) return null;
return this._elements.pop();
}
/**
* Returns the remaining elements as an array.
* @public
* @returns {array}
*/
toArray() {
return this._elements.slice();
}
/**
* Clears all elements from the stack.
* @public
*/
clear() {
this._elements = [];
}
/**
* Creates a shallow copy from the stack.
* @public
* @return {Stack}
*/
clone() {
return new Stack(this._elements.slice());
}
/**
* Creates a stack from an existing array
* @public
* @static
* @param {array} [elements]
* @return {Stack}
*/
static fromArray(elements) {
return new Stack(elements);
}
}
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
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
或者:
/* Stack data-structure. It's work is based on the LIFO method (last-IN-first-OUT).
* It means that elements added to the stack are placed on the top and only the
* last element (from the top) can be reached. After we get access to the last
* element, he pops from the stack.
* This is a class-based implementation of a Stack. It provides functions
* 'push' - to add an element, 'pop' - to remove an element from the top.
* Also it implements 'length', 'last' and 'isEmpty' properties and
* static isStack method to check is an object the instance of Stack class.
*/
// Class declaration
class Stack {
constructor () {
this.stack = []
this.top = 0
}
// Adds a value to the end of the Stack
push (newValue) {
this.stack.push(newValue)
this.top += 1
}
// Returns and removes the last element of the Stack
pop () {
if (this.top !== 0) {
this.top -= 1
return this.stack.pop()
}
throw new Error('Stack Underflow')
}
// Returns the number of elements in the Stack
get length () {
return this.top
}
// Returns true if stack is empty, false otherwise
get isEmpty () {
return this.top === 0
}
// Returns the last element without removing it
get last () {
if (this.top !== 0) {
return this.stack[this.stack.length - 1]
}
return null
}
// Checks if an object is the instance os the Stack class
static isStack (el) {
return el instanceof 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
45
46
47
48
49
50
51
52
53
54
55
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
或者使用 ES5:
/* Stack!!
* A stack is exactly what it sounds like. An element gets added to the top of
* the stack and only the element on the top may be removed. This is an example
* of an array implementation of a Stack. So an element can only be added/removed
* from the end of the array.
*/
// Functions: push, pop, peek, view, length
// Creates a stack constructor
const Stack = (function () {
function Stack () {
// The top of the Stack
this.top = 0
// The array representation of the stack
this.stack = []
}
// Adds a value onto the end of the stack
Stack.prototype.push = function (value) {
this.stack[this.top] = value
this.top++
}
// Removes and returns the value at the end of the stack
Stack.prototype.pop = function () {
if (this.top === 0) {
return 'Stack is Empty'
}
this.top--
const result = this.stack[this.top]
this.stack = this.stack.splice(0, this.top)
return result
}
// Returns the size of the stack
Stack.prototype.size = function () {
return this.top
}
// Returns the value at the end of the stack
Stack.prototype.peek = function () {
return this.stack[this.top - 1]
}
// To see all the elements in the stack
Stack.prototype.view = function (output = value => console.log(value)) {
for (let i = 0; i < this.top; i++) {
output(this.stack[i])
}
}
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
45
46
47
48
49
50
51
52
53
54
55
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
# 扩展
使用 Stack 检查表达式中的括号是否平衡(格式正确性)。
// Javascript program for checking balanced brackets
function areBracketsBalanced(expr) {
// Using ArrayDeque is faster than using Stack class
let stack = [];
// Traversing the Expression
for(let i = 0; i < expr.length; i++) {
let x = expr[i];
if (x == '(' || x == '[' || x == '{') {
// Push the element in the stack
stack.push(x);
continue;
}
// If current character is not opening bracket, then it must be closing.
// So stack cannot be empty at this point.
if (stack.length == 0) return false;
let check;
switch (x) {
case ')':
check = stack.pop();
if (check == '{' || check == '[') return false;
break;
case '}':
check = stack.pop();
if (check == '(' || check == '[') return false;
break;
case ']':
check = stack.pop();
if (check == '(' || check == '{') return false;
break;
}
}
// Check Empty Stack
return (stack.length == 0);
}
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
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
# 参考
编辑 (opens new window)
上次更新: 2022/10/25, 20:41:26