6.1 栈
6.1.1用两个栈实现一个队列
题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：
思路： 两个栈一个栈做队头（出元素），另一个栈做队尾（入元素）
- 每次push只需要push到尾栈
- pop时如果头栈为空则将尾栈全部“倒入”头栈，如果头栈不为空取出栈顶元素返回，否则返回失败（此时队列为空）。
示例代码：
type MyQueue struct {
stack_head []int
stack_tail []int
}
/** Initialize your data structure here. */
func Constructor() MyQueue {
return MyQueue{
stack_head: make([]int, 0),
stack_tail: make([]int, 0),
}
}
/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
this.stack_tail = append(this.stack_tail, x)
}
func(this *MyQueue) tail2head() {
for i := len(this.stack_tail) - 1; i >= 0; i-- {
this.stack_head = append(this.stack_head, this.stack_tail[i])
this.stack_tail = this.stack_tail[:len(this.stack_tail) - 1]
}
}
/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
if len(this.stack_head) == 0 {
this.tail2head()
}
if len(this.stack_head) > 0 {
r := this.stack_head[len(this.stack_head) - 1]
this.stack_head = this.stack_head[:len(this.stack_head) - 1]
return r
}
return -1
}
/** Get the front element. */
func (this *MyQueue) Peek() int {
if len(this.stack_head) == 0 {
this.tail2head()
}
if len(this.stack_head) > 0 {
return this.stack_head[len(this.stack_head) - 1]
}
return -1
}
/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
return len(this.stack_head) == 0 && len(this.stack_tail) == 0
}
6.1.2 逆波兰表达式求值
问题描述：根据 逆波兰表示法，求表达式的值。
有效的运算符包括+,-,*,/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
思路：借助一个栈，如果是数值就入栈，如果是运算符就从栈顶取出两个元素计算，然后将结果入栈，最后栈中只剩一个元素就是结果。
示例代码：
func operate(x, y int, op string) int {
switch op {
case "+": return x + y
case "-": return x - y
case "*": return x * y
case "/": return x / y
default:
return 0
}
}
func evalRPN(tokens []string) int {
stack := []int{}
for i := 0; i < len(tokens); i++ {
switch tokens[i] {
case "+", "-", "*", "/":
cur := operate(stack[len(stack) - 2], stack[len(stack) - 1], tokens[i])
stack = stack[:len(stack) - 1]
stack[len(stack) - 1] = cur
default:
num, _ := strconv.Atoi(tokens[i])
stack = append(stack, num)
}
}
return stack[0]
}
6.1.3 中缀表达式生成逆波兰表达式
- 借助一个符号栈和结果队列，具体过程见代码注释
示例代码：
func is_operation(b byte) bool {
return b == '+' || b == '-' || b == '*' || b == '/'
}
func compare_priority(a, b byte) int {
if (a == '+' || a == '-') && (b == '*' || b == '/') {
return -1
} else if (b == '+' || b == '-') && (a == '*' || a == '/') {
return 1
} else {
return 0
}
}
func toRPN(s string) []string {
// 运算符栈
ops_stack := []byte{}
// 结果队列
res_queue := []string{}
n := len(s)
for i := 0; i < n; i++ {
if s[i] == '(' {
// 遇到左括号直接入栈
ops_stack = append(ops_stack, s[i])
} else if s[i] == ')' {
// 遇到右括号，则将栈中的运算符依次弹出加入到结果队列，直到碰到左括号，然后将这对括号丢弃
for ops_stack[len(ops_stack) - 1] != '(' {
res_queue = append(res_queue, string(ops_stack[len(ops_stack) - 1]))
ops_stack = ops_stack[:len(ops_stack) - 1]
}
ops_stack = ops_stack[:len(ops_stack) - 1]
} else if is_operation(s[i]) {
// 遇到运算符，当前运算符的优先级小于等于栈顶运算符的优先级，则依次将栈顶弹出加入到结果队列
for len(ops_stack) > 0 && is_operation(ops_stack[len(ops_stack) - 1]) &&
compare_priority(s[i], ops_stack[len(ops_stack) - 1]) <= 0 {
res_queue = append(res_queue, string(ops_stack[len(ops_stack) - 1]))
ops_stack = ops_stack[:len(ops_stack) - 1]
}
ops_stack = append(ops_stack, s[i])
} else if s[i] == ' ' {
// 跳过空字符
continue
} else {
// 遇到数字加入到结果队列
num := 0
for ; i < n && s[i] >= '0' && s[i] <= '9'; i++ {
num = num * 10 + int(s[i] - '0')
}
i--
res_queue = append(res_queue, strconv.Itoa(num))
}
}
// 运算符栈中剩余的元素弹出添加到结果队列
for len(ops_stack) > 0 {
res_queue = append(res_queue, string(ops_stack[len(ops_stack) - 1]))
ops_stack = ops_stack[:len(ops_stack) - 1]
}
return res_queue
}
6.2 堆
定义：最大堆的堆顶为最大元素，最小堆同理
6.2.1 Golang实现堆类型
因为go本身没有实现堆类型，只提供了接口，使用时必须实现堆接口才能使用对应的堆方法，所以自己用golang的container/heap接口实现一个通用的堆类型，创建堆需要一个比较函数作为参数
实现代码：
// 比较函数类型
type Comparator func(a, b interface{}) bool
// 堆元素类型
type Elements struct {
es []interface{}
cmp Comparator
}
// 堆类型
type Heap struct {
elements *Elements
}
// 创建堆
func NewHeap(cmp Comparator) *Heap {
return &Heap{
elements: &Elements{
es: make([]interface{}, 0),
cmp: cmp,
},
}
}
// 堆元素实现了container/heap接口
func (e Elements) Len() int { return len(e.es) }
func (e Elements) Less(i, j int) bool { return e.cmp(e.es[i], e.es[j]) }
func (e Elements) Swap(i, j int) { e.es[i], e.es[j] = e.es[j], e.es[i] }
func (e *Elements) Push(item interface{}) { e.es = append(e.es, item) }
func (e *Elements) Pop() interface{} {
length := len(e.es)
if length == 0 {
return nil
}
top := e.es[length - 1]
e.es = e.es[:length - 1]
return top
}
// 入堆
func (h *Heap) Push(i interface{}) {
heap.Push(h.elements, i)
}
// 堆顶元素出堆
func (h *Heap) Pop() interface{} {
return heap.Pop(h.elements)
}
// 查看堆顶元素
func (h Heap) Top() interface{} {
if len(h.elements.es) == 0 {
return nil
}
return h.elements.es[0]
}
// 获取堆大小
func (h Heap) Len() int {
return h.elements.Len()
}
func CompareInt(a, b interface{}) bool {
if a.(int) > b.(int) {
return true
}
return false
}
6.2.2 数组中的第K个最大元素
问题描述：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
思路：使用最小堆，首先将前k个元素加入堆作为目前的最大的k个元素，然后遍历剩下的n-k个元素，如果堆顶元素比当前元素小，取出堆顶，将当前元素加入堆。最后堆顶的元素即为第k大的元素。
时间复杂度：O(n*log(n))
空间复杂度：O(k)
示例代码：
func findKthLargest(nums []int, k int) int {
heap1:= NewHeap(CompareInt)
// 前k个元素建立大小为k的小顶堆
for i := 0; i < k; i++ {
heap1.Push(nums[i])
}
// 遍历剩余的元素更新堆
for i := k; i < len(nums); i++ {
top := heap1.Top().(int)
if top > nums[i] {
heap1.Pop()
heap1.Push(nums[i])
}
}
return heap1.Top().(int)
}
