栈
后进者先出，先进者后出，这就是典型的“栈”结构，是一种“操作受限”的线性表，只允许在一端插入和删除数据
如何实现一个“栈”
栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。
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
| type Stack struct {
Items []string
Count int
Size int
}
func (stack *Stack) NewStack(n int) Stack {
return Stack{
Items: nil,
Count: 0,
Size: n,
}
}
func (stack *Stack) push(in string) bool {
if stack.Count == 0 {
return false
}
stack.Items[stack.Count] = in
stack.Count++
return true
}
func (stack *Stack) pop(in string) string {
if stack.Count == 0 {
return ""
}
temp := stack.Items[stack.Count-1]
stack.Count--
return temp
}
|
栈在函数调用中的应用
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
栈在表达式求值中的应用
编译器是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。