队列的实现
// 队列类
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`)); // true
console.log(isPalindrom(`ada`)); // true
console.log(isPalindrom(`mazey`)); // false
