-
栈结构:后进者先出,先进者后出
-
栈是一种“操作受限”的线性表
-
当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,这时我们就应该首选“栈”这种数据结构
栈的实现
- 使用数组实现:顺序栈
class ArrayStack:
"""使用数组实现一个顺序栈"""
def __init__(self):
'''
初始化顺序栈
参数:
无
返回值:
无
'''
self.items = []
def push(self, item):
'''
入栈操作
参数:
item (任意类型): 待入栈的值
返回值:
无
'''
self.items.append(item)
def pop(self):
'''
出栈操作
参数:
无
返回值:
待出栈的值
'''
if not self.is_empty():
return self.items.pop()
def is_empty(self):
'''
检查栈是否为空
参数:
无
返回值:
bool: 如果栈为空则返回True,否则返回False
'''
return len(self.items) == 0
- 使用链表实现:链式栈
class Node:
'''维护链表节点'''
def __init__(self, value):
'''
初始化链表节点
参数:
value (任意类型): 节点的值
返回值:
无
'''
# 节点的值
self.value = value
# 指向下一个节点的指针
self.next = None
class Stack:
'''进行出栈或入栈操作'''
def __init__(self):
'''
初始化栈
参数:
无
返回值:
无
'''
# 栈顶节点
self.top = None
def push(self, value):
'''
入栈操作
参数:
value (任意类型): 要入栈的值
返回值:
无
'''
if self.top is None:
self.top = Node(value)
else:
# 创建新节点
new_node = Node(value)
# 将新节点指向当前的栈顶节点
new_node.next = self.top
# 更新栈顶节点为新节点
self.top = new_node
def pop(self):
'''
出栈操作
参数:
无
返回值:
出栈的节点的值
'''
if self.top is None:
return None
else:
# 弹出栈顶节点
popped_node = self.top
# 更新栈顶节点为下一个节点
self.top = self.top.next
# 将弹出的节点从链表中断开
popped_node.next = None
# 返回弹出节点的值
return popped_node.value
栈的应用
函数调用栈
操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧1入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。
def main():
'''
主函数,用于执行程序的主要逻辑
参数:
无
返回值:
int: 表示程序执行结果的返回值
'''
a = 1
ret = 0
res = 0
# 调用add函数,将返回值赋给ret变量
ret = add(3, 5)
# 计算a和ret的和,将结果赋给res变量
res = a + ret
# 打印res的值
print(res)
return 0
def add(x, y):
'''
将两个数字相加
参数:
x (int): 第一个数字
y (int): 第二个数字
返回值:
int: 两个数字的和
'''
sum = 0
# 计算x和y的和,将结果赋给sum变量
sum = x + y
return sum
if __name__ == '__main__':
# 调用main函数
main()
能否使用其他数据结构实现函数调用功能?
- 虽然其他数据结构也可以用来保存临时变量,但是它们的实现可能不如栈那么高效。
- 例如,使用链表来保存上下文信息,需要在插入和删除元素时遍历链表,时间复杂度为O(n),而使用栈的时间复杂度为O(1)。因此,栈是最常用的函数调用栈的实现方式。
表达式求值
编译器通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符的栈。
- 我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;
- 当遇到运算符,就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;
- 如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。
检查括号是否匹配
假设表达式中只包含三种括号:
-
圆括号 ()
-
方括号[]
-
花括号{}
它们可以任意嵌套。比如,{[] ()[{}]}
或[{()}([])]
等都为合法格式,而{[}()]
或[({)]
为不合法的格式。
那么如何检查括号是否合法?
-
我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。
-
当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如
(
跟)
匹配,[
跟]
匹配,{
跟}
匹配,则继续扫描剩下的字符串。如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。 -
当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式。
实现浏览器的前进和后退功能
- 使用两个栈,X 和 Y。
- 我们把首次浏览的页面依次压入栈 X,当点击后退按钮时,再依次从栈 X 中出栈,并将出栈的数据依次放入栈 Y。当我们点击前进按钮时,我们依次从栈 Y 中取出数据,放入栈 X 中。
- 当栈 X 中没有数据时,那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据,那就说明没有页面可以点击前进按钮浏览了。
JVM中的堆栈和栈的区别是什么?
JVM 中的“栈”和数据结构中的“栈”是类似的,都是一种后进先出(LIFO)的数据结构。但是它们的实现和使用方式是不同的。
在JVM中,每个线程都有一个私有的栈,用于存储方法调用时的局部变量和操作数栈。当一个方法被调用时,会在栈上创建一个新的栈帧,用于存储该方法的局部变量和操作数栈等信息。当方法返回时,该方法对应的栈帧就会被销毁。因此,JVM中的“栈”主要用于方法调用和返回,以及存储线程私有的数据。
在计算机科学中,栈通常指的是一种数据结构,它是一种后进先出(LIFO)的数据结构,只能在栈顶进行插入和删除操作。栈通常用于函数调用时保存临时变量和返回地址,以及递归等算法实现中。
Leetcode:栈习题
题目:文章来源:https://www.toymoban.com/news/detail-479976.html
- 20
- 155
- 232
- 844
- 224
- 682
- 496
-
每当一个函数被调用时,都会创建一个新的栈帧(Stack Frame),用于保存该函数的局部变量、参数、返回地址等信息 ↩︎文章来源地址https://www.toymoban.com/news/detail-479976.html
到了这里,关于数据结构与算法之美 | 栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!