本文共 3185 字，大约阅读时间需要 10 分钟。

队列的实现

// 队列类function Deque () {    this.dataStore = [];    this.enqueueFront = enqueueFront;    this.enqueueBack = enqueueBack;    this.dequeueFront = dequeueFront;    this.dequeueBack = dequeueBack;    this.front = front;    this.back = back;    this.toString = toString;    this.empty = empty;}// 入队 - 队首function enqueueFront (element) {    this.dataStore.unshift(element);}// 出队 - 队首function dequeueFront () {    return this.dataStore.shift();}// 入队 - 队尾function enqueueBack (element) {    this.dataStore.push(element);}// 出队 - 队尾function dequeueBack (element) {    return this.dataStore.pop(element);}// 读取队首的元素function front () {    return this.dataStore[0];}// 读取队尾的元素function back () {    return this.dataStore[this.dataStore.length - 1];}// 显示队列内所有元素function toString () {    let retStr = ``;    for (let 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;    }}

练习

一. 修改Queue类，形成一个Deque类。这是一个和队列类似的数据结构，允许从队列两端添加和删除元素，因此也叫双向队列。写一段测试程序测试该类。

// 双向队列类function Deque () {    this.dataStore = [];    this.enqueueFront = enqueueFront;    this.enqueueBack = enqueueBack;    this.dequeueFront = dequeueFront;    this.dequeueBack = dequeueBack;    this.front = front;    this.back = back;    this.toString = toString;    this.empty = empty;}// 入队 - 队首function enqueueFront (element) {    this.dataStore.unshift(element);}// 出队 - 队首function dequeueFront () {    return this.dataStore.shift();}// 入队 - 队尾function enqueueBack (element) {    this.dataStore.push(element);}// 出队 - 队尾function dequeueBack (element) {    return this.dataStore.pop(element);}// 读取队首的元素function front () {    return this.dataStore[0];}// 读取队尾的元素function back () {    return this.dataStore[this.dataStore.length - 1];}// 显示队列内所有元素function toString () {    let retStr = ``;    for (let 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;    }}// 测试let d = new Deque();d.enqueueFront(`a`);d.enqueueFront(`b`);d.enqueueFront(`c`);d.enqueueFront(`d`);d.enqueueFront(`e`);console.log(d.dataStore); // ["e", "d", "c", "b", "a"]d.enqueueBack(`a`);d.enqueueBack(`b`);d.enqueueBack(`c`);d.enqueueBack(`d`);d.enqueueBack(`e`);console.log(d.dataStore); // ["e", "d", "c", "b", "a", "a", "b", "c", "d", "e"]d.dequeueFront();d.dequeueFront();console.log(d.dataStore); // ["c", "b", "a", "a", "b", "c", "d", "e"]d.dequeueBack();d.dequeueBack();d.dequeueBack();console.log(d.dataStore); // ["c", "b", "a", "a", "b"]

二. 使用前面完成的Deque类来判断一个给定单词是否为回文。

function isPalindrom (word) {    let d = new Deque();    let max = word.length;    for (let i = 0; i < max; ++i) {        d.enqueueBack(word[i]);    }    while (d.dataStore.length > 1) {        if (d.dequeueFront() !== d.dequeueBack()) {            return false;        }    }    return true;}// 示例console.log(isPalindrom(`racecar`)); // trueconsole.log(isPalindrom(`ada`)); // trueconsole.log(isPalindrom(`mazey`)); // false