# 栈

# 基本结构

# 1. 基于数组实现栈

https://github.com/Twelveeee/AlgorithmCamp2023/tree/main/04_stack

	type StackV1 struct {
	data []interface{}
	}

	func (s *StackV1) Push(v interface{}) {
	s.data = append(s.data, v)
	}

	func (s *StackV1) Pop() (out interface{}) {
	if s.Empty() {
	panic("stock empty")
	}
	out = s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return out
	}

	func (s *StackV1) Peek() (out interface{}) {
	return s.data[len(s.data)-1]
	}

	func (s *StackV1) Empty() bool {
	return len(s.data) == 0
	}

# 2. 基于链表实现栈

	type StackV2 struct {
	top *Node
	}

	type Node struct {
	Pre *Node
	Val interface{}
	}

	func (s *StackV2) Push(v interface{}) {
	s.top = &Node{s.top, v}
	}

	func (s *StackV2) Pop() (out interface{}) {
	if s.Empty() {
	panic("stock empty")
	}
	outNode := s.top
	s.top = outNode.Pre

	return outNode.Val
	}

	func (s *StackV2) Peek() (out interface{}) {
	return s.top.Val
	}

	func (s *StackV2) Empty() bool {
	return s.top == nil
	}

# 3. 内部包实现栈

	import "container/heap"

	// 基于内部包实现栈
	type StackV3 []int

	func InitStackV3() *StackV3 {
	s := new(StackV3)
	heap.Init(s)
	return s
	}

	func (h *StackV3) Len() int {
	return len(*h)
	}

	func (h *StackV3) Less(i, j int) bool {
	return (h)[i] < (h)[j]
	}
	func (h *StackV3) Swap(i, j int) {
	(h)[i], (h)[j] = (h)[j], (h)[i]
	}
	func (h *StackV3) Push(x interface{}) {
	h = append(h, x.(int))
	}

	func (h *StackV3) Pop() interface{} {
	v := (*h)[h.Len()-1]
	h = (h)[:h.Len()-1]
	return v
	}

# 算法题

# 1. 括号匹配问题

https://leetcode.cn/problems/valid-parentheses/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/04_stack/level_2/topic_1.go

给定一个只包括 '(' ， ')' ， '{' ， '}' ， '[' ， ']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

	func isValid(s string) bool {
	if len(s)%2 != 0 {
	return false
	}

	pairs := map[byte]byte{
	')': '(',
	']': '[',
	'}': '{',
	}

	stack := make([]byte, 0, 1000)

	for _, v := range []byte(s) {
	if pairs[v] > 0 {
	if len(stack) <= 0 \|\| stack[len(stack)-1] != pairs[v] {
	return false
	}
	stack = stack[:len(stack)-1]
	} else {
	stack = append(stack, v)
	}

	}

	return len(stack) == 0
	}

# 2. 最小栈

https://leetcode.cn/problems/min-stack/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/04_stack/level_2/topic_2.go

设计一个支持 push ， pop ， top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素 val 推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

	type MinStack struct {
	data []int
	minData []int
	}

	func Constructor() MinStack {
	return MinStack{[]int{}, []int{math.MaxInt64}}
	}

	func (s *MinStack) Push(val int) {
	s.data = append(s.data, val)
	if val < s.minData[len(s.minData)-1] {
	s.minData = append(s.minData, val)
	} else {
	s.minData = append(s.minData, s.minData[len(s.minData)-1])
	}
	}

	func (s *MinStack) Pop() {
	s.data = s.data[:len(s.data)-1]
	s.minData = s.minData[:len(s.minData)-1]
	}

	func (s *MinStack) Top() int {
	return s.data[len(s.data)-1]
	}

	func (s *MinStack) GetMin() int {
	return s.minData[len(s.minData)-1]
	}

	/**
	* Your MinStack object will be instantiated and called as such:
	* obj := Constructor();
	* obj.Push(val);
	* obj.Pop();
	* param_3 := obj.Top();
	* param_4 := obj.GetMin();
	*/

# 3. 计算器问题

https://leetcode.cn/problems/basic-calculator-ii/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/04_stack/level_3/topic_1.go

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
** 注意：** 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

	func calculate(s string) int {
	stack := make([]int, 0, 1023)

	preNum, ans := 0, 0
	preSign := '+'
	for i, ch := range s {
	isDigit := ch >= '0' && ch <= '9'

	if isDigit {
	preNum = preNum*10 + int(ch-'0')
	}

	if (!isDigit && ch != ' ') \|\| i == len(s)-1 {
	switch preSign {
	case '+':
	stack = append(stack, preNum)
	case '-':
	stack = append(stack, -preNum)
	case '*':
	stack[len(stack)-1] *= preNum
	case '/':
	stack[len(stack)-1] /= preNum
	}

	preSign = ch
	preNum = 0
	}
	}

	for _, v := range stack {
	ans += v
	}
	return ans
	}

# 4. 逆波兰表达式

https://leetcode.cn/problems/evaluate-reverse-polish-notation/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/04_stack/level_3/topic_2.go

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 '+' 、 '-' 、 '*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

	func evalRPN(tokens []string) int {
	stack := make([]int, 0)
	for _, v := range tokens {
	val, err := strconv.Atoi(v)
	if err == nil {
	// 数字
	stack = append(stack, val)
	} else {
	// 操作
	num2, num1 := stack[len(stack)-1], stack[len(stack)-2]
	stack = stack[:len(stack)-2]
	switch v {
	case "+":
	stack = append(stack, num1+num2)
	case "-":
	stack = append(stack, num1-num2)
	case "*":
	stack = append(stack, num1*num2)
	case "/":
	stack = append(stack, num1/num2)
	}
	}
	}
	return stack[0]
	}

数据结构算法

# 栈