数据结构

1.栈

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。在现实生活中也能发现很多栈的例子。例如，下图里的一摞书或者餐厅里堆放的盘子。栈也被用在编程语言的编译器和内存中保存变量、方法调用等。

实现栈之后，我们来看一看完整的代码：

function Stack() {
    var items = [];
    this.push = function (element) {
        items.push(element);
    };
    this.pop = function () {
        return items.pop();
    };
    this.peek = function () {
        return items[items.length - 1];
    };
    this.isEmpty = function () {
        return items.length == 0;
    };
    this.size = function () {
        return items.length;
    };
    this.clear = function () {
        items = [];
    };
    this.print = function () {
        console.log(items.toString());
    };
}

2.队列

队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在现实中，最常见的队列的例子就是排队：

还有，在电影院、自助餐厅、杂货店收银台，我们也都会排队。排在第一位的人会先接受服务。

普通队列

function Queue() {
    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.clear = function () {
        items = [];
    };
    this.size = function () {
        return items.length;
    };
 
    this.print = function () {
        console.log(items.toString());
    };
}

在计算机科学中，一个常见的例子就是打印队列。比如说我们需要打印五份文档。我们会打开每个文档，然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印，以此类推，直到打印完所有文档。

Queue类和Stack类非常类似。唯一的区别是dequeue方法和front方法，这是由于先进先出和后进先出原则的不同所造成的。

优先队列

循环队列

散列表

散列算法的作用是尽可能快地在数据结构中找到一个值。 1.散列表类似hash数组。但是散列表的键是将每个键值中的每个字母的ASCII值相加

散列表

散列集合

和集合相似，散列集合只存储唯一的不重复的值
解决散列表中的冲突问题，方法有分离链(借助于链表)、线性探查(简单的说就是遇到冲突hashCode就累加+1，直到没有冲突出现)、双向链表

“lose lose”散列函数

var loseloseHashCode = function (key) {
 var hash = 0; //{1}
 for (var i = 0; i < key.length; i++) { //{2}
 hash += key.charCodeAt(i); //{3}
 }
 return hash % 37; //{4}
};

给定一个key参数，我们就能根据组成key的每个字符的ASCII码值的和得到一个数字。所以，首先需要一个变量来存储这个总和（行{1}）。然后，遍历key（行{2}）并将从ASCII表中查到的每个字符对应的ASCII值加到hash变量中（可以使用JavaScript的String类中的charCodeAt 方法——行{3}）。最后，返回hash值。为了得到比较小的数值，我们会使用hash值和一个任意数做除法的余数（mod）。

比“lose lose”更好的散列函数是djb2

我们实现的“lose lose”散列函数并不是一个表现良好的散列函数，因为它会产生太多的冲突。如果我们使用这个函数的话，会产生各种各样的冲突。一个表现良好的散列函数是由几个方面构成的：插入和检索元素的时间（即性能），当然也包括较低的冲突可能性。我们可以在网上找到一些不同的实现方法，或者也可以实现自己的散列函数。另一个可以实现的比“lose lose”更好的散列函数是djb2：

var djb2HashCode = function (key) {
 var hash = 5381; //{1}
 for (var i = 0; i < key.length; i++) { //{2}
 hash = hash * 33 + key.charCodeAt(i); //{3}
 }
 return hash % 1013; //{4}
};

它包括初始化一个hash变量并赋值为一个质数（行{1}——大多数实现都使用5381），然后迭代参数key（行{2}），将hash与33相乘（用来当作一个魔力数），并和当前迭代到的字符的ASCII 码值相加（行{3}）。最后，我们将使用相加的和与另一个随机质数（比我们认为的散列表的大小要大——在本例中，我们认为散列表的大小为1000）相除的余数。

二叉树

对于寻找最小值，总是沿着树的左边；而对于寻找最大值，总是沿着树的右边。

this.min = function() {
 return minNode(root); //{1}
}; 
var minNode = function (node) {
 if (node){
 while (node && node.left !== null) { //{2}
 node = node.left; //{3}
 }
 return node.key;
 }
 return null; //{4}
}; 

this.max = function() {
 return maxNode(root);
};
var maxNode = function (node) {
 if (node){
 while (node && node.right !== null) { //{5}
 node = node.right;
 }
 return node.key;
 }
 return null;
};

1.栈

2.队列

普通队列

优先队列

循环队列

散列表

散列集合

二叉树

FEATURED TAGS

FRIENDS