Yanniyanni

队列

上次更新时间：4/6/2021, 6:10:35 PM 0

队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First In First Out）的线性表，简称 FIFO 结构。

# 存储结构

队列也可以有两种存储结构：

  • 顺序存储结构：可用 （一维数组）。

    顺序存储结构的还可以分为循环队列，头尾相接的循环队列有利于解决假溢出问题（当然也要考虑真溢出）。循环队列需要考虑前后指针指向、空队列和满队列问题。

  • 链式存储结构：链队列。（其实就是线性表的单链表，只不过是尾进头出）

存储结构 操作 时间复杂度 应用场景
顺序存储结构 入队 O(1) 可以确定队列长度时，使用循环队列
出队
普通队列：O(n)
循环队列：O(1)
链式存储结构 入队 O(1) 无法预测队列长队时，使用链队列
出队 O(1)

# 队列的实现

JavaScript 中没有队列的数据结构，但是可以用数组实现队列的所有功能。

# 抽象数据类型定义

  • ADT 队列（Queue）
    • Data
      • 同线性表，相邻元素具有前驱和后继关系
    • Operation
      • Init(): 初始化操作，建立一个空队列 Q。
      • Destroy(): 若队列 Q 存在，则销毁它。
      • Clear(): 清空队列。
      • Enqueue(): 向队尾插入新元素 e。
      • Dequeue(): 删除队头元素，并用 e 返回其值。
      • length(): 返回队列的元素个数。
      • Front(): 读取队首元素
      • Back(): 读取队尾元素
      • ToString(): 显示队列内所有元素
      • Empty(): 队列是否为空
  • endADT
function Queue() { 
    this.dataStore = []; 
    this.clear = clear;
    this.enqueue = enqueue; 
    this.dequeue = dequeue; 
    this.front = front; 
    this.back = back;
    this.toString = toString; 
    this.empty = empty; 
}
function clear() {
    this.dataStore = [];
}
function enqueue(element) { 
    this.dataStore.push(element); 
}
function dequeue() { 
    return this.dataStore.shift(); 
}
function front() { 
    return this.dataStore[0]; 
}
function back() { 
    return this.dataStore[this.dataStore.length-1]; 
}
function toString() { 
    var retStr = ""; 
    for (var i = 0; i < this.dataStore.length; ++i) { 
        retStr += this.dataStore[i] + "\n"; 
        }
        return retStr; 
}
function empty() { 
    if (this.dataStore.length == 0) { 
        return true; 
    }else { 
        return false; 
    } 
}
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

# 队列的应用

符合先进先出的场景都可以使用队列来解决。

上次更新时间: 4/6/2021, 6:10:35 PM

← 线性表 →