6.1 棧
6.1.1用兩個棧實現(xiàn)一個隊列
題目描述：請你僅使用兩個棧實現(xiàn)先入先出隊列。隊列應(yīng)當(dāng)支持一般隊列的支持的所有操作（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 逆波蘭表達(dá)式求值
問題描述：根據(jù) 逆波蘭表示法，求表達(dá)式的值。
有效的運算符包括+,-,*,/。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達(dá)式。
輸入: ["2", "1", "+", "3", "*"]
輸出: 9
解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：((2 + 1) * 3) = 9
思路：借助一個棧，如果是數(shù)值就入棧，如果是運算符就從棧頂取出兩個元素計算，然后將結(jié)果入棧，最后棧中只剩一個元素就是結(jié)果。
示例代碼：
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 中綴表達(dá)式生成逆波蘭表達(dá)式
- 借助一個符號棧和結(jié)果隊列，具體過程見代碼注釋
示例代碼：
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{}
// 結(jié)果隊列
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] == ')' {
// 遇到右括號，則將棧中的運算符依次彈出加入到結(jié)果隊列，直到碰到左括號，然后將這對括號丟棄
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]) {
// 遇到運算符，當(dāng)前運算符的優(yōu)先級小于等于棧頂運算符的優(yōu)先級，則依次將棧頂彈出加入到結(jié)果隊列
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 {
// 遇到數(shù)字加入到結(jié)果隊列
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))
}
}
// 運算符棧中剩余的元素彈出添加到結(jié)果隊列
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實現(xiàn)堆類型
因為go本身沒有實現(xiàn)堆類型，只提供了接口，使用時必須實現(xiàn)堆接口才能使用對應(yīng)的堆方法，所以自己用golang的container/heap接口實現(xiàn)一個通用的堆類型，創(chuàng)建堆需要一個比較函數(shù)作為參數(shù)
實現(xiàn)代碼：
// 比較函數(shù)類型
type Comparator func(a, b interface{}) bool
// 堆元素類型
type Elements struct {
es []interface{}
cmp Comparator
}
// 堆類型
type Heap struct {
elements *Elements
}
// 創(chuàng)建堆
func NewHeap(cmp Comparator) *Heap {
return &Heap{
elements: &Elements{
es: make([]interface{}, 0),
cmp: cmp,
},
}
}
// 堆元素實現(xiàn)了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 數(shù)組中的第K個最大元素
問題描述：在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
思路：使用最小堆，首先將前k個元素加入堆作為目前的最大的k個元素，然后遍歷剩下的n-k個元素，如果堆頂元素比當(dāng)前元素小，取出堆頂，將當(dāng)前元素加入堆。最后堆頂?shù)脑丶礊榈趉大的元素。
時間復(fù)雜度：O(n*log(n))
空間復(fù)雜度：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)
}
