一、栈的介绍
栈(stack)是含有一组对象的容器，支持快速后进先出（LIFO: Last In First Out）的插入和删除操作。如同存储货物或供旅客住宿的地方，可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈(Push)、出栈(Pop)的说法。
栈是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称为入栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素称作出栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素，业术语：
栈顶： 允许进行插入和进行删除操作的一段称为栈顶
栈底： 表的另一端称为栈底 （第一个元素进入的位置）
入栈： 在栈顶位置插入元素的操作叫做压栈，或入栈、进栈
出栈： 删除栈顶元素的操作叫做出栈，也叫作弹栈，或者退栈
空栈： 不含元素的空表
简单来说， 栈如同一个水桶，从桶口进，从桶口出 。在特定业务场景下，是非常合适的数据结构来支撑算法完成。
二、栈算法示例 - “接雨水”实例
2.1 原始需求
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例:
输入： height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出： 6
解释： 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
2.2 需求分析
- 这个题目就是对栈量身定做的，只有“水桶”样子的形状才能装上雨水
针对这种场景，则计算“水桶”中装的单位余量即可。
- 单边一直上升、或者一直下降、或者是平的都无法装下雨水
针对这种情况，无法装雨水直接忽略即可。
- “水桶”的形状比较复杂的场景，桶口或者桶底是起伏不平的
这种情况是最为复杂的，通过栈和索引按照栈的顺序遍历柱子计算并求和。
2.3 源码(附详细注释，不单独解释逻辑)
#-*- coding:utf-8 -*-
def store_rainwater_by_stack(heights:list[int]):
heights_length = len(heights)
#形成“桶”型才能装雨水，所以至少要三个柱子；否则直接返回0
if heights_length < 3:
return 0
#定义stack用于记录装雨水柱子的索引，通过索引来计算雨水的量
index_stack = []
#定义雨水总量变量
total_rainwater = 0
#轮询柱子，用于计算雨水
for i in range(heights_length):
#如果栈为空，则没有形成“桶”，无需计算装的雨水；
#如果新的柱子大于栈顶柱子，则具备了形成了桶状的条件，立刻计算理解的雨水
#此时栈内形状是斜向下样子，直到有了高于最低柱子的情况出来，才需要计算雨水
while len(index_stack) and heights[i] >= heights[index_stack[-1]]:
#栈顶保存为高低最低的柱子作为桶底
bottom_pillar_index = index_stack.pop()
#将平齐的柱*弹子**出，留不住雨水，无需额外处理
while len(index_stack) !=0 and heights[index_stack[-1]] == heights[bottom_pillar_index]:
index_stack.pop()
#如果已到了左侧边缘，则不再具备装水的条件，立刻退出
#相当于左侧是斜向上的形状，左侧低柱*弹子**出，换上当前的高柱子
if len(index_stack) == 0:
break
#桶型凹槽计算雨水
#按照行来计算承担的雨水，所以必须算出两个柱子的间隔，掐头去尾
no_of_pillar_gap = i - index_stack[-1] - 1
#计算雨水总量,长度(no_of_pillar_gap)乘以高度(边缘低的柱子减去底部柱子)
total_rainwater = total_rainwater + \
no_of_pillar_gap * (min(heights[i], heights[index_stack[-1]]) - heights[bottom_pillar_index])
index_stack.append(i)
return total_rainwater
if __name__ == '__main__':
#实例1
#输入
heights = [0,1,0,2,1,0,1,3,2,1,2,1]
#输出：6
print(store_rainwater_by_stack(heights))
#输入：
heights = [4,2,0,3,2,5]
#输出：9
print(store_rainwater_by_stack(heights))
2.4 验证结果
PS D:\Shangouxuehui_Git\PythonAlgorithm-main> & D:/Python312/python*ex.e** d:/Shangouxuehui_Git/PythonAlgorithm-main/sgxh_stack.py
6
9
2.5 代码*载下**
https://github.com/ShanGouXueHui/PythonAlgorithm
##山狗学会 License Start##
转载请注明出处，"*今条头日**"创作者"山狗学会“ ，注明出处即授权，未注明出处罚款100万元
主页链接：山狗学会主页
##山狗学会 License End##
