-
Notifications
You must be signed in to change notification settings - Fork 0
/
03-双向链表实现双端队列.ts
90 lines (83 loc) · 1.79 KB
/
03-双向链表实现双端队列.ts
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
class DoubleNode<T = any> {
public value: T;
public last: DoubleNode | null
public next: DoubleNode | null
constructor(val: T, last: DoubleNode | null = null, next: DoubleNode | null = null) {
this.value = val;
this.last = last;
this.next = next
}
}
/**
* 双端链表,两端都有队列的特性
*/
class MyDeque {
public head: DoubleNode | null = null;
public tail: DoubleNode | null = null;
private size: number = 0;
public isEmpty(): boolean {
return this.size === 0
}
public getSize(): number {
return this.size
}
public pushHead<T = any>(v: T): void {
let cur = new DoubleNode(v);
// 如果没有节点
if (this.head === null) {
this.head = cur;
this.tail = cur;
} else {
cur.next = this.head;
this.head.last = cur
this.head = cur
}
this.size++
}
public pollHead(): any {
let ans = null;
if (this.head === null) {
ans = null
} else {
ans = this.head.value
if (!this.head.next) {
this.head = null
this.tail = null
} else {
this.head.next.last = null;
this.head = this.head.next
}
this.size--
}
return ans
}
public pushTail<T = any>(v: T): void {
let cur = new DoubleNode(v)
if (this.tail === null) {
this.head = cur;
this.tail = cur;
} else {
this.tail.next = cur;
cur.last = this.tail
this.tail = cur
}
this.size++
}
public pollTail(): any {
let ans = null;
if (this.tail === null) {
ans = null
} else {
ans = this.tail.value
if (!this.tail.last) {
this.head = null
this.tail = null
} else {
this.tail.last.next = null;
this.tail = this.tail.last
}
this.size--
}
return ans
}
}