数据结构
什么是数据结构? 数据结构就是在计算机中,存储和组织数据的方式。 例如:图书管理,怎样摆放图书才能既能放很多书,也方便取? 主要需要考虑两个问题: 操作一:新书怎么插入? 操作二:怎么找到某本指定的书?
JavaScript
什么是数据结构?
数据结构就是在计算机中,存储和组织数据的方式。
例如:图书管理,怎样摆放图书才能既能放很多书,也方便取?
主要需要考虑两个问题:
- 操作一:新书怎么插入?
- 操作二:怎么找到某本指定的书?
常见的数据结构:
- 数组(Aarray)
- 栈(Stack)
- 链表(Linked List)
- 图(Graph)
- 散列表(Hash)
- 散列表(Hash)
- 树(Tree)
- 堆(Heap)
注意:数据结构与算法与语言无关,常见的编程语言都有直接或间接的使用上述常见的数据结构。
什么是算法?
算法(Algorithm)的定义
- 一个有限指令集,每条指令的描述不依赖于语言;
- 接收一些输入(有些情况下不需要输入);
- 产生输入;
- 一定在有限步骤之后终止;
算法通俗理解:解决问题的办法/步骤逻辑。数据结构的实现,离不开算法。
栈结构(Stack)
简介
数组是一个线性结构,并且可以在数组的任意位置插入和删除元素。而栈和队列就是比较常见的受限的线性结构。如下图所示:

栈的特点为先进后出,后进先出(LIFO:last in first out)。
程序中的栈结构:
函数调用栈:A(B(C(D()))):
-
函数调用栈:A(B(C(D()))):即A函数中调用B,B调用C,C调用D;在A执行的过程中会将A压入栈,随后B执行时B也被压入栈,函数C和D执行时也会被压入栈。所以当前栈的顺序为:A->B->C->D(栈顶);函数D执行完之后,会弹出栈被释放,弹出栈的顺序为D->C->B->A;
-
递归:为什么没有停止条件的递归会造成栈溢出?比如函数A为递归函数,不断地调用自己(因为函数还没有执行完,不会把函数弹出栈),不停地把相同的函数A压入栈,最后造成栈溢出(Stack Overfloat)
练习:题目:有6个元素6,5,4,3,2,1按顺序进栈,问下列哪一个不是合法的出栈顺序?
- A:5 4 3 6 1 2 (√)
- B:4 5 3 2 1 6 (√)
- C:3 4 6 5 2 1 (×)
- D:2 3 4 1 5 6 (√)
题目所说的按顺序进栈指的不是一次性全部进栈,而是有进有出,进栈顺序为6 -> 5 -> 4 -> 3 -> 2 -> 1。
解析:
- A答案:65进栈,5出栈,4进栈出栈,3进栈出栈,6出栈,21进栈,1出栈,2出栈(整体入栈顺序符合654321);
- B答案:654进栈,4出栈,5出栈,3进栈出栈,2进栈出栈,1进栈出栈,6出栈(整体的入栈顺序符合654321);
- C答案:6543进栈,3出栈,4出栈,之后应该5出栈而不是6,所以错误;
- D答案:65432进栈,2出栈,3出栈,4出栈,1进栈出栈,5出栈,6出栈。符合入栈顺序;
栈常见的操作:
-
push(element):添加一个新元素到栈顶位置;
-
pop():移除栈顶的元素,同时返回被移除的元素;
-
peek():返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)
-
isEmpty():如果栈里没有任何元素就返回true,否则返回false;
-
size():返回栈里的元素个数。这个方法和数组的length属性类似;
-
toString():将栈结构的内容以字符串的形式返回。
代码封装
javascript
// 封装栈类
function Stack() {
// 栈中的属性
this.stack = [];
/*
栈的相关操作
1.push():将元素压入栈
方式一(不推荐):给对象添加方法,其他对象不能复用
this.push = () => {}
方式二(推荐):给Stack类添加方法,能够多对象复用
*/
//push方法入栈
Stack.prototype.push=function(element) {
// 利用数组的push方法实现Stack的入栈
this.stack.push(element);
}
// 2. pop方法出栈
Stack.prototype.pop = function() {
// 利用数组的pop方法实现Stack出栈
return this.stack.pop();;
}
// 3.peek方法查看一个栈顶元素
Stack.prototype.peek = function() {
//数组的最后一个元素即为栈顶元素
return this.stack[this.stack.length - 1];
}
// 4.isEmpty方法判断栈空
Stack.prototype.isEmpty = function() {
// 计算数组元素是否为0
return this.stack.length==0;
}
// 5.size方法获取栈中的元素个数
Stack.prototype.size = function () {
//计算元素长度
return this.stack.length;
}
// 6. tostring方法以字符串形式输出栈内数据
Stack.prototype.toString = function() {
//希望输出的形式:20 10 12 8 7
var resultString = '';
//通过for of 拿到数组中的元素
//与for in 的区别是,in只是所引,而 of是值
for (let item of this.stack) {
//加上一个空字符串,结果是一个字符串形式
resultString +=item+' ';
}
return resultString;
}
}
测试结果
javascript
// 栈的使用
// 实例化封装的栈类(构造函数)
let st = new Stack();
// 入栈
st.push(20);
st.push(30);
st.push(40);
st.push(50);
console.log(st) // [20, 30, 40, 50]
// 出栈
let popResult = st.pop();
console.log(popResult);//50
// 栈顶元素
console.log(st.peek())//40---上面已经出栈50,所以现在栈顶元素是40
// 判空
console.log(st.isEmpty()) // false
// 计算长度
console.log(st.size()) // 3
// 字符串形式输出栈元素
console.log(st.toString()) //20 30 40
栈结构的简单应用:
利用栈结构的特点封装十进至转换为二进至的函数:
javascript
//简单应用:
//封装函数:将十进制转成二进制(十转二的运算最后倒叙取余的特点符合栈'先进后出')
let dec2bin = (decNumber)=>{
// 实例化栈对象
var stack = new Stack();
// 循环操作
while (decNumber > 0) {
// 获取余数并放进栈中
stack.push(decNumber%2);
// 获取整除后的结果作为下一次运算的数字(floor:向下取整)
decNumber = Math.floor(decNumber / 2)
}
// 从栈中取0和1
let binaryString = '';
//直到出栈完成
while (stack.size() > 0) {
binaryString += stack.pop();
}
return binaryString;
}
//测试
console.log(dec2bin(10)) // 1010
console.log(dec2bin(100)) // 1100100
console.log(dec2bin(1000)) // 1111101000
队列结构(Queue)
队列简介
队列是是一种受限的线性表,特点为先进先出(FIFO:first in first out)。
-
受限之处在于它只允许在表的头部(front)进行删除操作;
-
在表的尾部(rear)进行插入操作;

队列的应用:
-
打印队列:计算机打印多个文件的时候,需要排队打印;
-
线程队列:开启多线程时,当新开启的线程所需的资源不足时就先放入线程队列,等待CPU处理;
队列类的实现:
队列的实现和栈一样,有两种方案:
-
基于数组实现;
-
基于链表实现;
队列的常见操作:
-
enqueue(element):向队列尾部添加一个(或多个)新的项;
-
dequeue():移除队列的第一(即排在队列最前面的)项,并返回被移除的元素;
-
front():返回队列中的第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息与Stack类的peek方法非常类似);
-
isEmpty():如果队列中不包含任何元素,返回true,否则返回false;
-
size():返回队列包含的元素个数,与数组的length属性类似;
-
toString():将队列中的内容,转成字符串形式;
封装队列类
javascript
//封装队列类
function Queue() {
// 队列属性
this.queue = [];
// 方法
// 1.enqueue():将元素加入到队列中
Queue.prototype.enqueue=element=>{
//入队
this.queue.push(element);
}
// 2.dequeue():从队列中删除前端元素
Queue.prototype.dequeue = () => {
return this.queue.shift();
}
// 3.front():查看前端的元素
Queue.prototype.front = () => {
//获取第一个元素即为队首元素
return this.queue[0]
}
// 4.isEmpty:查看队列是否为空
Queue.prototype.isEmpty = () => {
// 判断长度是否为0
return this.queue.length == 0;
}
// 5.size():查看队列中元素的个数
Queue.prototype.size = () => {
//获取长度
return this.queue.length
}
// 6.toString():将队列中元素以字符串形式输出
Queue.prototype.toString = () => {
let resultString = ''
//使用join方法
resultString = this.queue.join(' ')
//for of方法
// for (let item of this.queue){
// resultString += item + ' '
// }
return resultString
}
}
测试结果
javascript
// 测试
// 是实例化队列
let queue = new Queue();
// 将元素加入到队列中
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
console.log(queue); // ['a', 'b', 'c', 'd']
// 从队列中删除元素
queue.dequeue()
console.log(queue);// ['b', 'c', 'd']
queue.dequeue()
console.log(queue); // ['c', 'd']
//查看队首(front)
console.log(queue.front());//c
//判空
console.log(queue.isEmpty()); // false
//长度
console.log(queue.size());// 2
//字符串形式输入队列元素
console.log(queue.toString()); c d
队列的应用
使用队列实现小游戏:击鼓传花,传入一组数据和设定的数字num,循环遍历数组内元素,遍历到的元素为指定数字num时将该元素删除,直至数组剩下一个元素。
javascript
// 队列应用:面试题:击鼓传花
let passGame = (NameList,num)=>{
// 实例化队列结果
let queue= new Queue();
//2.将所有人依次加入队列
// 这是ES6的for循环写法,i相当于nameList[i]
for(let item of NameList){
queue.enqueue(item);
}
// 3.开始数数
// 队列中只剩1个人就停止数数
while (queue.size()>1){
// 不是num的时候,重新加入队列末尾
// 是num的时候,将其从队列中删除
// num数字之前的人重新放入队列的末尾(把队列前面删除的加到队列最后)
for(let i =0;i<num-1;i++){
// 先出对再入队
queue.enqueue(queue.dequeue());
}
// num对应这个人,直接从队列中删除
/*
思路是这样的,由于队列没有像数组一样的下标值不能直接取到某一元素,所以采用,
把num前面的num-1个元素先删除后添加到队列末尾,这样第num个元素就排到了队列的最前面,可以直接使用dequeue方法进行删除
*/
queue.dequeue();
}
//获取剩下的那个人
console.log(queue.size());
let endName = queue.front();
console.log('最终剩下的人:' + endName);
return NameList.indexOf(endName);
}
// 测试击鼓传花
let names = ['lily', 'lucy', 'Tom', 'Lilei', 'Tony']
console.log(passGame(names, 3));
优先队列
优先级队列主要考虑的问题为:
- 每个元素不再只是一个数据,还包含数据的优先级;
- 在添加数据过程中,根据优先级放入到正确位置;
javascript
// 封装优先级队列
function PriorityQueue() {
//内部类:在类里面再封装一个类;表示带优先级的数据
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
// 封装属性
this.items = []
// 1.实现按照优先级插入方法
PriorityQueue.prototype.enqueue = (element, priority) => {
// 1.1.创建QueueElement对象
let queueElement = new QueueElement(element, priority)
// 1.2.判断队列是否为空
if(this.items.length == 0){
this.items.push(queueElement)
}else{
// 定义一个变量记录是否成功添加了新元素
let added = false
for(let i of this.items){
// 让新插入的元素与原有元素进行优先级比较(priority越小,优先级越大)
if(queueElement.priority < i.priority){
// 从元素i开始,删除0个元素,添加queueElement元素,
this.items.splice(i, 0, queueElement)
added = true
// 新元素已经找到插入位置了可以使用break停止循环
break
}
}
// 新元素没有成功插入,就把它放在队列的最前面
if(!added){
this.items.push(queueElement)
}
}
}
// 2.dequeue():从队列中删除前端元素
PriorityQueue.prototype.dequeue = () => {
return this.items.shift()
}
// 3.front():查看前端的元素
PriorityQueue.prototype.front = () => {
return this.items[0]
}
// 4.isEmpty():查看队列是否为空
PriorityQueue.prototype.isEmpty = () => {
return this.items.length == 0;
}
// 5.size():查看队列中元素的个数
PriorityQueue.prototype.size = () => {
return this.items.length
}
// 6.toString():以字符串形式输出队列中的元素
PriorityQueue.prototype.toString = () => {
let resultString = ''
for (let i of this.items){
resultString += i.element + '-' + i.priority + ' '
}
return resultString
}
}
测试结果
javascript
// 测试代码
let pq = new PriorityQueue();
pq.enqueue('Tom',111);
pq.enqueue('Hellen',200);
pq.enqueue('Mary',30);
pq.enqueue('Gogo',27);
// 打印修改过后的优先队列对象
console.log(pq);

关于数组方法splice用法:
-
splice(1,0,'Tom'):表示在索引为1的元素前面插入元素’Tom‘(也可以理解为从索引为1的元素开始删除,删除0个元素,再在索引为1的元素前面添加元素'Tom');
-
splice(1,1,'Tom'):表示从索引为1的元素开始删除(包括索引为1的元素),共删除1个元素,并添加元素'Tom'。即把索引为1的元素替换为元素'Tom'。
数组的push方法在数组、栈和队列中的形式:
-
数组:在数组[0,1,2]中,push(3),结果为[0,1,2,3];
-
栈:执行push(0),push(1),push(2),push(3),从栈底到栈顶的元素分别为:0,1,2,3;如果看成数组,可写为[0,1,2,3],但是索引为3的元素3其实是栈顶元素;所以说栈的push方法是向栈顶添加元素(但在数组的视角下为向数组尾部添加元素);
-
队列:enqueue方法可以由数组的push方法实现,与数组相同,相当于在数组尾部添加元素。

集合与字典
集合结构
简介
集合比较常见的实现方式是哈希表,这里使用JavaScript的Object类进行封装。
集合通常是由一组无序的、不能重复的元素构成。
- 数学中常指的集合中的元素是可以重复的,但是计算机中集合的元素不能重复。
集合是特殊的数组:
-
特殊之处在于里面的元素没有顺序,也不能重复。
-
没有顺序意味着不能通过下标值进行访问,不能重复意味着相同的对象在集合中只会存在一份。
实现集合类:
-
在ES6中的Set类就是一个集合类,这里我们重新封装一个Set类,了解集合的底层实现。
-
JavaScript中的Object类中的key就是一个集合,可以使用它来封装集合类Set。
集合常见的操作:
-
add(value):向集合添加一个新的项; -
remove(value):从集合中移除一个值; -
has(value):如果值在集合中,返回true,否则返回false; -
clear():移除集合中的所有项; -
size():返回集合所包含元素的数量,与数组的length属性相似; -
values():返回一个包含集合中所有值的数组;
封装set类
javascript
// 封装集合类
function Set() {
// 属性
this.items = {};
// 1.has方法
Set.prototype.has = value=>{
return this.items.hasOwnProperty(value);
}
// 2.add方法
Set.prototype.add=value=>{
// 判断集合中是否已经包含该元素
// 通过调用自身的has方法进行判断,值得注意的是这里this指向的是当前对象(函数)
if (this.has(value)){
return false;
}
//将元素添加到集合中
this.items[value]=value //表示该属性键和值都为value
return true;//添加成功
}
// 3.remove方法
Set.prototype.remove=key=>{
// 判断集合中是否包含该元素
if(!this.has(key)){
return false;
}
// 将元素从属性中删除
delete this.items[key];
return true; //删除成功
}
// 4.clear方法
Set.prototype.clear=()=>{
//原来的对象没有引用指向,会被自动回收
this.items = {};
}
// 5.size方法
Set.prototype.size=()=>{
//拿到items里面全部的KEY,然后计算长度
return Object.keys(this.items).length;
}
// 获取集合中所有的值
// 6.values方法
Set.prototype.values = () => {
return Object.keys(this.items)
}
}
测试结果
javascript
//测试集合类
//1.创建Set类对象
let set = new Set()
//添加元素
//2.测试add方法
console.log(set.add('a')); // true //67
console.log(set.add('a')); // false
console.log(set.add('b')); // true //69
console.log(set.add('c')); // true //70
console.log(set.add('d')); // true
//3.测试values方法
console.log(set.values()); // ['a', 'b', 'c', 'd']
//删除元素
//4.测试remove方法
console.log(set.remove('a')); // true //78
console.log(set.remove('a')); // false //79
console.log(set.values()); // ['b', 'c', 'd']
//5.测试has方法
console.log(set.has('b')); // true
//6.测试size方法和clear方法
console.log(set.size());// 3 //86
set.clear()
// 由于clear方法的实现原理为指向另外一个空对象,所以不影响原来的对象
console.log(set.size()); // 0 //89
console.log(set.values()); //[]
字典结构
简介
字典的特点:
-
字典存储的是键值对,主要特点是一一对应;
-
比如保存一个人的信息:数组形式:[19,‘Tom’,1.65],可通过下标值取出信息;字典形式:{"age":19,"name":"Tom","height":165},可以通过key取出value。
-
此外,在字典中key是不能重复且无序的,而Value可以重复。
字典和映射的关系:
-
有些编程语言中称这种映射关系为字典,如Swift中的Dictonary,Python中的dict;
-
有些编程语言中称这种映射关系为Map,比如Java中的HashMap&TreeMap等;
字典类常见的操作:
-
set(key,value):向字典中添加新元素。
-
remove(key):通过使用键值来从字典中移除键值对应的数据值。
-
has(key):如果某个键值存在于这个字典中,则返回
true,反之则返回false。 -
get(key):通过键值查找特定的数值并返回。
-
clear():将这个字典中的所有元素全部删除。
-
size():返回字典所包含元素的数量。与数组的
length属性类似。 -
keys():将字典所包含的所有键名以数组形式返回。
-
values():将字典所包含的所有数值以数组形式返回。
封装字典
JavaScript
//封装字典类
function Dictionary(){
//字典属性
this.items = {}
//字典操作方法
//一.在字典中添加键值对
Dictionary.prototype.set = function(key, value){
this.items[key] = value
}
//二.判断字典中是否有某个key
Dictionary.prototype.has = function(key){
return this.items.hasOwnProperty(key)
}
//三.从字典中移除元素
Dictionary.prototype.remove = function(key){
//1.判断字典中是否有这个key
if(!this.has(key)) return false
//2.从字典中删除key
delete this.items[key]
return true
}
//四.根据key获取value
Dictionary.prototype.get = function(key){
return this.has(key) ? this.items[key] : undefined
}
//五.获取所有keys
Dictionary.prototype.keys = function(){
return Object.keys(this.items)
}
//六.size方法
Dictionary.prototype.keys = function(){
return this.keys().length
}
//七.clear方法
Dictionary.prototype.clear = function(){
this.items = {}
}
}
哈希表
简介
哈希表通常是基于数组实现的,但是相对于数组,它存在更多优势:
-
哈希表可以提供非常快速的插入-删除-查找操作;
-
无论多少数据,插入和删除值都只需要非常短的时间,即O(1)的时间级。实际上,只需要几个机器指令即可完成;
-
哈希表的速度比树还要快,基本可以瞬间查找到想要的元素。但是相对于树来说编码要简单得多。
哈希表同样存在不足之处:
-
哈希表中的数据是没有顺序的,所以不能以一种固定的方式(比如从小到大 )来遍历其中的元素。
-
通常情况下,哈希表中的key是不允许重复的,不能放置相同的key,用于保存不同的元素。
哈希表是什么?
-
哈希表是一种根据关键码去寻找值的数据映射结构,该结构通过把关键码映射的位置去寻找存放值的地方
-
哈希表并不好理解,不像数组、链表和树等可通过图形的形式表示其结构和原理。
-
哈希表的结构就是数组,但它神奇之处在于对下标值的一种变换,这种变换我们可以称之为哈希函数,通过哈希函数可以获取HashCode。
通过以下案例了解哈希表:
-
案例一:公司想要存储1000个人的信息,每一个工号对应一个员工的信息。若使用数组,增删数据时比较麻烦;使用链表,获取数据时比较麻烦。有没有一种数据结构,能把某一员工的姓名转换为它对应的工号,再根据工号查找该员工的完整信息呢?没错此时就可以使用哈希表的哈希函数来实现。
-
案例二:存储联系人和对应的电话号码:当要查找张三(比如)的号码时,若使用数组:由于不知道存储张三数据对象的下标值,所以查找起来十分麻烦,使用链表时也同样麻烦。而使用哈希表就能通过哈希函数把张三这个名称转换为它对应的下标值,再通过下标值查找效率就非常高了。
也就是说:哈希表最后还是基于数据来实现的,只不过哈希表能够通过哈希函数把字符串转化为对应的下标值,建立字符串和下标值的对应关系。
哈希化的方式
为了把字符串转化为对应的下标值,需要有一套编码系统,为了方便理解我们创建这样一套编码系统:比如a为1,b为2,c为3,以此类推z为26,空格为27(不考虑大写情况)。
有了编码系统后,将字母转化为数字也有很多种方式:
方式一:数字相加。例如cats转化为数字:3+1+20+19=43,那么就把43作为cats单词的下标值储存在数组中;
但是这种方式会存在这样的问题:很多的单词按照该方式转化为数字后都是43,比如was。而在数组中一个下标值只能储存一个数据,所以该方式不合理。
方式二:幂的连乘。我们平时使用的大于10的数字,就是用幂的连乘来表示它的唯一性的。比如: 6543=6 * 103 + 5 * 102 + 4 * 10 + 3;这样单词也可以用该种方式来表示:cats = 3 * 273 + 1 * 272 + 20 * 27 + 17 =60337;
虽然该方式可以保证字符的唯一性,但是如果是较长的字符(如aaaaaaaaaa)所表示的数字就非常大,此时要求很大容量的数组,然而其中却有许多下标值指向的是无效的数据(比如不存在zxcvvv这样的单词),造成了数组空间的浪费。
两种方案总结:
-
第一种方案(让数字相加求和)产生的数组下标太少;
-
第二种方案(与27的幂相乘求和)产生的数组下标又太多;
现在需要一种压缩方法,把幂的连乘方案系统中得到的巨大整数范围压缩到可接受的数组范围中。可以通过取余操作来实现。虽然取余操作得到的结构也有可能重复,但是可以通过其他方式解决。
哈希表的一些概念:
-
哈希化:将大数字转化成数组范围内下标的过程,称之为哈希化;
-
哈希函数:我们通常会将单词转化成大数字,把大数字进行哈希化的代码实现放在一个函数中,该函数就称为哈希函数;
-
哈希表:对最终数据插入的数组进行整个结构的封装,得到的就是哈希表。
仍然需要解决的问题:
- 哈希化过后的下标依然可能重复,如何解决这个问题呢?这种情况称为冲突,冲突是不可避免的,我们只能解决冲突。
解决冲突常见的两种方案:
- 方案一:链地址法(拉链法);