【数据结构与算法】栈(JavaScript版详解)

By 大Van家 on 2021-08-12
阅读时间 12 分钟
文章共 3.1k
阅读量

要点:栈(顺序栈、链栈)概念、栈结构的5大应用

先知:数组是一个线性结构,并且可以在数组的任意位置插入和删除元素。但是有时候,我们为了实现某些功能,必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。

一、什么是栈

1.1 栈

栈(stack)是一种运算受限线性表

1、LIFO(last in first out)表示就是后进入的元素,第一个弹出栈空间。类似于自动餐托盘,最后放上的托盘,往往先把拿出去使用。

2、其限制是仅允许在表的一端进行插入删除运算。这一端被称为栈顶,相对地,把另一端称为栈底

3、向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;

4、从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

如下图所示:
image

栈的特点:先进后出,后进先出

常见问题:数制转换 表达式求值 括号匹配的检验 八皇后问题 行编辑程序 函数调用 迷宫求解 递归调用的实现

1.2 顺序栈&链栈

线性表的特例,其具备先进后出 FILO 特性

1.2.1 顺序栈

可以使用线性表的顺序存储结构(即数组)实现栈,将之称之为 顺序栈

1.2.2 链栈

可以使用单链表结构实现栈,将之称之为 链栈

1.2.3 顺序栈&链栈的异同

同【时间复杂度】

顺序栈和链栈的时间复杂度均为 $O(1)$

异【空间性能】
a顺序栈

顺序栈需要事先确定一个固定的长度(数组长度)

可能存在内存空间浪费问题,但它的优势存取时定位很方便

b链栈

要求每个元素都要配套一个指向下个结点的指针域

增大了内存开销,但好处是栈的长度无限

因此,如果栈的使用过程中元素变化不可预料,有时很小,有时很大,那么最好使用链栈;

反之,如果它的变化在可控范围内,则建议使用顺序栈

1.3 栈的内部实现原理

栈的内部实现原理其实就是数组或链表的操作

而之所以引入 这个概念,是为了将程序设计问题模型化

用高层的模块指导特定行为(栈的先进后出特性),划分了不同关注层次,使得思考范围缩小

更加聚焦于我们致力解决的问题核心,简化了程序设计的问题

二、程序中的栈结构

函数调用栈:A(B(C(D()))):
即 A 函数中调用 B,B 调用 C,C 调用 D;在 A 执行的过程中会将 A 压入栈,随后 B 执行时 B 也被压入栈,函数 C 和 D 执行时也会被压入栈。所以当前栈的顺序为:A->B->C->D(栈顶);函数 D 执行完之后,会弹出栈被释放,弹出栈的顺序为 D->C->B->A;

递归
为什么没有停止条件的递归会造成栈溢出?比如函数 A 为递归函数,不断地调用自己(因为函数还没有执行完,不会把函数弹出栈),不停地把相同的函数 A 压入栈,最后造成栈溢出(Queue Overfloat)。

浏览器中的栈

栈在很多地方都有着应用,比如大家熟悉的浏览器就有很多栈,其实浏览器的执行栈就是一个基本的栈结构,从数据结构上说,它就是一个栈。 这也就解释了,我们用递归的解法和用循环+栈的解法本质上是差不多的。

比如如下 JS 代码:

1
2
3
4
5
6
7
8
9
10
11
function bar() {
const a = 1;
const b = 2;
console.log(a, b);
}
function foo() {
const a = 1;
bar();
}

foo();

真正执行的时候,内部大概是这样的:

basic-data-structure-call-stack

栈常见的应用有进制转换,括号匹配,栈混洗,中缀表达式(用的很少),后缀表达式(逆波兰表达式)等。

合法的栈混洗操作也是一个经典的题目,这其实和合法的括号匹配表达式之间存在着一一对应的关系,也就是说 n 个元素的栈混洗有多少种,n 对括号的合法表达式就有多少种。

三、练习

题目1:

有 6 个元素 6,5,4,3,2,1 按顺序进栈,问下列哪一个不是合法的出栈顺序

A:5 4 3 6 1 2 (√)

B:4 5 3 2 1 6 (√)

C:3 4 6 5 2 1 (×)

D:2 3 4 1 5 6 (√)

题目所说的按顺序进栈指的不是一次性全部进栈,而是有进有出,进栈顺序为 6 -> 5 -> 4 -> 3 -> 2 -> 1。

解析:

A 答案:65 进栈,5 出栈,4 进栈出栈,3 进栈出栈,6 出栈,21 进栈,1 出栈,2 出栈(整体入栈顺序符合 654321)。

B 答案:654 进栈,4 出栈,5 出栈,3 进栈出栈,2 进栈出栈,1 进栈出栈,6 出栈(整体的入栈顺序符合 654321)。

C 答案:6543 进栈,3 出栈,4 出栈,之后应该 5 出栈而不是 6,所以错误。

D 答案:65432 进栈,2 出栈,3 出栈,4 出栈,1 进栈出栈,5 出栈,6 出栈。符合入栈顺序。

题目2:

1

题目3:

2

四、栈结构实现

4.1 栈常见的操作

push() 添加一个新元素到栈顶位置。

pop() 移除栈顶的元素,同时返回被移除的元素。

peek() 返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)。

isEmpty() 如果栈里没有任何元素就返回 true,否则返回 false

size() 返回栈里的元素个数。这个方法和数组的 length 属性类似。

toString() 将栈结构的内容以字符串的形式返回。

4.2 JavaScript 代码实现栈结构

顺序存储

用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
// 栈结构的封装
class Map {
constructor() {
this.items = [];
}

// push(item) 压栈操作,往栈里面添加元素
push(item) {
this.items.push(item);
}

// pop() 出栈操作,从栈中取出元素,并返回取出的那个元素
pop() {
return this.items.pop();
}

// peek() 查看栈顶元素
peek() {
return this.items[this.items.length - 1];
}

// isEmpty() 判断栈是否为空
isEmpty() {
return this.items.length === 0;
}

// size() 获取栈中元素个数
size() {
return this.items.length;
}

// toString() 返回以字符串形式的栈内元素数据
toString() {
let result = "";
for (let item of this.items) {
result += item + " ";
}
return result;
}
}

链式存储

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
function LinkedStack() {
let Node = function (ele) {
this.ele = ele;
this.next = null;
}

let length = 0,
top; //栈顶指针

//压栈操作
this.push = function (ele) {
let node = new Node(ele);
top ? node.next = top : top = node;
top = node;
length++;
return true;
}

//退栈操作
this.pop = function () {
let current = top;

if (top) {
top = current.next;
current.next = null;
length--;
return current;
} else {
return 'null stack';
}

}

this.top = function () {
return top;
}
this.size = function () {
return length;
}
//toString 从栈顶到栈底
this.toString = function () {
let string = '';
current = top;
while (current) {
string += current.ele + ' ';
current = current.next;
}
return string;
}
this.clear = function () {
top = null;
length = 0;
return true;
}
}

//使用
let myStack = new LinkedStack();
myStack.push('1')
myStack.push('2')
myStack.push('3')
myStack.push('4')
console.log(myStack.toString()) // 4 3 2 1
myStack.pop()
console.log(myStack.toString()) // 3 2 1
myStack.pop()
myStack.pop()
console.log(myStack.pop()) // Node { ele: '1', next: null }
console.log(myStack.pop()) // null stack

4.3 测试封装的栈结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// push() 测试
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.items); //--> [1, 2, 3]

// pop() 测试
console.log(stack.pop()); //--> 3

// peek() 测试
console.log(stack.peek()); //--> 2

// isEmpty() 测试
console.log(stack.isEmpty()); //--> false

// size() 测试
console.log(stack.size()); //--> 2

// toString() 测试
console.log(stack.toString()); //--> 1 2

五、栈结构的简单应用

5.1 进制转换

利用栈结构的特点封装实现十进制转换为二进制的方法。

原理:

3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function dec2bin(dec) {
// new 一个 Map,保存余数
const stack = new Map();

// 当不确定循环次数时,使用 while 循环
while (dec > 0) {
// 除二取余法
stack.push(dec % 2); // 获取余数,放入栈中
dec = Math.floor(dec / 2); // 除数除以二,向下取整
}

let binaryString = "";
// 不断地从栈中取出元素(0 或 1),并拼接到一起。
while (!stack.isEmpty()) {
binaryString += stack.pop();
}

return binaryString;
}

测试

1
2
3
// dec2bin() 测试
console.log(dec2bin(100)); //--> 1100100
console.log(dec2bin(88)); //--> 1011000

5.2 进制转换进阶

十进制转化为任何进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function baseConverter(decNum, base) {	//十进制转换为任意进制		
var base = (base >= 2 && base <= 16) ? base : 10,
remStack = new Stack(),
rem,
baseStr = '',
digits = '0123456789ABCDEF';
while(decNum) {
rem = Math.floor(decNum % base);
decNum = Math.floor(decNum / base);
remStack.push(rem); //余数放到栈中
}
while(!remStack.isEmpty()) {
baseStr += digits[remStack.pop()]; //利用pop把栈内元素逐一弹出,将余数拼接成为一个字符串
}
return baseStr;
}

5.3 用栈判断回文

回文是这样一种现象:一个单词,短语或者数字,从前往后和从后往前写都是一样的。比如单词“dad”,“racecar”就是回文;如果忽略空格和标点符号,下面这个句子也是回文,“A man, a plan, a canal: Panama”,数字1001也是回文。

使用栈可以轻松的判断一个字符是否是回文。我们将拿到的字符串的每个字符按照从左至右的顺序入栈,当所有字符都入栈之后站内就保存了一个反转后的字符串,最后的字符在栈顶,第一个在栈尾。字符串完全压入站内后,通过持续弹出栈中的每个字母就可以的大一个新的字符串,该字符串刚好与原来的字符串顺序相反。我们只要比较这两个字符串即可,如果他们相等就说明这个是一个回文。代码如下:

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
function isPalindrome(word){
var s = new Stack();
for (var i=0; i<word.length; ++i) {
s.push(word[i]);
}
var reword = "";
while(s.length()>0){
reword += s.pop();
}
if(word == reword){
return true;
}else{
return false;
}
}

var word = "hello";
if(isPalindrome(word)){
document.writeln(word + " is a palindrome.");
}else{
document.writeln(word + " is not a palindrome");
}
word = "racecar";
if(isPalindrome(word)){
document.writeln(word + " is a palindrome.");
}else{
document.writeln(word + " is not a palindrome");
}

输出结果如下:

hello is not a palindrome
racecar is a palindrome.

5.4 用栈实现递归

计算阶乘可以使用递归算法,如下:

1
2
3
4
5
6
7
8
function factorial(n) {
if (n === 0) {
return 1;
}
else {
return n * factorial(n-1);
}
}

使用栈来模拟阶乘过程,例如:首先将5到1压入栈内,然后使用给一个循环,将数字一次弹出连乘就得到正确的答案,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
function fact(n){
var s = new Stack();
while (n>1){
s.push(n--);
}
var product = 1;
while (s.length()>0){
product *= s.pop();
}
return product;
}
document.writeln(fact(5)); // 120

5.5 使用栈判断表达式中的括号是否完整

表达式中的{和},(和),[和]必须是匹配的,不然的话表达式就会出现语法错误,使用栈可以判断表达式中的括号是否左右匹配。思路是遇到左括号就入栈,遇到右括号就和当前栈顶元素匹配,如果匹配成功就将栈顶元素出栈,最后判断栈中元素个数,如果是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
function isMatch(str){
var left = "({[";
var right = ")}]";
var s = new Stack();
var i = 0;
while (str[i]){
//左符号入栈
if(left.indexOf(str[i])>-1){
s.push(str[i])
}
//遇到右括号
else if( right.indexOf(str[i])>-1 && right.indexOf( str[i] ) == left.indexOf( s.peek()) ){
s.pop();
}
i++
}

// document.writeln( s.peek() );
if(s.length() == 0){
document.writeln(str + " is match success");
}else{
document.writeln(str + " is not match");
}
}

isMatch("2.3 + {23 / 12 + (3.14159×0.24)");

Tips: Please indicate the source and original author when reprinting or quoting this article.