回味javascript資料結構與演算法(一)連載

語言: CN / TW / HK


theme: channing-cyan

一、棧資料結構

1、什麼是棧資料結構 棧是一種遵循從後進先出原則的有序集合,新新增或待刪除的元素都儲存在棧的同一端,稱作棧頂,另一端就叫棧底。在棧裡,新元素都靠近棧頂,舊元素都接近棧底。 2、實現一個基於陣列的棧

````

/* * 建立一個javascript資料結構和演算法庫 * 棧資料結構 * 向棧中新增元素 * 從棧中移除元素 * 如何使用stack類 * /

// 棧是是一種遵從先進後出原則的有序集合

class Stack { constructor() { this.items = [] // {1} } get() { return this.items
} // 實現向棧頂新增一個或多個元素 push(ele) { this.items.push(ele) } // 移除棧頂的元素,同時返回被移除的元素 pop() { return this.items.pop() } // 返回棧頂的元素,不對棧做任何修改 peek() { // 也就是返回棧最後新增的元素 return this.items[this.items.length - 1] } // 如果棧裡沒有任何元素就返回true,否則就返回false isEmpty() { return this.items.length === 0 } // 移除棧裡的所有元素 clear() { this.items = [] } // 返回棧裡元素個數。該方法和陣列的length屬性很類似 size() { return this.items.length } }

// 上面棧的功能已經實現,現在開始測試 // 1、例項化 棧 const stact = new Stack() stact.push(1) stact.push(2) stact.push(3) stact.push(4) stact.push(5)

// console.log( 'pop',stact.pop()) //1 console.log( 'peek',stact.peek()) //1 console.log( 'get',stact.get()) //1 console.log( 'size',stact.size()) console.log( 'isEmpty',stact.isEmpty())

````

3、實現一個基於javascript物件的Stack類

```` /* * 建立一個javascript資料結構和演算法庫 * 棧資料結構 * 向棧中新增元素 * 從棧中移除元素 * 如何使用stack類 * /

// 棧是是一種遵從先進後出原則的有序集合

class Stack { constructor() { this.count = 0 // 記錄棧的大小 this.items = {} // {1} } get() { return this.items
} // 返回棧裡元素個數。該方法和陣列的length屬性很類似 size() { return this.count } // 向棧中插入元素 push(ele) { this.items[this.count] = ele this.count++ } // 移除棧中的元素 ,從棧中彈出元素,也就是移除棧頂的元素 pop() { if (this.isEmpty()) { // 棧為空的情況 return undefined } this.count-- const result = this.items[this.count]; //先儲存棧頂的值 以便在刪除之前儲存下來並在刪除之後返回刪除的元素 delete this.items[this.count]; return result } // 返回棧頂的元素,不對棧做任何修改 peek() { if (this.isEmpty()) { // 棧為空的情況 return undefined } // 因為count 是從 return this.items[this.count - 1] // 也就是返回棧最後新增的元素

 }
// 如果棧裡沒有任何元素就返回true,否則就返回false
isEmpty() { 
    return this.count === 0
 }
// 移除棧裡的所有元素
clear() {
    this.items = {}
    this.count = 0
}
// 實現tostring()功能
toString() {
    if (this.isEmpty()) {
        // 棧為空的情況
        return ''
    }
    let objstring = `${this.items[0]}`
    for (let i = 1; i < this.count; i++) {
        objstring = `${objstring},${this.items[i]}`
    }
    return objstring

}

}

// 上面棧的功能已經實現,現在開始測試 // 1、例項化 棧 const stact = new Stack() stact.push(1) stact.push(2) stact.push(3) stact.push(4) stact.push(5) console.log( 'get',stact.get()) //1 // console.log('pop', stact.pop()) //1 // console.log( 'get',stact.get()) //1 console.log('peek', stact.peek()) //1 console.log('toString', stact.toString()) //1

// console.log( 'size',stact.size()) // console.log( 'isEmpty',stact.isEmpty())

````

二、佇列資料結構

1、佇列的定義

佇列是遵循先進後廚的原則的一組有序的項。佇列在尾部新增新元素,並從頂部移除元素。最新新增的元素必須排在佇列的末尾。

例如:電影廳、自助餐廳、雜貨店收銀臺。

2、實現一個佇列

```` /* * 本檔案實現目標 * 佇列資料結構 * 雙端佇列資料結構 * 向佇列和雙端佇列增加元素 * 從佇列和雙端佇列增加元素 * 用擊鼓傳花遊戲模擬迴圈佇列 * 用雙端佇列檢查一個片語是否構成迴文 * / // 佇列遵循先進先出原則的一組有序的項

// 建立佇列 class Queue { constructor() { this.count = 0; // 用來儲存佇列的大小 this.lowestCount = 0; // 追蹤第一個元素 this.items = {} //儲存佇列 } get() { return this.items } // 宣告一些佇列可用的方法 //向佇列尾部新增一個或多個項 enqueue(ele) { this.items[this.count] = ele this.count++ } // 移除佇列的第一項(即排在佇列最前面的項)並返回被移除的元素 dequeue() { if (this.isEmpty()) { return undefined } const result = this.items[this.lowestCount]; //儲存第一個元素 delete this.items[this.lowestCount]; // 刪除第一個元素 this.lowestCount++; // this.count--; return result } // 檢視佇列頭部的元素 peek() { if (this.isEmpty()) { return undefined } return this.items[this.lowestCount] } // 如果佇列中不包含任何元素,返回true,否則返回false isEmpty() { return this.size() === 0 } // 返回佇列包含的元素個數 size() { return this.count - this.lowestCount } // 清空佇列 clear() { this.items = {}; this.count = 0; this.lowestCount = 0 } // 實現tostring方法 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 } }

const queue = new Queue() queue.enqueue('第一') queue.enqueue('第2') queue.enqueue('第3') queue.enqueue('第4') console.log('檢視佇列頭部的資訊',queue.peek()) console.log('檢視佇列的大小',queue.size()) console.log('判斷是否為空',queue.isEmpty()) console.log('移除堆列資訊', queue.dequeue()) console.log('檢視佇列頭部的資訊',queue.peek()) console.log('格式化toString',queue.toString()) console.log('檢視佇列的大小', queue.size()) console.log('移除堆列資訊', queue.dequeue()) console.log('移除堆列資訊', queue.dequeue()) console.log('移除堆列資訊', queue.dequeue()) console.log('檢視佇列的大小', queue.size()) module.exports = Queue ````

3、雙端佇列資料結構

雙端佇列是一種允許我們同時從前端和後端新增和一簇元素的特殊佇列。

雙端佇列在顯示生活中的例子有電影院、餐廳種排隊的隊伍等。舉個例子,一個剛買了票的人如果知識還需要再問一些簡單的資訊,就可以直接回到隊伍的頭部。另外,再隊伍末尾的人如果趕時間,他可以直接離開隊伍。

實現一個雙端佇列

```` /* * 本檔案實現目標 * 佇列資料結構 * 雙端佇列資料結構 * 向佇列和雙端佇列增加元素 * 從佇列和雙端佇列增加元素 * 用擊鼓傳花遊戲模擬迴圈佇列 * 用雙端佇列檢查一個片語是否構成迴文 * / // 佇列遵循先進先出原則的一組有序的項

// 建立佇列 class Deque { constructor() { this.count = 0; // 用來儲存佇列的大小 this.lowestCount = 0; // 追蹤第一個元素 this.items = {} //儲存佇列 } get() { return this.items } // 在雙端佇列前端新增元素 addFrot(ele) { if (this.isEmpty()) { // 如果佇列為空,則新增第一個元素,呼叫新增元素到末尾的方法 this.addBack(ele) } else if (this.lowestCount > 0) { // 第一個元素被移除過lowestCount !== 0 this.lowestCount--; this.items[this.lowestCount] = ele } else { // 從後面開始移動所有元素一位 for (let i = this.count; i > 0; i-- ) { this.items[i] = this.items[i - 1]; } this.count++; this.lowestCount = 0; this.items[0] = ele } } //向佇列尾部新增一個或多個項 addBack(ele) { this.items[this.count] = ele this.count++ } // 移除佇列的第一項(即排在佇列最前面的項)並返回被移除的元素 removeFront() { if (this.isEmpty()) { return undefined } const result = this.items[this.lowestCount]; //儲存第一個元素 delete this.items[this.lowestCount]; // 刪除第一個元素 this.lowestCount++; // this.count-- return result } // 移除佇列後面一項 removeBack() { if (this.isEmpty()) { // 棧為空的情況 return undefined } this.count-- const result = this.items[this.count]; //先儲存棧頂的值 以便在刪除之前儲存下來並在刪除之後返回刪除的元素 delete this.items[this.count]; return result } // 檢視佇列頭部的元素 peek() { if (this.isEmpty()) { return undefined } return this.items[this.lowestCount] } // 如果佇列中不包含任何元素,返回true,否則返回false isEmpty() { return this.count === 0 } // 返回佇列包含的元素個數 size() { return this.count } // 清空佇列 clear() { this.items = {}; this.count = 0; this.lowestCount = 0 } // 實現tostring方法 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 } }

const queue = new Deque() // queue.addFrot('第一') // queue.addBack('第2') // queue.addFrot('第3') // queue.addBack('第4') // console.log('檢視佇列頭部的資訊',queue.peek()) // console.log('檢視佇列的大小',queue.size()) // console.log('判斷是否為空',queue.isEmpty()) // console.log('移除堆列資訊', queue.dequeue()) // console.log('檢視佇列頭部的資訊',queue.peek()) // console.log('移除後面一個元素', queue.peek()) // console.log('檢視佇列的大小',queue.size()) // console.log('格式化toString',queue.removeBack())

module.exports = Deque

````

三、使用佇列解決現實問題

1、實現一個擊鼓傳花遊戲

在這個遊戲中,孩子們圍城一個圓圈,把花盡快地傳遞給旁邊的人。某一時刻傳話停止,這個時候花在誰手裡,誰就推出圓圈、結束遊戲。重複這個過程,直到只剩一個孩子(勝者)。

```` /* * 使用queue 模擬擊鼓傳花遊戲 /

var Queue = require("./佇列");  //這個檔案見標題二 實現一個佇列程式碼

function hotPhtato ( elementList ,num ) {
    const queue = new Queue();
    const elimitatedList = [];//被移除的人
    for (let i = 0; i < elementList.length; i++) {
        queue.enqueue(elementList[i])
    }
    while (queue.size() > 1) {
        for (let i = 0; i < num; i++) {
            // console.log('queue.dequeue()',queue.dequeue())
            queue.enqueue(queue.dequeue()) //把移除的項,從新追加進去
            // console.log('queue.enqueue()',queue.get())
        }
        elimitatedList.push(queue.dequeue());
    }

    return {
        elimitated: elimitatedList,
        winner:queue.dequeue()
    }
}



const names = ['關羽', '張飛', '劉備', '黃忠', '諸葛亮']

const result = hotPhtato(names, 7)
result.elimitated.forEach(name => {
    console.log(`${name}在擊鼓傳花遊戲中被淘汰`)
})
console.log(`勝利者${result.winner}`)

````

2、迴文檢查器

迴文的解釋:迴文是正反都能讀通的單詞、片語、數或 一系列字元的序列例如 madam 或者 racecar

有不同的演算法可以檢查一個片語或字串是否為迴文。最簡單的方式是將字串反向排列並檢查它和源字串是否相同。如果兩者相同,那麼它就是一個迴文。我們也可以用棧來完成,但是利用資料結構來解決這個問題的最簡單方法是使用雙端佇列。

```` /* * 迴文檢查器 * / var Deque = require("./雙端佇列"); // 程式碼見上文 function palindromeChecker(aString) { const deque = new Deque(); const lowerString = aString.toLocaleLowerCase().split(' ').join('') // 去除空格 console.log("lowerString", lowerString) let isEqual = true; let firstChar, lastChar; for (let i = 0; i < lowerString.length; i++){ deque.addBack(lowerString.charAt(i)) } while (deque.size() >1 && isEqual) { firstChar = deque.removeFront(); lastChar = deque.removeBack(); console.log("firstChar",firstChar) console.log("lastChar",lastChar) if (firstChar !== lastChar) { isEqual = false; } } return isEqual } console.log(palindromeChecker('abcdyydcba'))

````