双向队列,双栈缓冲区的实现

双向队列

API

image-20200717093114582
image-20200717093114582

实现

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
package ds

import java.util.Deque

/**
* 双向队列类
* */
class Deque<T> : Collection<T> {
private val list = LinkedList<T>()

override fun isEmpty() = list.size == 0

fun pushLeft(element: T) = list.addFirst(element)

fun pushRight(element: T) = list.addLast(element)

fun popLeft(): T = list.removeFirst()

fun popRight(): T = list.removeLast()

override val size: Int
get() = list.size

/**
* 是否包含[element]
* */
override fun contains(element: T): Boolean {
return indexOf(element) != -1
}

/**
* 是否包含所有[elements]
* */
override fun containsAll(elements: Collection<T>): Boolean =
if (elements.isEmpty())
false
else
elements.all {
contains(it)
}

/**
* 查看[element]的位置
* */
private fun indexOf(element: T): Int {
var index = 0
this.forEach {
if (it == element) {
return index
}
index++
}
return -1
}

override fun toString(): String {
return list.toString()
}

override fun iterator(): Iterator<T> {
return list.iterator()
}
}

关于双向链表的实现见这篇博客: 算法(第四版)笔记(3)—双向链表(LinkedList)实现

缓冲区Buffer

API

image-20200717093315081
image-20200717093315081

实现

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
package ds

class Buffer {
private val ls = Stack<Char>()
private val rs = Stack<Char>()

fun insert(c: Char) {
ls.push(c)
}

fun delete(): Char =
if (ls.size() == 0) throw NoSuchElementException("无法删除")
else ls.pop()

fun left(k: Int) {
if (k > ls.size()) throw IllegalArgumentException("无法到达")
for (i in 1..k) {
rs.push(ls.pop())
}
}

fun right(k: Int) {
if (k > rs.size()) throw IllegalArgumentException("无法到达")
for (i in 1..k) {
ls.push(rs.pop())
}
}

val size: Int
get() = ls.size() + rs.size()

override fun toString(): String {
return StringBuilder().also {
it.append(ls)
it.reverse()
it.append(" | ")
it.append(rs)
}.toString()
}
}

关于栈的实现见这篇博客:算法(第四版)笔记(1)—简单类的实现

测试

image-20200717095951864
image-20200717095951864
image-20200717095958140
image-20200717095958140

Github

Github