隊列和棧的定義
這兩個數(shù)據(jù)結(jié)構(gòu)沒有什么可講的, 這里我就簡要說一下, 后面直接用例題說明
- 棧(stack): 先進(jìn)后出(FILO)
可以想象一下我們生活中的桶, 我們往桶里面放東西, 后放的東西會在桶的上部, 每次按順序取東西, 都是從上往下取, 所以后放進(jìn)去的會被先取出來 - 隊列(queue): 先進(jìn)先出(FIFO)
對應(yīng)我們生活中的物品就是管道, 我們從一頭往管道里面放東西, 另一頭東西出來的順序跟我們放的順序是一致的, 先放進(jìn)去的先出來
例題
用數(shù)組實現(xiàn)固定大小的棧
function Stack(arr, len) {
this.arr = arr
this.len = len
this.index = -1
}
Stack.prototype = {
push(num) {
if (this.arr.length === this.len) {
console.log('full')
return
}
this.arr[++this.index] = num
},
pop() {
if (this.arr.length === 0) {
console.log('empty')
return
}
let tmp = this.arr[this.index--]
this.arr.length -= 1
return tmp
},
peek() {
if (this.arr.length === 0) {
console.log('empty')
return
}
return this.arr[this.index]
}
}
Stack.prototype.constructor = Stack
用數(shù)組實現(xiàn)大小固定的隊列
function Queue(arr, len) {
this.start = 0
this.end = 0
this.size = 0
this.arr = arr
this.arr.length = len
}
Queue.prototype = {
add(num) {
if (this.size === this.arr.length) {
console.log('queue is full')
return
}
this.size++
this.arr[this.end] = num
this.end = this.end === this.arr.length - 1 ? 0 : this.end + 1
},
poll() {
if (this.size === 0) {
console.log('queue is empty')
return
}
this.size--
tmp = this.start
this.start = this.start === this.arr.length - 1 ? 0 : this.start + 1
return this.arr[tmp]
},
peek() {
if (this.size === 0) {
console.log ('queue is empty')
return
}
return this.arr[this.start]
}
}
Queue.prototype.constructor = Queue
實現(xiàn)一個特殊的棧
在現(xiàn)實棧的基本功能的基礎(chǔ)上, 再實現(xiàn)返回棧中最小元素的操作.
- pop, push, getMin操作的時間復(fù)雜度都是O(1)
- 設(shè)計的棧類型可以使用線程的棧結(jié)構(gòu)
思路:
- 開辟兩個棧, 一個data棧用來保存數(shù)據(jù), 另一個min棧用來保存最小值
- 第一次往data棧中push一個數(shù)時, 同時往min棧中也push這個數(shù)
- 每次往data棧中push數(shù)時, 如果data棧中push的數(shù)小于等于min棧頂?shù)闹? 那么往min棧中push這個數(shù), 如果data棧中push的數(shù)大于當(dāng)前min棧頂?shù)闹? 把min棧頂?shù)闹翟偻鵰in棧中push一次
- 每次從data棧頂pop一個值時, 同時從min棧中pop一個值, 這樣就能保證min棧頂?shù)闹涤肋h(yuǎn)是data棧的最小值
代碼這里就不寫了, 留給大家自己動手
矩陣
轉(zhuǎn)圈打印矩陣
.給定一個整型矩陣matrix, 請按照轉(zhuǎn)圈的方式打印它怎茫。
例如:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
打印結(jié)果為: 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
要求: 額外空間復(fù)雜度為O(1)
思路:
這個題可以用宏觀調(diào)度的思路來解決
把矩陣分層, 每層都當(dāng)做是獨立的, 互不影響,如圖:
那么題目就變成了蜜宪，從外向內(nèi), 依次打印每一層上所有的數(shù)圃验，每層都從左上角開始打印, 順時針打印一圈, 每層的操作互不影響, 例如:
第一層打印 1 2 3 4 5 10 15 5 6 43 22 8 3 16 11 6
進(jìn)入第二層打印7 8 9 14 6 7 9 12
第三層只打印13
function print(matrix) {
let c1 = 0
let r1 = 0
let c2 = matrix[0].length - 1
let r2 = matrix.length - 1
while (c1 <= c2 && r1 <= r2) {
printEdge(matrix, c1++, r1++, c2--, r2--)
}
}
function printEdge(matrix, C1, R1, C2, R2) {
if (R1 === R2) {
for (let i = C1; i <= C2; i++) {
console.log(matrix[R1][i])
}
} else if (C1 === C2) {
for (let i = R1; i <= R2; i++) {
console.log(matrix[i][C1])
}
} else {
let curR = R1
let curC = C1
while (curC != C2) {
console.log(matrix[R1][curC])
curC++
}
while (curR != R2) {
console.log(matrix[curR][C2])
curR++
}
while (curC != C1) {
console.log(matrix[R2][curC])
curC--
}
while (curR != R1) {
console.log(matrix[curR][C1])
curR--
}
}
}
鏈表
這部分大部分內(nèi)容來自于《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)和算法（第二版）》這本書
為什么用鏈表
- 不確定數(shù)組解構(gòu)的容量時:
- 數(shù)組大小調(diào)整的成本非常大， 所以我們需要提前設(shè)置容量
- 通常我們不知道我們需要多少空間花費
- 添加和移除很多元素時缝呕，最好的選擇就是鏈表
鏈表是什么
鏈表存儲有序的元素集合澳窑，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的供常。每個 元素由一個存儲元素本身的節(jié)點和一個指向下一個元素的引用（也稱指針或鏈接）組成摊聋。下圖展 示了一個鏈表的結(jié)構(gòu)：
用來說明鏈表的最流行的例子，那就是火車栈暇。一列火車是由一系列車廂（也 稱車皮）組成的。每節(jié)車廂或車皮都相互連接瞻鹏。你很容易分離一節(jié)車皮悲立，改變它的位置鹿寨，添加或 移除它新博。下圖演示了一列火車。每節(jié)車皮都是列表的元素脚草，車皮間的連接就是指針：
創(chuàng)建鏈表
下面是一個LinkedList類的框架:
function LinkedList() {
let Node = function(element) {
this.element = element
this.next = null
}
let length = 0
let head = null
this.append = function(element){}
this.insert = function(position, element){}
this.removeAt = function(position){}
this.remove = function(element){}
this.indexOf = function(element){}
this.isEmpty = function() {}
this.size = function() {}
this.getHead = function(){}
this.toString = function(){}; this.print = function(){};
}
- 其中Node是一個輔助類, 表示要加入鏈表的結(jié)點, 它包括element, 即結(jié)點保存的值和next, 即指向下一個結(jié)點的指針
- 同樣我們需要一個head, 用來保存鏈表的第一項
- length用來存儲結(jié)點的數(shù)量
- 剩下的就是一些常用的增刪改查方法
向鏈表尾部追加元素
向LinkedList對象尾部添加一個元素時赫悄，可能有兩種場景：列表為空，添加的是第一個元 素馏慨，或者列表不為空埂淮，向其追加元素。
this.append = function(element) {
let node = new Node(element)
let current
if (head === null) { //列表中第一個節(jié)點
head = node
} else {
current = head
//循環(huán)列表写隶，直到找到最后一項
while (current.next) {
current = current.next
}
//找到最后一項倔撞，將其next賦為node，建立鏈接
current.next = node
}
length++ //更新列表的長度
}
整體流程如下:
- 把element作為值傳入慕趴，創(chuàng)建Node項
-
若鏈表為空, 此時head指向null, 我們把head指向node
列表最后一個節(jié)點的下一個元素始終是null痪蝇。
-
如不是空鏈表, 要向列表的尾部添加一個元素，遍歷鏈表的每個結(jié)點冕房，直到找到最后一項躏啰。為此，我們需要一個指向列表中 current項的變量, 循環(huán)訪問列表時耙册，當(dāng)current.next元素為null時给僵，我們就知道已經(jīng)到達(dá)列表尾部了。然后 要做的就是讓當(dāng)前（也就是最后一個）元素的next指針指向想要添加到列表的節(jié)點详拙。 下圖展示了這個行為:
- 別忘了遞增鏈表的長度帝际，這樣就能控制它蔓同，輕松地得到鏈表的長度
從鏈表中移除元素
移除元素也有兩種場景：第一種是移 除第一個元素，第二種是移除第一個以外的任一元素蹲诀。
this.removeAt = function(position) {
//檢查越界值
if (position > -1 && position < length) {
let current = head
let previous
let index = 0
//移除第一項
if (positon === 0) {
head = current.next
} else {
while (index++ < position ) {
previous = current
current = current.next
}
previous.next = current.next
}
length--
return current.element
} else {
return null
}
}
-
從鏈表中移除第一個元素的情況
如果想移除第一個元素牌柄， 要做的就是讓 head 指向列表的第二個元素。
-
移除其他項的情況
要從列表中移除當(dāng)前元素侧甫，要做的就是將previous.next和current.next鏈接起來珊佣。這樣，當(dāng)前元素就會被丟棄在計算機(jī)內(nèi)存中披粟，等著被垃圾回收器清除咒锻。
在任意位置插入元素
this.insert = function(element, position) {
//檢查越界值
if (position > - 1 && position <= length) {
let node = new Node(element)
let current = head
let index = 0
let previous
if (position === 0) { //在第一個位置添加
node.next = current
head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = node
node.next = current
}
length++
return true
} else {
return false
}
}
其他方法
toString方法
this.toString = function() {
let current = head
let string = ''
while (current) {
string += current.element + (current.next ? 'n' : '')
current = current.next
}
return string
}
indexOf方法
this.indexOf(element) {
let current = head
let index = 0
while(current) {
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
isEmpty、size和getHead方法
this.isEmpty = function() {
return length === 0
}
this.getLength() {
return length
}
this.getHead() {
return head
}
雙向鏈表
雙向鏈表和普通鏈表的區(qū)別在于守屉，在鏈表中惑艇， 一個節(jié)點只有鏈向下一個節(jié)點的鏈接，而在雙向鏈表中拇泛，鏈接是雙向的：一個鏈向下一個元素滨巴， 另一個鏈向前一個元素，如下圖所示：
雙向鏈表提供了兩種迭代列表的方法：從頭到尾俺叭，或者反過來恭取。我們也可以訪問一個特定節(jié)點的下一個或前一個元素。在單向鏈表中熄守，如果迭代列表時錯過了要找的元素蜈垮，就需要回到列表起點，重新開始迭代裕照。這是雙向鏈表的一個優(yōu)點攒发。
DoublyLinkedList類所需的變動:
function DoublyLinkedList() {
let Node = function(element){
this.element = element
this.next = null
this.prev = null //新增的
}
let length = 0
let head = null
let tail = null //新增的
//這里是方法
...
}
在任意位置插入新元素
向雙向鏈表中插入一個新項跟（單向）鏈表非常類似。區(qū)別在于晋南，鏈表只要控制一個next 指針惠猿，而雙向鏈表則要同時控制next和prev（previous，前一個）這兩個指針负间。
this.insert = function(postion, element) {
if (position > -1 && position <= length) {
let node = new Node(element)
let current = head
let previous
let index = 0
if (position === 0) { //在第一個位置添加
if (!head) { //新增的
head = node
tail = node
} else {
node.next = current
current.prev = node //新增的
head = node
}
} else if (position === length) { //最后一項, 新增的
current = tail
node.next = current
current.prev = node
tail = node
} else {
while (index++ < postion) {
previous = current
current = current.next
}
previous.next = node
node.prev = previous //新增的
node.next = current
current.prev = node //新增的
}
length++ //更新列表的長度
return true
} else {
return false
}
}
我們來分析第一種場景：在列表的第一個位置（列表的起點）插入一個新元素偶妖。如果列表為 空（行{1}），只需要把head和tail都指向這個新節(jié)點唉擂。如果不為空餐屎，current變量將是對列表 中第一個元素的引用。就像我們在鏈表中所做的玩祟，把node.next設(shè)為current腹缩，而head將指向 node（它將成為列表中的第一個元素）。不同之處在于，我們還需要為指向上一個元素的指針設(shè)一個值藏鹊。current.prev指針將由指向null變?yōu)橹赶蛐略厝蠹ァode.prev指針已經(jīng)是null，因此不需要再更新任何東西盘寡。下圖演示了這個過程：
現(xiàn)在來分析一下楚殿，假如我們要在列表最后添加一個新元素。這是一個特殊情況竿痰，因為我們還 控制著指向最后一個元素的指針（tail）脆粥。current變量將引用最后一個元素。然后開 始建立第一個鏈接：node.prev將引用current影涉。current.next指針（指向null）將指向node （由于構(gòu)造函數(shù)变隔，node.next已經(jīng)指向了null）。然后只剩一件事了蟹倾，就是更新tail匣缘，它將由指向current變?yōu)橹赶騨ode。下圖展示了這些行為：
然后還有第三種場景：在列表中間插入一個新元素鲜棠。就像我們在之前的方法中所做的肌厨，迭代 列表，直到到達(dá)要找的位置豁陆。我們將在current和previous元素之間插入新元素柑爸。首先，node.next將指向current献联，而previous.next將指向node竖配，這樣就不會丟失節(jié)點之間的鏈接何址。然后需要處理所有的鏈接：current.prev將指向node里逆，而node.prev將指向previous。下圖展示了這一過程：
從任意位置刪除元素
從雙向鏈表中移除元素跟鏈表非常類似用爪。唯一的區(qū)別就是還需要設(shè)置前一個位置的指針原押。我 們來看一下它的實現(xiàn)：
this.removeAt(position) {
//檢查越界值
if (position > -1 && position < length) {
let current = head
let index = 0
let previous
//移除第一項
if (position === 0) {
head = current.next
//如果只有一項，更新tail, 新增的
if (length === 1) {
tail = null
} else {
head.prve = null
}
}else if (position === length - 1) { //最后一項, 新增的
current = tail
tail = current.prev
tail.next = null
} else {
while (index++ < length) {
previous = current
current = current.next
}
//將previous與current的下一項鏈接起來——跳過current
previous.next = current.next
current.next.prev = previous //新增的
}
length--
return current.element
} else {
return null
}
}
我們需要處理三種場景：從頭部偎血、從中間和從尾部移除一個元素诸衔。
我們來看看如何移除第一個元素。current變量是對列表中第一個元素的引用颇玷，也就是我 們 想 移 除 的 元 素 笨农。 需 要 做 的 就 是 改 變 head 的 引 用 ， 將 其 從 current 改 為 下 一 個 元 素 （current.next）帖渠。但我們還需要更新current.next指向上一個元素的指針（因為第一個元素的prev指針是null）谒亦。因此，把head.prev的引用改為null（因為head也 指向列表中新的第一個元素，或者也可以用current.next.prev）份招。由于還需要控制tail的引用切揭， 我們可以檢查要移除的元素是否是第一個元素，如果是锁摔，只需要把tail也設(shè)為null廓旬。
下圖勾畫了從雙向鏈表移除第一個元素的過程：
下一種場景是從最后一個位置移除元素。既然已經(jīng)有了對最后一個元素的引用（tail）谐腰，我 們就不需要為找到它而迭代列表孕豹。這樣我們也就可以把tail的引用賦給current變量。 接下來十气，需要把tail的引用更新為列表中倒數(shù)第二個元素（current.prev巩步，或者tail.prev 也可以）。既然tail指向了倒數(shù)第二個元素桦踊，我們就只需要把next指針更新為null（tail.next = null）椅野。下圖演示了這一行為：
第三種也是最后一種場景：從列表中間移除一個元素。首先需要迭代列表籍胯，直到到達(dá)要找的位）竟闪。current變量所引用的就是要移除的元素。那么要移除它杖狼，我們可以通過更新 previous.next和current.next.prev的引用炼蛤，在列表中跳過它。因此蝶涩，previous.next將 指向current.next理朋，而current.next.prev將指向previous，如下圖所示：
