栈和队列和堆

Posted on Edited on In Word count in article: 20k Reading time ≈ 19 mins.
栈，队列，堆以及golang的使用

栈 Stack

栈是一种非常基础的线性结构，一种FILO类型的数据结构，FILO 即 Fisrt In Last Out

也就是先进后出，也可以说是后进先出

栈只支持三个操作， pop, top, push。

pop取出栈中最上层元素(8)，栈的最上层元素变为早先进入的元素(9)， 出栈

top查看栈的最上层元素(8)。

push将一个新的元素(5)放在栈的最上层， 入栈

通过数组实现的叫顺序栈， 通过链表实现的叫链式栈

golang实现栈

通过golang实现简单的栈

slice实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package main

import (
	"fmt"
	"sync"
)

// Item 接口
type Item interface{}

// ItemStack 栈结构体，加锁，保证协程安全
type ItemStack struct {
	items []Item
	lock  sync.RWMutex
}

// NewStack 创建一个新栈
func NewStack() *ItemStack {
	s := &ItemStack{}
	s.items = []Item{}
	return s
}

// Pirnt 打印栈的元素
func (s *ItemStack) Print() {
	fmt.Println(s.items)
}

// Push 入栈，加锁
func (s *ItemStack) Push(t Item) {
	s.lock.Lock()
	defer s.lock.Unlock()
	s.items = append(s.items, t)
}

// Pop 出栈，返回栈顶元素
func (s *ItemStack) Pop() Item {
	s.lock.Lock()
	defer s.lock.Unlock()
	if len(s.items) == 0 {
		return nil
	}
	item := s.items[len(s.items)-1]
	s.items = s.items[0 : len(s.items)-1]
	return item
}

1.slice相对简单

2.interface类型，允许添加任意类型元素

3.Push和Pop有加锁处理，线程安全

问题：slice的pop并不是真正意义上的pop，slice[:]只是一个新的引用，底层的内存并没有减少

container/list内置包

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package main

import (
	"container/list"
	"sync"
)

// Stack 栈结构体，读写锁
type Stack struct {
	list *list.List
	lock *sync.RWMutex
}

// NewStack 初始化栈
func NewStack() *Stack {
	list := list.New()
	l := &sync.RWMutex{}
	return &Stack{list, l}
}


// Push 入栈 加锁 
func (stack *Stack) Push(value interface{}) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	stack.list.PushBack(value)
}


// Pop 出栈
func (stack *Stack) Pop() interface{} {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	e := stack.list.Back()
	if e != nil {
		stack.list.Remove(e)
		return e.Value
	}
	return nil
}

// Peak 返回栈顶元素
func (stack *Stack) Peak() interface{} {
	e := stack.list.Back()
	if e != nil {
		return e.Value
	}

	return nil
}

// Len 长度
func (stack *Stack) Len() int {
	return stack.list.Len()
}

// Empty 判断是否为空
func (stack *Stack) Empty() bool {
	return stack.list.Len() == 0
}

container/list 是一个双向链表

用链表模拟栈，要么都向链表的最后做push和pop，要么都向链表的起点做push和pop

单链表自定义实现栈

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package main

import (
	"sync"
)

type (
	// Stack 栈结构体
	Stack struct {
		top    *node
		length int
		lock   *sync.RWMutex
	}
	// node 节点，先前指针
	node struct {
		value interface{}
		prev  *node
	}
)

// NewStack 初始化栈
func NewStack() *Stack {
	return &Stack{nil, 0, &sync.RWMutex{}}
}

// Len 返回栈的长度
func (this *Stack) Len() int {
	return this.length
}

// Peek 栈顶元素返回
func (this *Stack) Peek() interface{} {
	if this.length == 0 {
		return nil
	}
	return this.top.value
}

// Pop 删除栈顶，新栈顶元素等于该栈顶的先前指向元素，再减少长度
func (this *Stack) Pop() interface{} {
	this.lock.Lock()
	defer this.lock.Unlock()
	if this.length == 0 {
		return nil
	}
	n := this.top
	this.top = n.prev
	this.length--
	return n.value
}

// Push 入栈，新建一个节点，长度加一，先前指针指向当前的top节点，然后 新建的节点等于top
func (this *Stack) Push(value interface{}) {
	this.lock.Lock()
	defer this.lock.Unlock()
	n := &node{value, this.top}
	this.top = n
	this.length++
}

1.允许添加任意类型的元素

2.Push和Pop是线程安全的

性能对比

1

队列 Queue

队列是一种先进先出，后进后出的线性表

先进入队列的先出去，后进入队列的后出去。必须从队尾插入新元素，队列中的元素只能从队首出

队列也可以通过数组，链表实现

顺序队列

1.初始化一个数组，及两个指针，一个队头指针，一个队尾指针，都指向0的位置

2.队列总是从队头取元素，队尾插入元素

3.入队，判断队列是否已满，队尾指针是否等于长度，不等可以插入，新元素放在队尾位置，指针加一后移

4.出队，头指针和尾指针指向同一个位置，则队列为空，不为空可以出队，出队则头指针的元素出队，头指针加一后移

出队和入队的时间复杂度都是O(1)

golang 实现顺序队列

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

package main
 
import "fmt"

// ArrayQueue
type ArrayQueue struct {
    q []interface{}
    capacity int // 队列容量
    head int // 队头指针
    tail int // 队尾指针
}
 
// 创建队列
func NewArrayQueue(n int) *ArrayQueue {
    return &ArrayQueue{
        q:        make([]interface{}, n),
        capacity: n,
        head:     0,
        tail:     0,
    }
}
 
// 入队操作
func (this *ArrayQueue) EnQueue(v interface{}) bool {
    if this.tail == this.capacity { // 队列已满
        return false
    }
    this.q[this.tail] = v
    this.tail++
    return true
}
 
 
// 出队操作
func (this *ArrayQueue) DeQueue() interface{}  {
    if this.head == this.tail { // 队列已空
        return false
    }
    v := this.q[this.head]
    this.head++
    return v
}
 
// 队列不为空返回所有元素，否则返回空
func (this *ArrayQueue) String() string  {
    if this.head == this.tail {
        return  "empty queue!"
    }
    result := "head"
    for i := this.head; i <= this.tail - 1; i++ {
        result += fmt.Sprintf("<-%+v", this.q[i])
    }
    result += "<-tail"
    return result
}
 
 
// 判断队列是否为空
func (this *ArrayQueue) Empty() bool {
    if this.head == this.tail {
        return true
    }else {
        return false
    }
}
 
// 返回队列长度
func (this *ArrayQueue) Len() int {
    return len(this.q)
}
 
// 返回队头元素
func (this *ArrayQueue) GetHead() interface{} {
    if this.Empty() {
        return nil
    }
    return this.q[this.head]
}
 
 
// 判断队列是否已满
func (this *ArrayQueue) Full() bool {
    if this.tail == this.head {
        return true
    }
    return false
}
 
 
// 清空队列 并没有释放内存
func (this *ArrayQueue)  Clear() {
    this.head = 0
    this.tail = 0
}

链式队列

1.初始化也需要两个指针，队头指针，队尾指针

2.入队，让新节点的Next指向队尾节点的Next，也就是nil，再让队尾节点的Next指向新节点，队尾指针加一后移，空队列单独处理

3.出队，头指针指向的元素出队，头指针加一后移，队列长度为1的情况，单独处理

golang 实现链式队列

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package main

import (
    "fmt"
)

//链式队列的数据结构
type queueNode struct {
    data interface{} // 存放数据
    next *queueNode // 存放指针
}

type queueList struct {
    length int //存储链表长度
    front *queueNode // 指向队头
    rear *queueNode // 指向队尾
}

//链队初始化
func initQueue() *queueList {
    L := &queueList{
        length: 0,
        front: nil,
        rear: nil,
    }
    return L
}

//链队的入队
func (queue *queueList) push(val interface{}) {
    node := &queueNode{
        data: val,
        next: nil,
    }

    //处理空队
    if queue.isNull() {
        queue.front = node // 指向队头
        queue.rear = node
        queue.length ++
        return
    }

    queue.rear.next = node
    queue.rear = queue.rear.next
    queue.length ++
}


//链队的出队
func (queue *queueList) pop() {
    // 判断队空
    if queue.isNull() {
        fmt.Println("队列为空")
        return
    }

    // 处理链队中只有一个结点的特殊情况
    if queue.length == 1 {
        queue.front = nil
        queue.rear = nil
        queue.length --
        return
    }

    queue.front = queue.front.next
    queue.length --
}

//判断队空
func (queue queueList) isNull() bool {
    return queue.length == 0
}


func (queue *queueList) Traverse() (arr []interface{}) {
    pre := queue.front
    for i := 0; i < queue.length; i++ {
        arr = append(arr, pre.data, "-->")
        pre = pre.next
    }
    return
}

循环队列

循环队列是指队列是前后连成一个圆圈，它以循环的方式去存储元素，但还是会按照队列的先进先出的原则去操作

循环队列是基于数组实现的，相比于顺序队列，更好的利用数组空间

普通的数组队列在经过了一段时间的入队和出队以后，尾指针就指向了数组的最后位置了，没法再往队列里插入数据了，但是数组的前面部分（头指针的前面）由于旧的数据曾经出队了，所以会空出来一些空间，这些空间就没法利用起来

即使可以单独处理顺序队列，整体移动，也需要消耗额外的操作

循环队列也是一种线性结构

1.最后一个位置并不是结束位。对于循环队列，头指针始终指向队列的前面，尾指针始终指向队列的末尾

2.初始化队列，头指针和尾指针指向相同位置，此时队列是空

3.入队，新元素插入队尾指针位置，队尾指针加一后移

4.出队，头指针元素出队，头指针加一后移，该元素并不删除，只是不属于队列的一部分

5.继续入队，尾指针到达队列尾部时候，尾指针的下标重新变成0，而之前出队的元素则空出来

6.继续出队，则队列又有空间了，就可以继续入队，头指针的下标已经大于尾指针的下标了，这也是正式循环队列的特性导致的

7.判断队列为空的条件是：head==tail

8.判断队列满的情况：(tail+1)%n=head，取余数等于head，则表示满了，因为是循环

9.会浪费一个空间（length+1）== capacity 表示队列为满

PS：循环队列为什么用空一个元素的位置呢

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。
因此，无法通过条件front==rear来判别队列是”空”还是”满”。
解决这个问题的方法至少有三种：
1.另设一布尔变量以区别队列的空和满

2.少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）

3.使用一个计数器记录队列中元素的总数（即队列长度）。

golang 实现

预留了一个空间

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// 循环队列实现方法
type loopQueue struct {
    queues   []interface{}
    front    int //队首
    tail     int //队尾
    length   int //队伍长度
    capacity int //队伍容量
}

// NewLoopQueue 可以自己传参数，初始化队列
func NewLoopQueue() *loopQueue {
    loop := &loopQueue{
        queues:   make([]interface{}, 0, 2),
        front:    0,
        tail:     0,
        length:   0,
        capacity: 2,
    }
    //初始化队列，加入初始数据
    for i := 0; i < 2; i++ {
        loop.queues = append(loop.queues, "")
    }
    return loop
}

// Len 返回循环队列的长度
func (q *loopQueue) Len() int {
    return q.length
}

// Cap 返回循环队列的容量
func (q *loopQueue) Cap() int {
    return q.capacity
}

// IsEmpty 判断队列是否为空
func (q *loopQueue) IsEmpty() bool {
    return q.length == 0
}

// IsFull 判断队列是否满的
func (q *loopQueue) IsFull() bool {
    return (q.length + 1) == q.capacity
}

// GetFront 获取队头元素
func (q *loopQueue) GetFront() (interface{}, error) {
    if q.Len() == 0 {
        return nil, errors.New(
            "failed to getFront,queues is empty.")
    }
    return q.queues[q.front], nil
}

// Enqueue 入队，放在队尾
func (q *loopQueue) Enqueue(elem interface{}) {
    // 如果队列满了，队列扩容
    if q.IsFull() {
    	// 创建一个新队列
        buffer := new(loopQueue)
        //初始化队列，2倍容量
        for i := 0; i < 2*q.capacity; i++ {
            buffer.queues = append(buffer.queues, "")
        }
        // 搬运元素
        for i := 0; i < q.length; i++ {
            buffer.queues[i] = q.queues[q.front]
            q.front = (q.front + 1) % q.capacity
        }
        // 替换当前的queues为扩容后的队列，length不变
        q.queues = buffer.queues
        q.front = 0
        q.tail = q.length
        q.capacity = 2 * q.capacity
    }

    q.queues[q.tail] = elem
    // 因为是循环队列，下标会重新设定，循环求法
    q.tail = (q.tail + 1) % q.capacity
    q.length++
}

// Dequeue 出队
func (q *loopQueue) Dequeue() (interface{}, error) {
    if q.IsEmpty() {
        return nil, errors.New(
            "failed to dequeue,queues is empty.")
    }

    // 当队列长度小于容量1/4时，队列容量缩短一半
    if q.length <= q.capacity/4 {
    	// 创建一个新的队列
        buffer := new(loopQueue)
        //初始化队列
        for i := 0; i < q.capacity/2; i++ {
            buffer.queues = append(buffer.queues, "")
        }
        // 搬运元素
        for i := 0; i < q.length; i++ {
            buffer.queues[i] = q.queues[q.front]
            q.front = (q.front + 1) % q.capacity
        }
        // length不变，缩小其他元素
        q.queues = buffer.queues
        q.fron1t = 0
        q.tail = q.length
        q.capacity = q.capacity / 2
    }
    // 出队头元素，更新头指针
    queue := q.queues[q.front]
    q.front = (q.front + 1) % q.capacity
    // 减少长度
    q.length--
    return queue, nil
}

循环双端队列

双端队列，就是可在头部入队出队，也可在尾部入队出队

leetcode 641 设计循环双端队列

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
package lt641

// 设计实现双端队列。
//你的实现需要支持以下操作：
//
//    MyCircularDeque(k)：构造函数,双端队列的大小为k。
//    insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
//    insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
//    deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
//    deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
//    getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
//    getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
//    isEmpty()：检查双端队列是否为空。
//    isFull()：检查双端队列是否满了。

//    所有值的范围为 [1, 1000]
//    操作次数的范围为 [1, 1000]
//    请不要使用内置的双端队列库。

// ---------------------------------------------------------------

// 来回顾下队列。
// 顺序队列（基于数组，每次取数据需要进行数据搬迁，优化是等位置不够了再一次搬迁）、
// 链式队列（容易实现，无限扩展，但不太常用）、
// 循环队列（基于数组，head/tail循环移动，多占用一个数据空间）、
// 阻塞队列（取空队列头部阻塞至有值入队）、
// 并发队列(最简单的就是入队出队操作加锁)

// 队列的应用
// 线程池等资源池，通常有最大数量限制，不适合链式队列
// 银行等业务排队系统

// --------------------------------------------------------------------

// 双端队列就是队头队尾都可以进行出入队操作
// 直接上手干咯，没什么巧的
// 循环队列的难点就在于队满的判定条件。

// 另外题给所有值的范围是[1~1000]这是否要我使用而更小的数据表示类型呢？
// 搞不明白

// 初始队空，f=0=l， 尽管此时一个数据都没有
// fl					// f == l 判空
//[0, 0, 0, 0, 0, 0]	// 为了方便表示，0代表没填充数据
// 插入一个数据， f不变， l后移一位，指向末尾数据的下一位。（如果此时是设计非循环队列，那么 l==n(n为容量)就是判满条件 ）
// f  l
//[1, 0, 0, 0, 0, 0]
// 数据已满 (暂且按照非循环来看，数据满时 l == n (l==6))
// f			     l
//[1, 2, 3, 4, 5, 6]
// 头部取出数据,这时候左边空出了一个位置，l应该挪到那里去
// l  f
//[0, 2, 3, 4, 5, 6]		// 这里是为了演示需要，置0了，其实不用管，移动f/l就行，后面只能取出f~l区间里的数据
// 头部再取一个数据
// l	 f
//[0, 0, 3, 4, 5, 6]		// 这里是为了演示需要，置0了，其实不用管，移动f/l就行，后面只能取出f~l区间里的数据
// 尾部插入一个数据
//    l	 f
//[1, 0, 3, 4, 5, 6]		// 这里是为了演示需要，置0了，其实不用管，移动f/l就行，后面只能取出f~l区间里的数据

// --------------------------------------------------------------------------------
// 前面这个流程存在问题：
// 当l到数组尾部后，l == 7，但是要按循环处理的话， l就得回到0， 那么此时 f==l！导致该条件下不知道是满是空
//
// 为了实现循环队列，留一个位置让 l 指向，不填充数据，以使在队中有数据时 l != f

// 重塑后的流程如下：
// 队列有效容量变成了5

// 初始队空，f=0=l， 此时第一个位置就是 l 的占空位
// fl					// f == l 判空
//[0, 0, 0, 0, 0, 0]	// 为了方便表示，0代表没填充数据
// 插入一个数据， f不变， l后移一位，指向末尾数据的下一位。
// f  l
//[1, 0, 0, 0, 0, 0]
// 数据已满 （1） f=0, l=5=n (n为队列真实容量)
// f			  l
//[1, 2, 3, 4, 5, 0]
// 头部取出数据,这时候左边空出了一个位置，l应该挪到那里去
//    f	 	      l
//[0, 2, 3, 4, 5, 0]		// 这里是为了演示需要，置0了，其实不用管，移动f/l就行，后面只能取出 [f, l) 区间里的数据
// 头部再取一个数据
//  	 f	      l
//[0, 0, 3, 4, 5, 0]
// 尾部插入一个数据. l = (l+1)%n=(5+1)%6=0回到最左边
// l	 f
//[0, 0, 3, 4, 5, 1]
// 尾部再插入一个数据. 队列满（2） f=2, l=1
//    l	 f
//[2, 0, 3, 4, 5, 1]

// 上面有两种队列满的情况。怎么合并在一起来普适性地判断队满呢
// (2)中 l+1 = f
// (1)中 l+1 = 6, f=0, (l+1)%6 = f
// 合并起来就是 (l+1)%6 == f 为队满条件， 6为实际数组容量，5为有效数据容量

// 考虑好了循环队列（单向）后，再来看看循环双端队列。
// 就是加上队尾删除和队头插入的情况。
// 一般情况下很好理解，队尾删除就l前移， 队头插入就f前移。 （除非队已满）
// 但是如果是 f发生了循环左移至数组最末呢
// 其实并不会对队空队满条件产生影响
// 来试着看下这个场景：

// 此时队列还剩一个位置可用，front左移一位，在新的front上插入一个数据
//    f	 	      l
//[0, 2, 3, 4, 5, 0]
// f   	 	      l
//[1, 2, 3, 4, 5, 0]

// 循环右移操作 l = (l + 1) % n
// 循环左移操作 l = (l - 1) % n ? x  这样会使索引越界，因为真正循环的那一次是由 0 -> -1 -> n-1, 所以应该先加一个 n
// l = (n+l-1) % n

// -------------------------------------

// 下面给出我的程序的操作实验结果
//		obj := Constructor(5)
//		param_1 := obj.InsertFront(99)
//		param_2 := obj.InsertLast(88)
//		param_5 := obj.GetFront()
//		param_6 := obj.GetRear()
//		param_3 := obj.DeleteFront()
//		param_4 := obj.DeleteLast()
//		param_7 := obj.IsEmpty()
//		param_8 := obj.IsFull()

// 记录的队列状态为：
// data=[0 0 0 0 0 0], front=0, last=0
//data=[0 0 0 0 0 99], front=5, last=0
//data=[88 0 0 0 0 99], front=5, last=1
//data=[88 0 0 0 0 99], front=5, last=1
//data=[88 0 0 0 0 99], front=5, last=1
//data=[88 0 0 0 0 0], front=0, last=1
//data=[0 0 0 0 0 0], front=0, last=0
//data=[0 0 0 0 0 0], front=0, last=0
//data=[0 0 0 0 0 0], front=0, last=0

// 好了，开始实现循环双端队列

// -------------------------------------------------------------------------------------------------

//51/51 cases passed (20 ms)
//Your runtime beats 61.36 % of golang submissions
//Your memory usage beats 100 % of golang submissions (6.1 MB)
// 占用内存少是因为很多地方没有去用局部变量，而是以计算式传入。
// 运行时间却很一般。稍后分析

// 一个可以提升效率的地方就是可以通过添加容量字段来减少计算容量的运算。

// 奇怪的是，重新提交之后运行效率却击败了百分之九十多....

// 循环双端队列 CircularDoubleEndedQueue
type MyCircularDeque struct {
	data []int	// 数组(切片)存储数据
	// 实际容量为data容量减1，可以在这里记录也可以不记录，我选择不记录
	front int	// “头指针”数组下标
	last int	// “尾指针”数组下标
}

//    MyCircularDeque(k)：构造函数,双端队列的大小为k。
func Constructor(k int) MyCircularDeque {
	return MyCircularDeque{
		// 构造长度容量都为k+1的切片；当然也可以初始化为长度为0，容量为k+1；
		data: make([]int, k+1, k+1),	// 初始值全0
		front:0,
		last:0,
	}
}

//    insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
func (this *MyCircularDeque) InsertFront(value int) bool {
	// 检查队列是否已满
	if this.IsFull() {
		return false
	}

	// 插入元素。
	this.front = (len(this.data) + this.front - 1) % len(this.data)	// 先循环左移一位
	this.data[this.front] = value	// 填入数据

	return true
}

//    insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
func (this *MyCircularDeque) InsertLast(value int) bool {
	// 检查队列是否已满
	if this.IsFull() {
		return false
	}

	// 插入元素
	this.data[this.last] = value	// 填入数据
	this.last = (this.last + 1) % len(this.data)	// 循环右移一位

	return true
}

//    deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
func (this *MyCircularDeque) DeleteFront() bool {
	// 检查队列是否为空
	if this.IsEmpty() {
		return false
	}

	// 删除头部元素
	//this.data[this.front] = 0	// 置0，这一部完全不是必须，只是为了方便输出调试。可以将这句直接注释
	this.front = (this.front + 1) % len(this.data)	// 循环右移一位

	return true
}

//    deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
func (this *MyCircularDeque) DeleteLast() bool {
	// 检查队列是否为空
	if this.IsEmpty() {
		return false
	}

	// 删除头部元素
	this.last = (len(this.data) + this.last - 1) % len(this.data)	// 循环左移一位
	//this.data[this.last] = 0	// 置0，这一部完全不是必须，只是为了方便输出调试。可以将这句直接注释

	return true
}

//    getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
func (this *MyCircularDeque) GetFront() int {
	// 检查队列是否为空
	if this.IsEmpty() {
		return -1
	}

	// 获取头部元素
	return this.data[this.front]
}

//    getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
func (this *MyCircularDeque) GetRear() int {
	// 检查队列是否为空
	if this.IsEmpty() {
		return -1
	}

	// 获取尾部元素。这里要注意下，last应该循环左移一位得到数据下标
	return this.data[(len(this.data) + this.last - 1) % len(this.data)]
}

//    isEmpty()：检查双端队列是否为空，两个指针在一个位置。
func (this *MyCircularDeque) IsEmpty() bool {
	return this.last == this.front
}

//    isFull()：检查双端队列是否满了。
func (this *MyCircularDeque) IsFull() bool {
	return (this.last + 1) % len(this.data) == this.front
}

优先队列

优先队列分为两种，一种是最大优先队列，一种是最小优先队列

最大优先队列，出队时最大值先出

有序数组的入队时间复杂度为 O(n)，出队时间复杂度为 O(1)

无序数组的入队时间复杂度为 O(1)，出队时间复杂度为 O(n)

总的来说出入队都是O(n)

利用堆来实现优先队列

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package main

import (
	"container/heap"
	"fmt"
)

// Item 是优先队列中包含的元素。
type Item struct {
	value    string // 元素的值，可以是任意字符串。
	priority int    // 元素在队列中的优先级。
	// 元素的索引可以用于更新操作，它由 heap.Interface 定义的方法维护。
	index int // 元素在堆中的索引。
}

// 一个实现了 heap.Interface 接口的优先队列，队列中包含任意多个 Item 结构。
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	// 我们希望 Pop 返回的是最大值而不是最小值，
	// 因此这里使用大于号进行对比。
	return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

// Push 入队，尾部入队
func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

// Pop 出队，尾部出队
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // 为了安全性考虑而做的设置
	*pq = old[0 : n-1]
	return item
}

// 更新函数会修改队列中指定元素的优先级以及值。
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

// 这个示例首先会创建一个优先队列，并在队列中包含一些元素
// 接着将一个新元素添加到队列里面，并对其进行操作
// 最后按优先级有序地移除队列中的各个元素。
func main() {
	// 一些元素以及它们的优先级。
	items := map[string]int{
		"banana": 3, "apple": 2, "pear": 4,
	}

	// 创建一个优先队列，并将上述元素放入到队列里面，
	// 然后对队列进行初始化以满足优先队列（堆）的不变性。
	pq := make(PriorityQueue, len(items))
	i := 0
	for value, priority := range items {
		pq[i] = &Item{
			value:    value,
			priority: priority,
			index:    i,
		}
		i++
	}
	heap.Init(&pq)

	// 插入一个新元素，然后修改它的优先级。
	item := &Item{
		value:    "orange",
		priority: 1,
	}
	heap.Push(&pq, item)
	pq.update(item, item.value, 5)

    // 以降序形式取出并打印队列中的所有元素。
	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s ", item.priority, item.value)
	}
}

堆 heap

分为大顶堆，小顶堆

查找最大或最小：O(1)

删除最大或最小：O（logn）

插入： O（logn）或O（1）

golang 标准库，实现的是小顶堆， “container/heap”包

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
// 通过小顶堆实现，列表里是一个2个数字的列表嵌套
type IHeap []interface{}
// 返回长度
func (h IHeap) Len() int { 
    return len(h) 
}
// 小的值
func (h IHeap) Less(i, j int) bool { 
    return h[i] < h[j] 
}
// 交换
func (h IHeap) Swap(i, j int) { 
    h[i], h[j] = h[j], h[i]
}
// 入堆
func (h *IHeap) Push(x interface{}) {
    *h = append(*h, x)
}
// 出堆，得到最小元素
func (h *IHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

二叉堆

1.是一颗完全二叉树，根节点都是满的，除了最后一层

2.树中任意节点的值大于等于或小于等于（二叉大顶，小顶）其子节点的值

3.二叉堆一般都是通过数组实现

4.父节点，子节点位置关系，索引为i

左子节点：2*i+1
右子节点：2*i+2
父节点：floor((i-1)/2)

5.插入元素：插入堆尾部，重新维护堆，向上调整

6。删除元素：向下调整

golang实现二叉堆

通过数组实现一个二叉大顶堆

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// 最大堆的定义和实现：
// 最大堆
type maxHeap struct {
    size int
    nums []int
}

// 获取父节点索引
func parent(i int) int {
    if i == 0 {
        return 0
    }
    return (i - 1) / 2
}

// 获取左节点索引
func leftChild(i int) int {
    return 2*i + 1
}

// 右节点索引
func rightChild(i int) int {
    return 2*i + 2
}

// 初始化
func NewMaxHeap() *maxHeap {
    return &maxHeap{}
}

// 获取大小
func (heap *maxHeap) GetSize() int {
    return heap.size
}

// 判断是否为空
func (heap *maxHeap) IsEmpty() bool {
    return heap.size == 0
}

// 插入元素，并向上调整
func (heap *maxHeap) SiftUp(i int) {
    // 小于则赋值
    if heap.size < len(heap.nums) {
        heap.nums[heap.size] = i
    } else { // 大于则扩容
        heap.nums = append(heap.nums, i)
    }
    // 插入的是堆尾，此时的heap.size还没更新，也就是索引
    parI := parent(heap.size)
    childI := heap.size
    // 父节点小于子节点，则交换
    for heap.nums[parI] < heap.nums[childI] {
        heap.nums[parI], heap.nums[childI] = heap.nums[childI], heap.nums[parI]
        childI = parI
        parI = parent(parI)
    }
    heap.size++
}

// 向下调整
func siftDown(heap *maxHeap, parI int) {
    var maxI int
    for {
        leftI := leftChild(parI)
        switch {
        // 左索引超出size
        case leftI+1 > heap.size:
            return

            // 左索引不超,右索引超出size,说明左索引是最后索引
        case leftI+2 > heap.size:
            if heap.nums[parI] < heap.nums[leftI] {
                heap.nums[parI], heap.nums[leftI] = heap.nums[leftI], heap.nums[parI]
            }
            return
        case heap.nums[leftI] >= heap.nums[leftI+1]:
            maxI = leftI
        case heap.nums[leftI] < heap.nums[leftI+1]:
            maxI = leftI + 1
        }

        // 比左右子节点的值都大,返回
        if heap.nums[parI] >= heap.nums[maxI] {
            return
        }

        heap.nums[parI], heap.nums[maxI] = heap.nums[maxI], heap.nums[parI]
        parI = maxI
    }
}

// 取出对中最大元素,即root节点值
func (heap *maxHeap) SiftDown() (int, error) {
    if heap.IsEmpty() {
        return 0, errors.New("maxHeap is empty.")
    }
    vTop := heap.nums[0]
    heap.size--
    heap.nums[0], heap.nums[heap.size] = heap.nums[heap.size], 0

    siftDown(heap, 0)

    return vTop, nil
}


// 查看堆中最大元素
func (heap *maxHeap) GetMax() (int, error) {
    if heap.IsEmpty() {
        return 0, errors.New("maxHeap is empty.")
    }
    return heap.nums[0], nil
}