Tip
計(jì)算機(jī)基礎(chǔ)不管是什么語(yǔ)言、什么開(kāi)發(fā)崗位都是必須要了解的知識(shí)，本文主要是通過(guò) JS 來(lái)實(shí)現(xiàn)一些常用的數(shù)據(jù)結(jié)構(gòu)，很簡(jiǎn)單。
本文插圖引用：啊哈！算法 ，由于是總結(jié)性文章，所以會(huì)不定時(shí)地修改并更新，歡迎關(guān)注！
Stack 棧
堆棧（stack），也可以直接稱為棧，它是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，并且限定了只能在一段進(jìn)行插入和刪除操作。
如上圖所示，假設(shè)我們有一個(gè)球桶，并且桶的直徑只能允許一個(gè)球通過(guò)。如果按照 2 1 3 的順序把球放入桶中，然后要將球從桶中取出，取出的順序就是 3 1 2，先放入桶中的球被后取出，這就是 棧 插入和刪除的原理。
我們接觸過(guò)的算法書(shū)基本也都是用c語(yǔ)言實(shí)現(xiàn)這個(gè)數(shù)據(jù)結(jié)構(gòu)，它的特殊之處在于只能允許鏈接串列或者陣列的一端（top）進(jìn)行 插入數(shù)據(jù)（push）和 輸出數(shù)據(jù)（pop）的運(yùn)算。那么如果要用 JS 來(lái)實(shí)現(xiàn)它又該怎么操作呢？
// ?？梢杂靡痪S數(shù)組或連結(jié)串列的形式來(lái)完成
class Stack {
constructor() {
this.data = []
this.top = 0
}
// 入棧
push() {
const args = [...arguments]
args.forEach(arg => this.data[this.top++] = arg)
return this.top
}
// 出棧
pop() {
if(this.top === 0) {
throw new Error('The stack is already empty!')
}
const popData = this.data[--this.top]
this.data = this.data.slice(0, -1)
return popData
}
// 獲取棧內(nèi)元素的個(gè)數(shù)
length() {
return this.top
}
// 判斷棧是否為空
isEmpty() {
return this.top === 0
}
// 獲取棧頂元素
goTop() {
return this.data[this.top-1]
}
// 清空棧
clear() {
this.top = 0
return this.data = []
}
}
通過(guò) 面向?qū)ο?/strong> 的思想就可以抽象出一個(gè) 棧 的對(duì)象，實(shí)例化：
const stack = new Stack()
stack.push(1, 2)
stack.push(3, 4, 5)
console.log(stack.data)
// [ 1, 2, 3, 4, 5 ]
console.log(stack.length())
// 5
console.log(stack.goTop())
// 5
console.log(stack.pop())
// 5
console.log(stack.pop())
// 4
console.log(stack.goTop())
// 3
console.log(stack.data)
// [ 1, 2, 3 ]
stack.clear()
console.log(stack.data)
// []
在 啊哈！算法 描述 棧 的應(yīng)用時(shí)，舉了一個(gè)求回文數(shù)的例子，我們也用 JS 來(lái)把它實(shí)現(xiàn)一波：
const isPalindrome = function(words) {
const stack = new Stack()
let copy = ''
words = words.toString()
words.split('').forEach(word => stack.push(word))
while(stack.length() > 0) {
copy += stack.pop()
}
return copy === words
}
console.log(isPalindrome('123ada321'))
// true
console.log(isPalindrome(1234321))
// true
console.log(isPalindrome('addaw'))
// false
Linked List 鏈表
在存儲(chǔ)一大波數(shù)的時(shí)候，我們通常使用的是數(shù)組，但有時(shí)候數(shù)組顯得不夠靈活，比如：有一串已經(jīng)從小到大排好序的數(shù) 2 3 5 8 9 10 18 26 32。現(xiàn)需要往這串?dāng)?shù)中插入 6 使其得到的新序列仍符合從小到大排列。
如上圖所示，如果使用數(shù)組來(lái)實(shí)現(xiàn)的話，則需要將 8 和 8 后面的 數(shù)都依次往后挪一位，這樣操作顯然很耽誤時(shí)間，如果使用 鏈表 則會(huì)快很多：
鏈表（Linked List）是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)。它是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針。和圖中一樣，如果需要在 8 前面插入一個(gè) 6，直接插入就行了，而無(wú)需再將 8 及后面的數(shù)都依次往后挪一位。
那么問(wèn)題來(lái)了，如何使用 JS 實(shí)現(xiàn) 鏈表呢？還是運(yùn)用 面向?qū)ο?/strong> 的思想：
// 抽象節(jié)點(diǎn)類
function Node(el) {
this.el = el
this.next = null
}
// 抽象鏈表類
class LinkedList {
constructor() {
this.head = new Node('head')
}
// 查找數(shù)據(jù)
find(item) {
let curr = this.head
while(curr.el !== item) {
curr = curr.next
}
return curr
}
// 查找前一個(gè)節(jié)點(diǎn)
findPre(item) {
if(item === 'head') {
throw new Error('Now is head!')
}
let curr = this.head
while(curr.next && curr.next.el !== item) {
curr = curr.next
}
return curr
}
// 在 item 后插入節(jié)點(diǎn)
insert(newEl, item) {
let newNode = new Node(newEl)
let curr = this.find(item)
newNode.next = curr.next
curr.next = newNode
}
// 刪除節(jié)點(diǎn)
remove(item) {
let pre = this.findPre(item)
if(pre.next !== null) {
pre.next = pre.next.next
}
}
// 顯示鏈表中所有元素
display() {
let curr = this.head
while(curr.next !== null) {
console.log(curr.next.el)
curr = curr.next
}
}
}
實(shí)例化：
const list = new LinkedList()
list.insert('0', 'head')
list.insert('1', '0')
list.insert('2', '1')
list.insert('3', '2')
console.log(list.findPre('1'))
// Node { el: '0', next: Node { el: '1', next: Node { el: '2', next: [Object] } } }
list.remove('1')
console.log(list)
// LinkedList { head: Node { el: 'head', next: Node { el: '0', next: [Object] } } }
console.log(list.display())
// 0 2 3
Binary tree 二叉樹(shù)
二叉樹(shù)（binary tree）是一種特殊的樹(shù)。二叉樹(shù) 的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)兒子，左邊的叫做左兒子，右邊的叫做右兒子，或者說(shuō)每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)。更加嚴(yán)格的遞歸定義是：二叉樹(shù) 要么為空，要么由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)組成，而左子樹(shù)和右子樹(shù)分別是一棵 二叉樹(shù)。
和前兩個(gè)例子一樣，通過(guò)類的抽象來(lái)實(shí)現(xiàn) 二叉樹(shù)：
// 抽象節(jié)點(diǎn)類
function Node(key) {
this.key = key
this.left = null
this.right = null
}
// 插入節(jié)點(diǎn)的方法
const insertNode = function(node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode
} else {
insertNode(node.left, newNode)
}
} else {
if (node.right === null) {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
}
// 抽象二叉樹(shù)
class BinaryTree {
constructor() {
this.root = null
}
insert(key) {
let newNode = new Node(key)
if(this.root === null) {
this.root = newNode
} else {
insertNode(this.root, newNode)
}
}
}
實(shí)例化測(cè)試一波：
const data = [8, 3, 10, 1, 6, 14, 4, 7, 13]
// 實(shí)例化二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)
const binaryTree = new BinaryTree()
// 遍歷數(shù)據(jù)并插入
data.forEach(item => binaryTree.insert(item))
// 打印結(jié)果
console.log(binaryTree.root)
/*
Node {
key: 8,
left:
Node {
key: 3,
left: Node { key: 1, left: null, right: null },
right: Node { key: 6, left: [Object], right: [Object] } },
right:
Node {
key: 10,
left: null,
right: Node { key: 14, left: [Object], right: null } } }
*/
總結(jié)
算法和數(shù)據(jù)結(jié)構(gòu)是非常重要的一環(huán)，之后也會(huì)慢慢總結(jié)更新，歡迎關(guān)注！
