javascript数据结构—

　　队列是一种先进先出的数据结。队列只能在队尾插入元素，在队首删除元素，这点和栈不一样。它用于存储顺序排列的数据。队列就像我们日常中的排队一样，排在最前面的第一个办理业务，新来的人只能在后面排队。队列这种数据结构在编程中被用到很多地方。

定义队列的操作

　　上图展示了队列的两个操作，入队和出队。出队操作是删除对头的元素，入队操作是在队尾添加元素。除此之外我们还需要能够获取队首和队尾的元素或者全队列的元素，还需要知道队列的长度，还需要一个方法来清空队列，由此，我们定义队列的方法。

enqueue() 入队
dequeue() 出队
front() 返回队首
back() 返回队尾
toString() 返回所有队列中所有元素
length() 返回队列的长度
clear() 清空队列

队列的实现

　　javascript中的数组具有其他编程语言的数组没有的缺点，直接只用数组的push()方法就可以在数组末端加入元素，使用shift()方法可以删除数组的第一个元素。使用数组来实现队列顺理成章。

　　准备开始实现对列Queue类，先从构造函数开始；

function Queue() {

    this.dataStore = [];

    this.enqueue = enqueue;

    this.dequeue = dequeue;

    this.front = front;

    this.back = back;

    this.toString = toString;

    this.length = length;

}

　　接下来开始实现对列的各个方法。

　　enqueue()方法向队尾添加一个元素，dequeue()方法删除队首的元素：

function enqueue(element) {

    this.dataStore.push(element);   // 把新来的元素放在队尾

}

function dequeue() {

    return this.dataStore.shift();    // 删除队首元素，并把这个元素返回

}

　　front()和back()方法分别是返回队列的队首和队尾的元素：

function front() {

    return this.dataStore[0];  // 返回队首元素

}

function back() {

    return this.dataStore[this.dataStore.length - 1];  // 返回队尾元素

}

　　toString() 方法显示队列内的所有元素:

function toString() {

    var retStr = '';

    this.dataStore.forEach(val => {   // 遍历队列，把队列中的所有元素拼成字符串返回

        retStr += val + '\n';

    });

    return retStr;

}

　　length() 方法返回队列长度，clear()方法清空队列：

function length() {

    return this.dataStore.length;

}

function clear() {

    this.dataStore.length = 0;  // 通过把队列的长置0来清空队列

}

　　到此，队列这种数据结构借助javascript已经实现了。接下来测试一下。

队列的测试

　　测试代码：

const q = new Queue();

q.enqueue('java');

q.enqueue('php');

q.enqueue('python');

console.log('队列里的所有元素：');

console.log(q.toString());

q.dequeue()

console.log('出队之后所有元素：');

console.log(q.toString());

console.log('队首元素：' + q.front());

console.log('队尾元素：' + q.back());

console.log('队列长度：' + q.length());

q.clear();

console.log('清空队列后的长度：' + q.length());

　　输出结果：

　　输出结构符合预期。

优先队列

　　在一般情况下，从队列中删除的元素，一定是率先入队的元素。但有的特殊情况不用遵守先进先出的约定。比如急诊室里的队列，医生会根据病人病情的严重程度来决定服务的优先级。在这种队列里，从队列中删除的元素就有可能不是最先入队的元素。这种情况，就需要使用一个叫优先队列的数据结构来模拟。

　　接下来，我们以急诊室排队为例，实现以下优先队列。

　　在急诊室的候诊室里，分诊护士会评估患者病情的严重程度，然后给一个优先级代码，高优先级的患者先于低优先级的患者就医，同样优先级的患者按照先来先服务的顺序就医。

　　先来定义存储队列元素的对象，然后再构建我们的优先队列系统:

function Patient(name, code) {

    this.name = name;

    this.code = code;    // 优先级代码，整数，代表患者优先级

}

　　现在需要重新定义 dequeue() 方法，使其删除队列中拥有最高优先级的元素。我们规定优先码的值最小的元素优先级最高。新的 dequeue() 方法遍历队列的底层存储数组，从中找出优先码最小的元素，然后删除该元素。新的dequeque()方法定义如下所示：

function dequeue() {

    let priority = this.dataStore[0].code;

    let pos = 0;

    // 使用简单的顺序查找方法寻找优先级最高的元素

    this.dataStore.forEach((p, i) => {

        if (p.code < priority) {

            priority = p.code;

            pos = i;

        }

    });

    // 返回从队列中删除的元素

    return this.dataStore.splice(pos, 1);

}

　　最后，重新实现toString()方法来显示Patient对象。

function toString() {

    var retStr = "";

    this.dataStore.forEach(p => {

        retStr += `${p.name} 优先级： ${p.code}\n`;

    });

    return retStr;

}

　　到此，模拟的急诊优先队列已经实现完成，我们测试一下。

var p = new Patient("小一", 5);

const ed = new Queue();

ed.enqueue(p);

p = new Patient("小二", 4);

ed.enqueue(p);

p = new Patient("小三", 6);

ed.enqueue(p);

p = new Patient("小四", 1);

ed.enqueue(p);

p = new Patient("小五", 1);

console.log('正在排队的人：');

console.log(ed.toString());

// 第一轮

ed.enqueue(p);

var seen = ed.dequeue();

console.log('正在被接诊的病人：' + seen[0].name);

console.log('等待的人：')

console.log(ed.toString());

// 下一轮

var seen = ed.dequeue();

console.log('正在被接诊的病人：' + seen[0].name);

console.log('等待的人：')

console.log(ed.toString());

// 下一轮

var seen = ed.dequeue();

console.log('正在被接诊的病人：' + seen[0].name);

console.log('等待的人：')

console.log(ed.toString());

　　输入结果：

　　可以看到，待诊病人按照优先级，一个一个的从队列中被接诊。

巴特西

javascript数据结构——队列

定义队列的操作

队列的实现

队列的测试

优先队列

最新文章

热门文章