Stack 栈
var Stack = function(){
var items = []
//私有属性，禁止直接外部访问，只能调用接口
// push 栈顶添加元素
this.push = function(element){
items.push(element)
}
// pop 移除栈顶元素
this.pop = function(){
return items.pop()
}
// peek 检查栈顶
this.peek = function(){
return items[items.length - 1]
}
// 检查栈 是否为空
this.isEmpty = function(){
return items.length == 0
}
// 清除栈
this.clear = function(){
items = []
}
// 获取栈的大小
this.length = function(){
return items.length
}
// 检查items
this.getItems = function(){
return items
}
}
Queue 队列
var Queue = function(){
var items = []
//入队
this.enqueue = function(element){
items.push(element)
}
// 出队
this.dequeue = function(){
return items.shift()
}
//查看队列头
this.front = function(){
return items[0]
}
//检查队列是否为空
this.isEmpty = function(){
return items.length === 0
}
//队列大小
this.size = function(){
return items.length
}
}
PriorityQueue 优先队列
var PriorityQueue = function(){
var items = []
// 数据+优先级
var QueueItem = function(element,priority){
this.element = element
this.priority = priority
}
this.enqueue = function(element,priority){
var queueItem = new QueueItem(element,priority)
var added = false
for(var i = 0 ; i < items.length ; i++){
if(queueItem.priority > items[i].priority){
items.splice(i,0,queueItem)
added = true
break
}
}
if(!added){
items.push(queueItem)
}
}
this.getItems = function(){
return items
}
}
Set 集合
- 我写的和网上其他方法不一样，
- ES6的Set支持去重，并防止对象转化成为[object Obeject]
function mySet() {
var set = [];
// this.set = set;
//制作函数时方便检查用的
//避免暴露给用户
this.add = function (item) {
if (!this.has(item)) {
console.log(item)
set.push([item])
}
}
this.has = function (item) {
for (var i = 0; i < set.length; i++) {
if (set[i][0] === item) {
return true;
}
}
return false;
}
this.get = function (item) {
var arr = [];
for (var i = 0; i < set.length; i++) {
arr.push(set[i][0])
}
return arr;
}
this.size = function (item) {
return set.length;
}
this.clear = function () {
items = [];
return true
}
if (arguments) {
for (var i = 0; i < arguments[0].length; i++) {
this.add(arguments[0][i])
}
}
}
// 测试
var obj = { name: 'obj' }
var oSet = new mySet([1, 2, obj,{}]);
oSet.add(function () { });
oSet.add({ name: "lyz" });
oSet.add(obj);
console.log(oSet);
Map 字典
class myMap {
constructor() {
//初始化桶
this.bucket = new Array(8);
for (var i = 0; i < this.bucket.length; i++) {
this.bucket[i] = {
type: 'bucket_' + i,
next: null
}
}
}
makeHash(key) {
// 根据类型产生哈希
var hash = 0;
if (typeof key !== 'string') {
if (typeof key === 'number') {
hash = Object.is(NaN, key) ? 0 : key;
} else if (typeof key == 'object') {
hash = 0;
} else if (typeof key == 'boolean') {
hash = +key;
} else {
//function undefined symbol()
hash = 8;
}
} else {
//如果是string
for (var i = key.length - 1; i > key.length - 4; i--) {
if (key[i]) {
hash += key[i].charCodeAt(0)
}
}
}
hash = hash % 8;
console.log(hash)
return hash;
}
get(key) {
let hash = this.makeHash(key);
//游标 桶
var oTempBucket = this.bucket[hash];
while (oTempBucket) {
if (oTempBucket.next.key == key) {
//如果已经存在
return oTempBucket.next.value
}
oTempBucket = oTempBucket.next;
}
}
set(key, value) {
let hash = this.makeHash(key);
var oTempBucket = this.bucket[hash];
while (oTempBucket.next) {
//查找
if (oTempBucket.next.key == key) {
//如果已经存在
oTempBucket.next.key == key
} else {
//如果不存在， 临时桶的next为空，下一步跳出循环
oTempBucket = oTempBucket.next;
}
}
//对空桶初始化赋值
oTempBucket.next = {
key,
value,
next: null
}
}
has(key) {
let hash = this.makeHash(key);
//游标桶
var oTempBucket = this.bucket[hash];
while (oTempBucket) {
if (oTempBucket.next && oTempBucket.next.key == key) {
//如果已经存在
return true
}
oTempBucket = oTempBucket.next;
}
return false;
}
delete(key) {
let hash = this.makeHash(key);
//游标桶
var oTempBucket = this.bucket[hash];
while (oTempBucket.next) {
// 判断下一个的key是否是
if (oTempBucket.next.key == key) {
console.log(oTempBucket, oTempBucket.next.next)
//当前的这个denext等于下一个的下一个
oTempBucket.next = oTempBucket.next.next;
return true;
}
oTempBucket = oTempBucket.next;
}
return false;
}
clear() {
this.bucket = new Array(8);
for (var i = 0; i < this.bucket.length; i++) {
this.bucket[i] = {
type: 'bucket_' + i,
next: null
}
}
}
}
二叉树
图
