前端数据结构——队列篇

发表于 更新于 分类于

队列是数据结构中的一种，它与实际生活中的排队相似：在一条队伍中，先来的人总是能够先得到服务，后来的人只能排在队伍末尾等候。队列也是一样，它符合先进先出 FIFO（First Input First Out）的顺序。

队列的类型

队列有两种类型：一种是和日常排队类似的队列，叫做普通队列；另一种叫做环形队列。

对于一个队列来说，有队头和队尾，以及容量。

普通队列

普通队列的队头和队尾是分开的，当队头的元素离开队列后，下一个元素就会成为队头，而新加入的元素会跟随在原本的队尾之后，成为新的队尾。

环形队列

当只有一个元素时，队头队尾是同一个元素；当队列容量已满时，队头和队尾是连接在一起的；当队头的元素离开后，下一个元素会成为队头，而新的元素则会插入原本队头的位置成为新的队尾。

在容量确定的情况下，普通队列前面的元素离开后，对应的内存就会被空置，而在环形队列中，前面的元素离开，新的元素就会占据原来的内存。相比之下，就容量而言，环形队列具有更高的内存利用率，可以减小内存的开支消耗。

属性

  1. 队列长度的属性，因为队列的实际长度可能并不会达到队列容量的大小
  2. 队列中用来存放元素的数组（为什么是？如果说队列与 JS 中的哪一种数据类型最相似的话，那数组肯定是最好的答案）

方法

  1. 将元素插入队尾的方法
  2. 将队头移出队列的方法
  3. 清空队列的方法
  4. 判断队列是否已满（如果已满，则不能再插入元素）
  5. 判断队列是否为空（如果为空，则不能移除元素）
  6. 遍历所有元素的方法
  7. ……（你还可以根据你的实际需要增加方法，如定时从队列中执行任务、增加任务等）

代码实现

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
/**
 * 生成随机字符串
 * @param {number} [len] 字符串长度
 */
export function randomStr(len = 6) {
  let str = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
  let l = str.length;
  let pwd = "";
  for (let i = 0; i < len; i++) pwd += str.charAt(Math.floor(Math.random() * l));
  return pwd;
}

/**
 * 函数处理队列
 */
export class Queue {
  RUN_TIMER = {};
  DATA_ALL = [];
  DATA_ALL_ID = [];
  DATA_RUNING = {};
  DATA_ERROR = [];
  $EVENT = (type, data) => {};
  constructor(options = {}, event = () => {}) {
    const { NAME = "", RUN_MAX = 1, RUN_TIMEOUT = 20000, ERROR_DELAY = true, ERROR_DELAY_TIME = 20000, ERROR_TRYTIMES = 0, RUN_NOW = true } = options;
    this.NAME = NAME; //队列名称
    this.RUN_NOW = RUN_NOW; //是否立即执行
    this.RUN_MAX = RUN_MAX; //同时进行的数量
    this.RUN_TIMEOUT = RUN_TIMEOUT; //单个超时时间
    this.ERROR_DELAY = ERROR_DELAY; // 是否开启运行出错后延迟处理
    this.ERROR_DELAY_TIME = ERROR_DELAY_TIME; // 运行出错后重试延迟时间
    this.ERROR_TRYTIMES = ERROR_TRYTIMES; // 运行出错后重试次数，0表示无上限，达到次数后移除队列
    this.$EVENT = event; // 状态
  }
  getId() {
    return Date.now().toString().slice(7) + randomStr();
  }
  log(...args) {
    // console.log(this.NAME, ...args);
  }
  push(id, fn) {
    if (typeof id === "function") {
      fn = id;
      id = this.getId();
    } else {
      if (this.DATA_ALL_ID.includes(id) || this.DATA_RUNING[id]) {
        return;
      }
    }
    this.DATA_ALL_ID.push(id);
    this.DATA_ALL.push({
      id,
      entryTime: Date.now(),
      fn,
      startTime: 0,
      tryTimes: 1
    });
    this.log("■■■■■■push■■■■■■", id, this.DATA_ALL_ID, this.DATA_RUNING);
    this.check();
    return {
      id,
      length: this.DATA_ALL.length,
      runing: Object.keys(this.DATA_RUNING).length
    };
  }
  unshift(id, fn) {
    if (typeof id === "function") {
      fn = id;
      id = this.getId();
    } else {
      if (this.DATA_ALL_ID.includes(id) || this.DATA_RUNING[id]) {
        return;
      }
    }
    this.DATA_ALL_ID.unshift(id);
    this.DATA_ALL.unshift({
      id,
      entryTime: Date.now(),
      fn,
      startTime: 0,
      tryTimes: 1
    });
    this.log("■■■■■■unshift■■■■■■", id, this.DATA_ALL_ID, this.DATA_RUNING);
    this.check();
    return {
      id,
      length: this.DATA_ALL.length,
      runing: Object.keys(this.DATA_RUNING).length
    };
  }
  try(item) {
    if (item.tryTimes < this.ERROR_TRYTIMES || !this.ERROR_TRYTIMES) {
      item.tryTimes++;
      item.tryEntryTime = Date.now();
      this.DATA_ALL.push(item);
      this.DATA_ALL_ID.push(item.id);
      this.check();
      return { code: 0, isEnd: false, data: item };
    } else {
      this.DATA_ERROR.push(item);
      return { code: 1, isEnd: true, data: item };
    }
  }
  start() {
    this.RUN_NOW = true;
    this.check();
  }
  check() {
    if (!this.RUN_NOW) {
      return;
    }
    const nowTime = Date.now();
    const runing = Object.values(this.DATA_RUNING);
    if (runing.length === 0 && this.DATA_ALL.length === 0) {
      this.finish();
      return;
    }
    runing.forEach((item) => {
      const startTime = item.tryStartTime || item.startTime;
      if (nowTime - startTime > this.RUN_TIMEOUT) {
        this.error(item.id, "checktimeout");
      }
    });
    setTimeout(() => {
      const runingNum = Object.keys(this.DATA_RUNING).length;
      this.next(this.RUN_MAX - runingNum);
    });
  }
  next(len = 1) {
    if (this.DATA_ALL.length === 0 || len < 1) {
      return;
    }
    const runData = this.DATA_ALL.splice(0, len);
    this.DATA_ALL_ID.splice(0, len);
    runData.forEach((item) => {
      item.startTime = Date.now();
      this.DATA_RUNING[item.id] = item;
      ((item) => {
        const t = item.id;
        setTimeout(
          () => {
            item.fn(
              () => {
                this.done(t);
              },
              () => {
                return this.error(t);
              }
            );
            this.RUN_TIMER[t] = setTimeout(() => {
              this.error(t, "timeout");
            }, this.RUN_TIMEOUT);
          },
          item.tryTimes > 1 ? this.ERROR_DELAY_TIME : 0
        );
      })(item);
    });
  }
  done(id) {
    const item = this.DATA_RUNING[id];
    this.RUN_TIMER[id] && clearTimeout(this.RUN_TIMER[id]);
    if (item) {
      delete this.DATA_RUNING[id];
      this.check();
    }
  }
  finish() {
    this.$EVENT("finish", this.DATA_ERROR);
  }
  error(id, type = "fn") {
    this.RUN_TIMER[id] && clearTimeout(this.RUN_TIMER[id]);
    delete this.RUN_TIMER[id];
    const item = this.DATA_RUNING[id];
    console.warn(this.NAME, "error", id, type);
    if (item) {
      this.done(item.id);
      return this.try(item);
    }
    return { code: 1, isEnd: true, data: item };
  }
  clear() {
    for (const key in this.RUN_TIMER) {
      this.RUN_TIMER[key] && clearTimeout(this.RUN_TIMER[key]);
    }
    this.DATA_ALL = [];
    this.DATA_ALL_ID = [];
    this.DATA_RUNING = {};
    this.DATA_ERROR = [];
  }
}

数据处理队列

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
/**
 * 数据处理队列
 */
export class dataQueue {
  RUN_TIMER = {}; // 超时监听
  DATA_ORIGIN = []; //原始单条数据
  DATA_GROUP = []; //切割后的数据 Array<{id,time,data}>
  DATA_RUNING = {}; //正在运行的数据
  /**
   *
   * @param {object} options 配置参数
   * @param {function} run 执行函数（data, done, err）
   * @param {function} callback 状态回调函数
   */
  constructor(options = {}, run = (data, done, err) => {}, callback = (code, data, msg) => {}) {
    const { NAME = this.getId(), RUN_TIMEOUT = 20000, RUN_DELAY = 5000, RUN_NUM = 10, RUN_MAX = 1, RUN_NOW = true, ERROR_TRYTIMES = 3 } = options;
    this.NAME = "$$UNI__DATA:" + NAME; //队列名称（用于本地存储）
    this.RUN_NOW = RUN_NOW; //是否立即执行
    this.RUN_TIMEOUT = RUN_TIMEOUT; //单个超时时间
    this.RUN_NUM = RUN_NUM; // 执行条数
    this.RUN_DELAY = RUN_DELAY; //push后延迟执行时间
    this.ERROR_TRYTIMES = ERROR_TRYTIMES; //重试次数
    this.RUN_MAX = RUN_MAX; // 同时执行任务
    this._RUN = run; // 状态
    this._CALLBACK = callback; // 状态
    this.DATA_ORIGIN = this.getLocalData();
    if (this.DATA_ORIGIN.length > 0) {
      console.log(this.DATA_ORIGIN);
      this.addAfter(true);
    }
  }
  getId() {
    return Date.now().toString().slice(7) + randomStr();
  }
  getLocalData() {
    return JSON.parse(uni.getStorageSync(this.NAME) || "[]");
  }
  setLocalData() {
    const all = [...this.DATA_ORIGIN];
    this.DATA_GROUP.forEach((item) => {
      all.push(...item.data);
    });
    for (const id in this.DATA_RUNING) {
      const item = this.DATA_RUNING[id];
      all.push(...item.data);
    }
    uni.setStorageSync(this.NAME, JSON.stringify(all));
  }
  push(item, immediate = false) {
    this.DATA_ORIGIN.push(item);
    this.log("■■■■■■push", item);
    this.addAfter(immediate);
  }
  unshift(item, immediate = true) {
    this.DATA_ORIGIN.unshift(item);
    this.log("■■■■■■unshift", item);
    this.addAfter(immediate);
  }
  runAll() {
    this.addAfter(true);
  }
  /**
   * 切割数据
   * @param {boolean} all 是否全部切割
   * @returns {boolean} 是否切割数据
   */
  groupData(all = false) {
    // 数据长度够RUN_NUM 或者 切割所有数据
    if (this.DATA_ORIGIN.length >= this.RUN_NUM || (this.DATA_ORIGIN.length > 0 && all)) {
      const data = this.DATA_ORIGIN.splice(0, this.RUN_NUM);
      this.DATA_GROUP.push({ data });
      this.groupData();
      return true;
    }
    // 是否有完整数据
    return false;
  }
  addAfter(immediate) {
    this.setLocalData();
    // 清除定时器PUSH防抖定时器
    this.RUN_TIMER["PUSH"] && clearTimeout(this.RUN_TIMER["PUSH"]);
    if (immediate) {
      this.groupData(true);
      this.next(10);
    } else {
      this.groupData() && this.check();
      this.RUN_TIMER["PUSH"] = setTimeout(() => {
        delete this.RUN_TIMER["PUSH"];
        console.log(this);
        this.groupData(true);
        this.check();
      }, this.RUN_DELAY);
    }
  }
  start() {
    this.RUN_NOW = true;
    this.check();
  }
  check() {
    if (!this.RUN_NOW) {
      return;
    }
    const nowTime = Date.now();
    for (const id in this.DATA_RUNING) {
      const item = this.DATA_RUNING[id];
      const time = item.time;
      if (nowTime - time > this.RUN_TIMEOUT) {
        this.try(item);
      }
    }
    const runingNum = Object.keys(this.DATA_RUNING).length;
    this.next(this.RUN_MAX - runingNum);
  }
  next(len = 1) {
    if (len < 1 || (!this.DATA_ORIGIN.length && !this.DATA_GROUP.length)) {
      return;
    }
    if (this.DATA_GROUP.length < len) {
      this.groupData(true);
    }
    const runData = this.DATA_GROUP.splice(0, len);
    runData.forEach((item) => {
      this.runItem(item);
    });
  }
  runItem(item) {
    this.log("run", item);
    const data = item.data;
    const id = (item.id = item.id || this.getId());
    item.time = Date.now();
    item.errTimes = item.errTimes || 0;
    this.DATA_RUNING[id] = item;
    // 超时后执行check
    this.RUN_TIMER[id] = setTimeout(() => {
      this.err(id);
    }, this.RUN_TIMEOUT);
    // 执行新的一组数据
    this._RUN(
      data,
      () => {
        this.done(id);
      },
      () => {
        this.err(id);
      }
    );
  }
  done(id) {
    const item = this.clearItem(id);
    this.log("done", item);
    this.setLocalData();
    this.check();
  }
  err(id) {
    const item = this.clearItem(id);
    this.log("err", item);
    this.check();
    if (item) {
      this.try(item);
    }
  }
  try(item) {
    if (item.errTimes < this.ERROR_TRYTIMES) {
      item.errTimes++;
      this.DATA_GROUP.push(item);
      this.check();
    } else {
      uni.getNetworkType({
        success: (res) => {
          if (res.networkType === "none") {
            this.DATA_GROUP.push(item);
            this.log("无网状态", item);
          } else {
            this.setLocalData();
            this._CALLBACK(50, item.data, `重试${item.errTimes}次失败`);
          }
        }
      });
    }
  }
  clearItem(id) {
    let item = this.DATA_RUNING[id];
    this.RUN_TIMER[id] && clearTimeout(this.RUN_TIMER[id]);
    if (!item) {
      // 要删除的id正在重试
      const index = this.DATA_GROUP.findIndex((a) => id === a.id);
      item = this.DATA_GROUP[index];
      this.DATA_GROUP.splice(index, 1);
      console.warn("超时后成功", item);
    }
    delete this.DATA_RUNING[id];
    delete this.RUN_TIMER[id];
    return item;
  }
  clear() {
    for (const key in this.RUN_TIMER) {
      this.RUN_TIMER[key] && clearTimeout(this.RUN_TIMER[key]);
    }
    this.DATA_ORIGIN = [];
    this.DATA_GROUP = [];
    this.DATA_RUNING = {};
  }
  log(...args) {
    console.warn(...args);
  }
}

单一循环队列

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
let singleQueueFlag = 0;

/**
 * 单一循环队列
 * @param {Function} fn 返回成功、失败、完成三个状态
 */
export function singleQueue(fn) {
  let times = 0;
  const check = () => {
    return fn()
      .then((isEnd = false) => {
        if (isEnd === true) {
          return Promise.resolve({ times, isEnd });
        } else {
          if (singleQueueFlag) {
            return Promise.reject({ times, isEnd, singleQueueFlag, from: 1 });
          } else {
            times++;
            return check();
          }
        }
      })
      .catch((res = "") => {
        return Promise.reject({ times, res, from: 2 });
      });
  };
  return check();
}

/**
 * 单一循环队列状态标记
 */
export function singleQueueSign(flag) {
  singleQueueFlag = flag;
}

等待队列

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
/**
 * 等待队列，间隔最小时间后执行下一个队列
 */
export class WaitingQueue {
  // 传递等待时间 默认一秒
  constructor(waitingTime = 1) {
    this.isBusy = false;
    this.isFirst = true;
    this.waitingTime = waitingTime;
    this.box = [];
  }
  // 初始化
  init() {
    this.isBusy = false;
    this.isFirst = true;
    this.box = [];
  }
  get size() {
    return this.box.length;
  }

  get isEmpty() {
    return !this.box.length;
  }

  // 清空队列
  clear() {
    this.init();
  }

  lazyRun(func, time = 0) {
    setTimeout(func.bind(this), time);
  }
  // 进入队列方法，
  entry(func) {
    // 无论如何，队列方法先放入数组中
    this.box.unshift(func);
    // 判断是否第一次执行，如果是，自执行启动
    if (this.isFirst) {
      this.isFirst = false;
      this.next();
      return;
    }
  }
  // 执行下一个队列方法
  next() {
    // 每次执行下一个队列时，先检查能否执行
    if (!this.check()) {
      return;
    }
    // 取出队列中的方法
    let func = this.box.pop();
    // done 函数，外部调用,time：强制等待时间，cb：调用后通知
    func(
      (time) =>
        new Promise((resolve) => {
          // 不忙
          this.isBusy = false;
          // 等待时间 可能传0不等待，或者默认
          let waitTime = (time ?? this.waitingTime) * 1000;
          // 延迟执行
          this.lazyRun(() => {
            // 下一步延迟执行,确保resolve先执行
            this.lazyRun(this.next);
            resolve();
          }, waitTime);
        })
    );
  }
  // 检查能否执行下一个队列的方法
  check() {
    // 如果队列都空了，不执行
    if (this.isEmpty) {
      this.isFirst = true;
      this.isBusy = false;
      return false;
    }
    // 如果队列正在执行，不执行
    if (this.isBusy) {
      return false;
    }
    // 其他的都继续执行
    this.isBusy = true;
    return true;
  }
}

应用

通过一个专门用来存放请求的队列，实现请求发起的前后顺序（先进入的先发起）及当前页面中同时发起请求的数量（进入队列的队列在发起的同时移出，请求结束后向队列中添加下一个请求），甚至可以通过队列实现请求的自动发起（这就需要对 demo 中的代码进行修改从而实现想要的功能）。