数据结构与算法：线性结构的快速掌握

线性结构

线性结构是数据结构中的一类，那什么是线性结构呢？线性结构是一种有序数据项的集合，其中每个数据项都有 唯一的 前驱和后继，注意是唯一的，当然，也可能只有一个前驱没有后继（第一个），或者有后继没有前驱（最后一个），但是只要有，就是唯一的。生活中的例子比如手串、火车等都是线性结构的。再放个图感受一下下。

是不是有概念了。接下来我们将分别介绍几个数据结构中常见的线性结构：

• 列表
• 栈
• 队列
• 链表

列表

列表是非常常见的数据结构，列表分为无序列表和有序列表，数组就是最基本的列表，几乎所有的编程语言都会给予原生的支持，我们也在代码中经常使用它，它是最简单的数据结构。下面我们用代码实现数组每一种数据结构我们都要实现一系列用来操作它的方法。JavaScript已经给我们实现了操作数组的方法。我们可以直接使用他们去操作数组。

方法描述pop删除并返回数组的最后一个元素push向数组的末尾添加一个或更多元素，并返回新的长度。shift删除并返回数组的第一个元素unshift向数组的开头添加一个或更多元素，并返回新的长度。concat连接两个或更多数组，并返回结果every对数组中的每个元素运行给定函数，如果该函数对每个元素都返回 true ，则返回 truefilter对数组中的每个元素运行给定函数，返回该函数会返回 true 的元素组成的数组forEach对数组中的每个元素运行给定函数。这个方法没有返回值join将所有的数组元素连接成一个字符串indexOf返回第一个与给定参数相等的数组元素的索引，没有找到则返回 -1lastIndexOf返回在数组中搜索到的与给定参数相等的元素的索引里最大的值map对数组中的每个元素运行给定函数，返回每次函数调用的结果组成的数组reverse颠倒数组中元素的顺序，原先第一个元素现在变成最后一个，同样原先的最后一个元素变成了现在的第一个slice传入索引值，将数组里对应索引范围内的元素作为新数组返回some对数组中的每个元素运行给定函数，如果任一元素返回 true ，则返回 truesort按照字母顺序对数组排序，支持传入指定排序方法的函数作为参数toString将数组作为字符串返回valueOf和 toString 类似，将数组作为字符串返回

栈

栈类似于数组，是一种在添加和删除元素时更加可控的的数组。在栈中，数据项的添加和删除都只发生在顶端。 就像叠在一起的盘子一样，你只能取最上面的盘子，也只能把盘子放在最上面。下面我们用JavaScript数组来实现一下栈结构。

class Stack {    // 构造函数    constructor() {        this.items = [];    }    // 添加数据项到栈顶    push(element) {        this.items.push(element);    }    // 从栈移除数据项    pop() {        return this.items.pop();    }    // 查看栈顶数据项    peek() {        return this.items[this.items.length - 1];    }    // 栈是否为空    isEmpty() {        return this.items.length === 0;    }        // 栈的大小    size() {        return this.items.length;    }    // 清空栈    lear() {        this.items = [];    }}

实现之后我们就能使用它了，下面来做一个经典的练习

十进制转换为二进制

这个题目我们数学上都会解答，即采用"除2取余，逆序排列"法

用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为小于1时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

那么我们用上面的栈来解决一下

function binaryConver(num) {	let numStack = new Stack();	let numStr = '';	while (num > 0) {		console.log(num);		numStack.push(num % 2);		num = Math.floor(num / 2);	}	while (!numStack.isEmpty()) {		numStr += numStack.pop();	}	return numStr;}console.log(binaryConver(3)); // 11

队列

队列也类似于数组，是另一种在添加和删除元素时更加可控的的数组。其特征与栈不同：新增数据项发生在一端，而移除现有数据项发生在另一端。就像排队买票一样，后来的人只能排在队伍的最后，只有最前面的人买完票后面的人才能买票。我们用JavaScript代码来实现一下。用数组实现是比较简单的，我们这里用对象来实现一下；

class Queue {    constructor() {        this.count = 0;// 记录队列尾部的元素        this.lowestCount = 0;// 记录队列首部的元素        this.items = {};    }    //向队列中添加元素    enqueue(element) {        this.items[this.count] = element;        this.count++;    }    //从队列移除元素    dequeue() {        if (this.isEmpty()) {            return undefined;        }        const result = this.items[this.lowestCount];        delete this.items[this.lowestCount];        this.lowestCount++;        return result;    }    //查看队列头元素    peek() {        if (this.isEmpty()) {            return undefined;        }        return this.items[this.lowestCount];    }    //队列是否为空    isEmpty() {        return this.count - this.lowestCount === 0;    }    //队列的大小    size() {        return this.count - this.lowestCount;    }    //清空队列    clear() {        this.items = {};        this.count = 0;        this.lowestCount = 0;    }    //输出队列的全部元素    toString() {        if (this.isEmpty()) {            return '';        }        let objString = `${this.items[this.lowestCount]}`;        for (let i = this.lowestCount + 1; i < this.count; i++) {            objString = `${objString},${this.items[i]}`;        }        return objString;    }}

我们还是找一个经典题目实践一下：击鼓传花问题，设置每次数到6时，手中有花的人就出队表演节目，看看最后剩下哪一个幸运儿。我们还是用已经实现的队列结构来实现一下这个问题。我们假设队列的第一个人手中持花。

function spread(array) {	let queue = new Queue();	for (let people of array) {		queue.enqueue(people);	}	while (queue.size() > 1) {		for (let i = 0; i < 6; i++) {			let first = queue.dequeue(); //第一个元素移除队列			queue.enqueue(first); //刚刚出列的元素进入队列		}		queue.dequeue();	}	return queue.dequeue();}let list = ['Leblanc','Azir','Ryze','Kassadin','Oriana','Ahri','Viktor','Diana','Ziggs'];console.log(spread(list)); // Azir复制代码

这样问题就解决了。 接下来我们基于上面的队列完成 双端队列 结构，双端队列，顾名思义，就是队列的两端均可添加数据项和删除数据项，因此更改enqueue名称为addBack即在队列的后端添加数据项，更改dequeue名称为removeFront即在队列的前端移除数据项，更改peek名称为peekFront即查看队列最前端的数据项。除了这些方法我们还要添加几个方法

//向队列前端添加元素addFront(element) {	if (this.isEmpty()) {		this.items[this.count] = element		this.count++	} else if (this.lowestCount > 0) {		this.items[--this.lowestCount] = element	} else {		this.count++		for (let i = this.count; i > 0; i--) {			this.items[i] = this.items[i - 1]		}		this.items[0] = element	}}	//从队列后端移除元素removeBack() {	if (this.isEmpty()) {		return undefined	}	const result = this.items[this.count - 1]	delete this.items[this.count - 1]	this.count--	return result}//查看队列尾元素	peekBack() {	if (this.isEmpty()) {		return undefined	}	return this.items[this.count - 1]}

再做一个练习来巩固一下，这个练习也很经典，就是回文的检测，利用队列先将回文逐个插入队列，然后从头尾个出队列一个字符，比较是否相等，如果知道迭代结束都相同就返回true，其间有一个不同就返回false，代码如下。

function palindromes(str) {	let queue = new DeQueue()	for (let char of str) {		queue.addBack(char)	}	let flag = true	while (queue.size() > 1 && flag) {		if (queue.removeBack() !== queue.removeFront()) flag = false	}	return flag}console.log(palindromes('井桐双照新妆冷,冷妆新照双桐井')) // true

链表

列表结构的数据项在内存中是一个接一个存储的，虽然查询的时候很方便，但是增加一个或者删除一个元素的时候，大部分情况都需要将列表的其他元素也移动一遍，这样就使性能变差。链表结构解决了这个问题，它允许将数据存储在任意位置，但是每个元素的都将自己的引用存储到上一个元素的内存中，这样就形成了一个链，添加或删除数据时只要更改他的上一个元素和下一个元素的引用就可以。虽然链表给添加和删除带来了便利，但是查询时就需要从链表头开始遍历查找。都各有利弊吧，要分情况来使用他们。下面我们用代码实现一个列表结构。

//相等性比较函数function defaultEquals(a, b){  return Object.is(a, b)}//表示链表中的一个元素class Node {  constructor(element) {    this.element = element; //元素的值    this.next = undefined; //指向下一个元素的指针  }}//链表类class LinkedList {  constructor (equalsFn = defaultEquals) {    this.count = 0; //记录链表元素的数量    this.head = undefined; //保存第一个元素的引用  }  //向链表的尾部添加一个元素  push(element){    const node = new Node(element); //创建一个Node实例    let current; //用来存储最后一个元素的临时变量    if(this.head == null){ //判断第一个元素是否为空即链表是否为空      this.head = node; //为空直接把元素赋值给第一个元素    }else{      current = this.head; //不为空把链表的第一个元素赋值给循环用的临时变量      while (current.next != null) { //判断是否循环到了最后一个元素        current = current.next;      }      current.next = node;//将最后一个的指针指向要新增的元素    }    this.count++;//链表元素数量加一  }  //从链表中移除元素  removeAt(index){    //检查位置参数是否越界    if (index >= 0 && index < this.count) {      if(index === 0){ //如果要移除的是第一个元素        this.head = current.next //直接将第一个元素改为第二个      }else {        let previous = this.getElementAt(index - 1); //用来存储要移除元素的前一个元素        previous.next = previous.next.next      }      this.count--    }    return undefined  }  //获取某个位置的元素  getElementAt(index) {    //检查位置参数是否越界    if (index >= 0 && index < this.count) {      let node = this.head;      for (let i = 0; i < index && node != null; i++) {        node = node.next;      }      return node;    }    return undefined;  }  //在某一个位置插入元素  insert(element, index) {    //判断位置参数是否越界    if(index >= 0 && index <= this.count) {      const node = new Node(element); //创建一个新的元素      let current = this.head      if(index === 1) { //判断是否在第一个位置添加        node.next = current;        this.head = node;      }else{        let previous = this.getElementAt(index - 1);        node.next = previous.next;        previous.next = node;      }      this.count++      return true;    }    return false;  }  //查找相应元素的位置  indexOf(element) {    let current = this.head;    for (let i = 0; i < this.count && current != null; i++) { //循环遍历整个链表      if (this.equalsFn(element, current.element)) { //利用传入的函数进行检验        return i; //返回元素的位置      }      current = current.next; //让current指向下一个指针    }    return -1; //未找到，返回-1  }  //移除某个元素  remove(element) {    const index = this.indexOf(element);    return this.removeAt(index);  }  //检查链表是否为空  isEmpty() {    return this.size() === 0;  }  //返回链表大小  size() {    return this.count;  }  //获取链表头  getHead() {    return this.head;  }  //返回整个链表的字符串  toString() {    if (this.head == null){      return '';    }    let objString = `${this.head.element}`;    let current = this.head.next;    for (let i = 1; i < this.count && current != null; i++) {      objString = `${objString},${current.element}`;      current = current.next;    }    return objString;  }}

链表是数据结构中比较难的一块内容，但是把它放在js里应该就好理解多了。

小结

本篇介绍了一些数据结构中的线性结构，比较好理解。数据结构是算法的基础，多敲几遍代码，自己实现一下就能感受到它的奇妙了。加油！！！