大した理由があるわけでもないのだけど、最近たまにJavascriptを触っている。いや、もちろん仕事などとは全く関係ない。趣味の話である。
その時に気づいたのだけど、どうやらJavascriptには、標準でキューが用意されていないらしい。正確には、Array.shift() などを用いればそれっぽい動作はできるのだが、内部動作的には配列を動かしているだけで、計算量も\(O(N)\)となり、きちんと実装されたキューとは言えないだろう。
キューが無いと、典型的なところでは、BFSを行おうとしたりする際に困る。というわけで、せっかくなので01-BFSなどで使用できるように、両端キューを実装してみることにした。
両端キューの実装方法にはいくつかあるが、ここでは配列を2つ用いた簡便な方法と、双方向リンクリストを用いた真面目な実装の二種類を作ってみた。
といっても、特に参考文献なども使用せず「こんな仕組みらしい」という聞きかじりからいきなり実装しているので、誤っていたり、効率の悪い実装などが入っている可能性がある。見つけたら、遠慮なくお知らせいただきたい。
// 配列を2つ使用しての両端キューの実装。
// どちらかの方向に偏るとそちら側の配列が際限なく伸びるので、
// 長期運用には使用しないほうがいい。
// でも、競技プログラミングならこれでいいでしょ……みたいな。
// 存在しない値を取得しようとすると、エラーではなく
// undefined を返すので注意。
class deque {
// コンストラクタ。
// 何も渡さなければ要素数 0 で初期化し、
// 配列を渡せばそれを用いて初期化する。
constructor(arr) {
this.dualArray = [[], []];
this.offset = 0;
this.length = 0;
if (arr instanceof Array && arr.length > 0) {
for (value of arr) {
this.push(value);
}
}
}
// 渡されたインデックスから、内部動作上のインデックスを返す関数。
// [1, x] なら右側の配列、[0, x] なら左側の配列とする。
getIndex(pos) {
if (pos + this.offset >= 0) {
return [1, pos + this.offset];
} else {
return [0, -(pos + this.offset)-1];
}
}
// value を右端に追加
push(value) {
let [lr, idx] = this.getIndex(this.length);
if (lr === 0) {
this.dualArray[lr][idx] = value;
this.length += 1;
} else {
this.dualArray[lr].push(value);
this.length += 1;
}
}
// value を左端に追加
pushLeft(value) {
let [lr, idx] = this.getIndex(-1);
if (lr === 0) {
this.dualArray[lr].push(value);
this.offset -= 1;
this.length += 1;
} else {
this.dualArray[lr][idx] = value;
this.offset -= 1;
this.length += 1;
}
}
// 右端の要素を削除し、値を返す
pop() {
if (this.length === 0) {
return undefined;
}
let [lr, idx] = this.getIndex(this.length-1);
if (lr === 0) {
this.length -= 1;
return this.dualArray[lr][idx];
} else {
this.length -= 1;
return this.dualArray[lr].pop();
}
}
// 左端の要素を削除し、値を返す
popLeft() {
if (this.length === 0) {
return undefined;
}
let [lr, idx] = this.getIndex(0);
if (lr === 0) {
this.offset += 1;
this.length -= 1;
return this.dualArray[lr].pop();
} else {
this.offset += 1;
this.length -= 1;
return this.dualArray[lr][idx]
}
}
// 指定したインデックスの値を取得する。
get (pos) {
if (pos < 0) {
pos = this.length + pos;
}
if (pos < 0 || this.length <= pos) {
return undefined;
}
let[lr, idx] = this.getIndex(pos);
return this.dualArray[lr][idx];
}
}// 双方向連結リストによる、両端キューの実装。
// 学習の一環として作成。
// 実際のところ早くない……が、長期運用にも耐える構造のはず。
// 存在しない値を取得しようとすると、エラーではなく undefined を
// 返すので注意。
// 両端キュー用ノードのクラス
class dequeNode {
constructor(value) {
this.left = null;
this.right = null;
this.value = value;
}
}
class deque {
// コンストラクタ。
// 何も渡さなければ、要素数 0 にて初期化のみ行い、
// Array を渡せば、それを用いて初期化する。
constructor(arr) {
this.root = new dequeNode(null);
this.root.left = this.root;
this.root.right = this.root;
this.length = 0;
if (arr instanceof Array && arr.length > 0) {
for (let value of arr) {
this.push(value);
}
}
}
// 参照ノードの左側に値を追加し、追加した要素の参照を返す
insertLeft(ref, value) {
if (!ref instanceof dequeNode) {
return undefined;
} else {
const obj = new dequeNode(value);
ref.left.right = obj;
obj.left = ref.left;
ref.left = obj;
obj.right = ref;
this.length += 1;
return obj;
}
}
// 参照ノードの右側に値を追加し、追加した要素の参照を返す
insertRight(ref, value) {
if (!ref instanceof dequeNode) {
return undefined;
} else {
const obj = new dequeNode(value);
ref.right.left = obj;
obj.right = ref.right;
ref.right = obj;
obj.left = ref;
this.length += 1;
return obj;
}
}
// 右端に値を追加し、追加した要素の参照を返す
push(value) {
return this.insertLeft(this.root, value);
}
// 左端に値を追加し、追加した要素の参照を返す
pushLeft(value) {
return this.insertRight(this.root, value);
}
// 参照ノードを削除し、その値を返す
pop_ref(ref) {
if (ref === this.root) {
return undefined;
} else {
ref.right.left = ref.left;
ref.left.right = ref.right;
this.length -= 1;
return ref.value;
}
}
// 右端の要素を削除し、その値を返す
pop() {
if (this.length === 0) {
return undefined;
} else {
const ref = this.root.left;
return this.pop_ref(ref);
}
}
// 左端の要素を削除し、その値を返す
popLeft() {
if (this.length === 0) {
return undefined;
} else {
const ref = this.root.right;
return this.pop_ref(ref);
}
}
// 左から pos-1 番目の値を取得する
get(pos) {
if (pos < 0) {
pos = this.length + pos;
}
if (pos >= this.length) {
return undefined;
}
// 一応近い方から数えるように……。
if (pos < this.length / 2) {
let nd = this.root.right;
for (let i = 0; i < pos; i++) {
nd = nd.right;
}
return nd.value;
} else {
let nd = this.root.left;
for (let i = 0; i < this.length - pos - 1; i++) {
nd = nd.left;
}
return nd.value;
}
}
}