線性結構
線性結構是數據結構中的一類，那什麼是線性結構呢？線性結構是一種有序數據項的集合，其中每個數據項都有 唯一的 前驅和後繼，注意是唯一的，當然，也可能只有一個前驅沒有後繼（第一個），或者有後繼沒有前驅（最後一個），但是只要有，就是唯一的。生活中的例子比如手串、火車等都是線性結構的。再放個圖感受一下下。
是不是有概念了。接下來我們將分別介紹幾個數據結構中常見的線性結構：
- 列表
- 棧
- 隊列
- 鍊表
列表
列表是非常常見的數據結構，列表分為無序列表和有序列表，數組就是最基本的列表，幾乎所有的程式語言都會給予原生的支持，我們也在代碼中經常使用它，它是最簡單的數據結構。下面我們用代碼實現數組每一種數據結構我們都要實現一系列用來操作它的方法。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) {
\tlet numStack = new Stack();
\tlet numStr = '';
\twhile (num > 0) {
\t\tconsole.log(num);
\t\tnumStack.push(num % 2);
\t\tnum = Math.floor(num / 2);
\t}
\twhile (!numStack.isEmpty()) {
\t\tnumStr += numStack.pop();
\t}
\treturn 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) {
\tlet queue = new Queue();
\tfor (let people of array) {
\t\tqueue.enqueue(people);
\t}
\twhile (queue.size() > 1) {
\t\tfor (let i = 0; i < 6; i++) {
\t\t\tlet first = queue.dequeue(); //第一個元素移除隊列
\t\t\tqueue.enqueue(first); //剛剛出列的元素進入隊列
\t\t}
\t\tqueue.dequeue();
\t}
\treturn 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) {
\tif (this.isEmpty()) {
\t\tthis.items[this.count] = element
\t\tthis.count++
\t} else if (this.lowestCount > 0) {
\t\tthis.items[--this.lowestCount] = element
\t} else {
\t\tthis.count++
\t\tfor (let i = this.count; i > 0; i--) {
\t\t\tthis.items[i] = this.items[i - 1]
\t\t}
\t\tthis.items[0] = element
\t}
}
\t
//從隊列後端移除元素
removeBack() {
\tif (this.isEmpty()) {
\t\treturn undefined
\t}
\tconst result = this.items[this.count - 1]
\tdelete this.items[this.count - 1]
\tthis.count--
\treturn result
}
//查看隊列尾元素
\tpeekBack() {
\tif (this.isEmpty()) {
\t\treturn undefined
\t}
\treturn this.items[this.count - 1]
}再做一個練習來鞏固一下，這個練習也很經典，就是迴文的檢測，利用隊列先將迴文逐個插入隊列，然後從頭尾個出隊列一個字符，比較是否相等，如果知道疊代結束都相同就返回true，其間有一個不同就返回false，代碼如下。
function palindromes(str) {
\tlet queue = new DeQueue()
\tfor (let char of str) {
\t\tqueue.addBack(char)
\t}
\tlet flag = true
\twhile (queue.size() > 1 && flag) {
\t\tif (queue.removeBack() !== queue.removeFront()) flag = false
\t}
\treturn 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里應該就好理解多了。
小結
本篇介紹了一些數據結構中的線性結構，比較好理解。數據結構是算法的基礎，多敲幾遍代碼，自己實現一下就能感受到它的奇妙了。加油！！！