线性数据结构-队列

队列（Queue）是一种先进先出（First In First Out, FIFO）的数据结构，它按照元素进入的顺序来处理元素。队列的基本操作包括：

• enqueue：在队列的末尾添加一个元素。
• dequeue：移除队列的第一个元素，并返回被移除的元素。
• front 或 peek：返回队列的第一个元素，但不移除它。
• isEmpty：检查队列是否为空。
• size：返回队列中元素的数量。

数组实现队列

• 内存连续性：数组在内存中是连续分配的，这有助于利用现代处理器的缓存机制，提高访问速度。
• 动态扩容：数组需要预先定义大小或动态扩容。动态扩容涉及到创建新数组并复制旧数组元素的操作，这个操作的时间复杂度为O(n)。
• 插入和删除操作：在队列末尾插入元素（enqueue）的时间复杂度为O(1)，但在队列开头删除元素（dequeue）时，由于需要移动所有后续元素，时间复杂度也为O(n)。不过，如果只在数组末尾进行操作，这个复杂度可以降低到O(1)。

class Queue {
    contructor(){
        this._queue = [];
    }

    isEmty() {
        return this._queue.length === 0;
    }

    enqueue(value) {
        this._queue.push(value);
    }

    dequeue() {
        if (this.isEmty()) {
            return undefined;
        }
        return this._queue.shift();
    }
    
    size() {
        return this._queue.length;
    }

    peek() {
        if (this.isEmty()) {
            return undefined;
        }
        return this._queue[0];
    }
}
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

链表实现队列

• 内存分配：链表节点在内存中可以分散分配，不需要连续的内存空间。
• 动态大小：链表可以根据需要动态地分配节点，不需要担心扩容问题。
• 插入和删除操作：在链表队列的末尾插入元素（enqueue）和从头部删除元素（dequeue）的时间复杂度都为O(1)，因为只需要改变指针的指向。
• 额外开销：链表操作涉及到额外的指针操作，可能会有一些性能开销，尤其是在js中，对象和指针的处理通常比原始数据类型慢。

class Node {
    constructor(value){
        this.value = value;
        this.next  = null;
    }
}


class Queue {
    contructor(){
        this._front = null
        this._rear = null
        this._size = 0
    }

    isEmty() {
        return this._size === 0;
    }

    size() {
        return this._size;
    }

    dequeue() {
        if (this.isEmty()) {
            return undefined;
        }
        this._size--
        const removeNode = this._front
        this._front = this._front.next
        if (this.isEmty()) {
            this._rear = null
        }
        return removeNode.value;
    }
    
    enqueue(value) {
        const newNode = new Node(value)
        if (this.isEmty()) {
            this._front = newNode
            this._rear = newNode
        } else {
            this._rear.next = newNode
            this._rear = newNode
        }
        this._size++
    }
    peek() {
        if (this.isEmty()) {
            return undefined;
        }
        return  this._front.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54