队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
# 一、简介
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
- 用数组实现一个顺序队列
- 用链表实现一个链式队列
- 实现一个循环队列
# 二、手写
# 1. 数组队列
function ArrayQueue() {
let queue = []
this.push = function(value) {
queue.push(value)
}
this.pop = function(value) {
queue.shift(value)
}
this.getFront = function() {
return queue[0]
}
this.getRear = function() {
return queue[queue.length - 1]
}
this.clear = function() {
queue = []
}
this.size = function() {
return queue.length
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2. 链表队列
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
class LinkedQueue {
constructor() {
this.head = null
this.tail = null
}
enqueue(value) {
if (this.head === null) {
this.head = new Node(value)
this.tail = this.head
} else {
this.tail.next = new Node(value)
this.tail = this.tail.next
}
}
dequeue() {
if (this.head === null) {
return -1
} else {
const value = this.head.value
this.head = this.head.next
return value
}
}
}
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
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
# 三、思考题
# 1. 设计双端队列(#641)
设计实现双端队列。
你的实现需要支持以下操作:
MyCircularDeque(k): 构造函数, 双端队列的大小为k。
insertFront(): 将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast(): 将一个元素添加到双端队列尾部。 如果操作成功返回 true。
deleteFront(): 从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast(): 从双端队列尾部删除一个元素。 如果操作成功返回 true。
getFront(): 从双端队列头部获得一个元素。 如果双端队列为空, 返回 - 1。
getRear(): 获得双端队列的最后一个元素。 如果双端队列为空, 返回 - 1。
isEmpty(): 检查双端队列是否为空。
isFull(): 检查双端队列是否满了。
示例:
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了,返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4
提示:
所有值的范围为[1, 1000]
操作次数的范围为[1, 1000]
请不要使用内置的双端队列库。
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
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
(待续)