简单的Queue实现

Posted on In

简单的 Queue 实现

数组实现

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
class Queue {
  constructor(size = 10) {
    this.size = size // 队列最大长度
    this.top = 0 // 首位置
    this.bottom = -1 // 尾位置
    this.elems = 0 // 成员个数
    this.arr = [] // 队列
  }

  add(elem) {
    if (this.elems == this.size) {
      console.log("Queue is full")
      return
    }
    if (this.bottom == this.size - 1) {
      // 循环队列
      this.bottom = -1
    }
    this.arr[++this.bottom] = elem
    this.elems++
    return true
  }

  out() {
    if (this.elems == 0) {
      console.log("Queue is empty")
      return
    }
    let elem = this.arr[this.top]
    this.arr[this.top] = null
    this.top++
    if (this.top == this.size) {
      this.top = 0
    }
    this.elems--
    return elem
  }
}
var queue = new Queue()
queue.add(3)
queue.add(2)
console.log(queue.out())
console.log(queue.out())
console.log(queue.out())

链式实现

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
class Node {
  constructor(data = -1, next = null) {
    this.data = data
    this.next = next
  }
}
class Queue {
  constructor() {
    this.top = null // 首指针
    this.bottom = null // 尾指针
    this.elems = 0 // 成员个数
  }

  add(elem) {
    if (this.elems == 0) {
      this.top = this.bottom = new Node(elem)
    } else {
      let newNode = new Node(elem)
      this.bottom.next = newNode
      this.bottom = newNode
    }
    this.elems++
  }

  out() {
    if (this.elems == 0) {
      console.log("queue is empty")
      return
    }
    let current = this.top
    let value = current.data
    this.top = this.top.next
    this.elems--
    this.current = null
    return value
  }
}

结果

1
2
3
4
3
2
Queue is empty
undefined