【JavaScript数据结构与算法】二、队列 及leetcode实战

队列

队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

首先需要一个用于存储队列中元素的数据结构。我们可以使用数组，就像上一的Stack类那样。但是，为了写出一个在获取元素时更高效的数据结构，我们将使用一个对象来存储我们的元素。你会发现Queue类和Stack类非常类似，只是添加和移除元素的原则不同。

接下来需要声明一些队列可用的方法。

• enqueue(element(s))：向队列尾部添加一个（或多个）新的项。
• dequeue()：移除队列的第一项（即排在队列最前面的项）并返回被移除的元素。
• peek()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。
• isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。
• size()：返回队列包含的元素个数，与数组的length属性类似。

class Queue {
    constructor() {
        this.count = 0; // 控制队列的大小
        this.lowestCount = 0; // 追踪第一个元素
        this.items = {};
    }
    enqueue(element) {
        this.items[this.count] = element;
        this.count++;
    }
    dequeue() {
        if (this.isEmpty()) return undefined;
        const result = this.items[this.lowestCount]; 
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;
    }
    peek() {
        if (this.isEmpty()) return undefined;
        return this.items[this.lowestCount];
    }
    size() {
        return this.count - this.lowestCount;
    }
    isEmpty() {
        return this.count - this.lowestCount === 0;
    }
    clear(){
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
    toString(){
        if (this.isEmpty()) return undefined;
        let objString = `${this.items[this.lowestCount]}`;
        for (let i = this.lowestCount + 1; i < this.count; i++) {
            objString = `${objString},${this.items[i]}`;
        }
        return objString;
    }
}
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

leetcode实战

225. 用队列实现栈 (easy)

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

方法1.使用两个 Queue 实现

• 思路：为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中queue1 用于存储栈内的元素，queue2 作为入栈操作的辅助备份队列：
  • 入栈的时候，queue1 入队；
  • 出栈的时候，如果queue1为空，则交换queue1 和queue2，为的是将备份队列的元素全部加入queue1，然后将queue1中除了最后一个元素外全部出队并备份到queue2
• 复杂度分析：push的时间复杂度为O(1)，pop的时间复杂度为O(n)。空间复杂度O(n)，其中n是栈内元素的个数，用两个队列来存储

var MyStack = function () {
    this.queue1 = []
    this.queue2 = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
    this.queue1.push(x)
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function () {
    // 减少两个队列交换的次数， 只有当queue1为空时，交换两个队列
    if (!this.queue1.length) [this.queue1, this.queue2] = [this.queue2, this.queue1];
    
    while (this.queue1.length > 1) { //当队列1的元素数量大于1的时候不断将元素push进备份队列
        this.queue2.push(this.queue1.shift());
    }
    return this.queue1.shift(); //最后将队列1最后一个元素出队
};

/**
 * @return {number}
 */
MyStack.prototype.top = function () {
    const x = this.pop(); //查看栈顶，队列出队，然后在push进队列1
    this.queue1.push(x);
    return x;
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
    return !(this.queue1.length || this.queue2.length);
};
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

方法2.使用一个 队列 实现

• 思路：使用一个 队列 实现，入栈的时候直接push进队列就行，出栈的时候将除了最后一个元素外的元素全部加入到队尾。
• 复杂度分析：push的时间复杂度为O(1)，pop的时间复杂度为O(n)，空间复杂度O(n)

var MyStack = function () {
    this.queue = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
    this.queue.push(x)
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function () {
    let size = this.queue.length;
    while(size-- > 1) {//将除了最后一个元素外的元素全部加入到队尾。
        this.queue.push(this.queue.shift());
    }
    return this.queue.shift();
};

/**
 * @return {number}
 */
MyStack.prototype.top = function () {
    const x = this.pop();//先出栈，然后在加入队列
    this.queue.push(x);
    return x;
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
    return !this.queue.length;
};
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

933. 最近的请求次数 (easy)

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t 值。

• 思路：将请求加入队列，如果队头元素请求的时间在[t-3000,t]之外 就不断出队
• 复杂度分析
  • 时间复杂度：均摊 O(1)，每个元素至多入队出队各一次。
  • 空间复杂度：O(L)，其中 L 为队列的最大元素个数。

var RecentCounter = function() {
    this.queue = []
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    this.queue.push(t)
    const condition = t - 3000;
    while(this.queue[0]<condition){
        this.queue.shift();
    }
    return this.queue.length
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

622. 设计循环队列 (medium)

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

• 思路：在循环队列中，当队列为空，可知front=rear；而当所有队列空间全占满时，也有 front=rear。为了区别这两种情况，假设队列使用的数组有capacity 个存储空间，则此时规定循环队列最多只能有capacity−1 个队列元素，当循环队列中只剩下一个空存储单元时，则表示队列已满。根据以上可知，队列判空的条件是front=rear，而队列判满的条件是 front=(rear+1) mod capacity。
  对于一个固定大小的数组，只要知道队尾rear 与队首 front，即可计算出队列当前的长度：(rear−front+capacity) mod capacity

• 复杂度分析

  • 时间复杂度：初始化和每项操作的时间复杂度均为 O(1)。
  • 空间复杂度O(k)，其中 k* 为给定的队列元素数目。

/**
 * @param {number} k
 */
var MyCircularQueue = function (k) {
    this.front = 0
    this.rear = 0

    this.maxLen = k+1
    this.circleQueue = new Array(k+1).fill(0);
};

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function (value) {
    if (this.isFull()) return false;
    this.circleQueue[this.rear] = value
    this.rear = (this.rear + 1) % this.maxLen
    return true
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function () {
    if (this.isEmpty()) return false;
    this.front = (this.front + 1) % this.maxLen
    return true
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Front = function () {
    if (this.isEmpty()) return -1;
    return this.circleQueue[this.front]
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function () {
    if (this.isEmpty()) return -1;
    let tail = (this.rear - 1 + this.maxLen) % this.maxLen
    return this.circleQueue[tail]
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function () {
    // 两指针位置一致
    return this.front === this.rear
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function () {
    return this.front === ((this.rear + 1) % this.maxLen)
};
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