JavaScriptによるコーディングテスト中のデータ構造

一、ハッシュテーブル

1.配列Array

const arr = [1, 2, 3]

2.集合Set

const set = new Set([1, 2, 3]);

3.写像Map

const map = new Map([
  ['name', 'tom'],
  ['title', 'Author']
]);

二、スタック

function Stack(){
    // スタック
    this.items = [];
    // 追加
    Stack.prototype.push = function(element){
       this.items.push(element);
    }
    // 削除
    Stack.prototype.pop = function(){
        return this.items.pop();
    }
    // 取得
    Stack.prototype.peek = function(){
        return this.items[this.items.length-1];
    }
}

// 使用
const stack = new Stack();

三、キュー

function Queue() {
	// キュー
	this.dataStore = [];
	// 追加
	Queue.prototype.enqueue = function (element) {
		this.dataStore.push(element);
	};
	// 削除
	Queue.prototype.dequeue = function () {
		this.dataStore.shift();
	};
	// 取得
	Queue.prototype.theFront = function () {
		return this.dataStore[0];
	};
}

// 使用
const queue = new Queue();

四、連結リスト

配列→連結リスト

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

const makeList = (protoArr) => {
  let list = new ListNode(protoArr[0]);
  let pre = list;
  for (let i = 1; i < protoArr.length; i++) {
    pre.next = new ListNode(protoArr[i]);
    pre = pre.next;
  }
  return list;
};

// 使用
const list = makeList([1, 2, 3, 4, 5, 6])

五、二分木

配列→二分木

function TreeNode(val, left, right) {
	this.val = val === undefined ? 0 : val;
	this.left = left === undefined ? null : left;
	this.right = right === undefined ? null : right;
}

const tree = (arr) => {
	if (!arr || arr.length === 0) return null;

	let root = new TreeNode(arr.shift());
	let nodeQueue = [root];

	while (arr.length > 0) {
		let node = nodeQueue.shift();
		if (arr.length === 0 || node === undefined) break;
    
		const leftArr = arr.shift();
		if (leftArr !== null) {
			let left = new TreeNode(leftArr);
			node.left = left;
			nodeQueue.push(left);
		}


		if (arr.length === 0) break;

		const rightArr = arr.shift();
		if (rightArr !== null) {
			let right = new TreeNode(rightArr);
			node.right = right;
			nodeQueue.push(right);
		}
	}

	return root;
};

// 使用
tree([1, 2, 3, 4, 5, 6, 7, 8, 9])