数据结构6：栈、队列、堆

6.1 用两个栈实现一个队列

LeetCode No.232

题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（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.2 堆

定义：最大堆的堆顶为最大元素，最小堆同理

1.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个最大元素

LeetCode No.215

问题描述：在未排序的数组中找到第 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)
}

有疑问加站长微信联系（非本文作者）