y
ysj
V1
2023/03/19阅读:11主题:全栈蓝
什么是栈结构?
栈结构
栈(Stack)是一种线性数据结构,它具有后进先出(LIFO)的特点,即最后进入的元素最先出栈。栈结构常常用于函数调用、表达式求值、括号匹配等场景中。
栈的基本操作
栈的基本操作包括入栈(Push)、出栈(Pop)、查看栈顶元素(Top)和判断栈是否为空(IsEmpty)。
-
入栈:将一个元素压入栈中,使之成为新的栈顶元素。 -
出栈:将栈顶元素弹出栈外,并返回该元素。 -
查看栈顶元素:返回当前栈顶元素,但不对栈进行修改。 -
判断栈是否为空:如果栈中没有任何元素,返回 true,否则返回 false。
栈的实现方式
栈可以使用数组或链表来实现。
数组实现
使用数组实现栈时,可以使用数组的 push() 和 pop() 方法来实现入栈和出栈操作。栈顶元素即为数组的最后一个元素。
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
return this.items.pop();
}
top() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
栈的应用场景
-
函数调用:每当进入一个函数,就将该函数的返回地址(即调用该函数之后要执行的下一条指令的地址)入栈,当函数执行完毕后,再将该地址出栈,以返回到原来的调用点。 -
表达式求值:使用两个栈,一个存储操作数,一个存储操作符,按照一定的规则进行入栈和出栈操作,最终得到表达式的值。 -
括号匹配:遍历字符串中的每个字符,如果是左括号,则将其入栈,如果是右括号,则将栈顶元素出栈并判断是否与该右括号匹配。
参考资料
-
《算法(第4版)》 -
Data Structures and Algorithms - Stack
作者介绍
y
ysj
V1