JavaScript數據結構與算法之棧詳解
1.認識棧
棧:(stack)又名堆棧,它是一種運算受限的線性表。遵循後進先出(LIFO)
棧頂:限定僅在表尾進行插入和刪除操作的線性表,
棧底:限定僅在表頭進行插入和刪除操作的線性表。
進棧:向一個棧插入新元素又稱作進棧、入棧或壓棧,它是把新元素放到棧頂元素的上面,使之成為新的棧頂元素;
出棧:從一個棧刪除元素又稱作出棧或退棧,它是把棧頂元素刪除掉,使其相鄰的元素成為新的棧頂元素
2.面向過程方法源碼編寫棧
2.1思考
面向過程是什麼:
面向過程就是將解決問題的步驟分析出來,
然後用函數實現,
隻要一步一步的執行調用他就可以瞭。
2.2需要實現的方法
- push(element)添加一個或多個元素到棧頂
- pop()刪除錢頂的元素,並返回移除的元素
- peek()返回棧頂的元素
- isEmpty()用於判斷棧是否為空,空則為空
- clear()用於清空棧的元素
- size()用於返回棧中元素的個數
在實現之前我們思考一下我們怎麼實現
首先我們借用數組的方法來實現,所以我們需要創建
一個空數組來模擬棧
2.3源碼實現,並調用類
構建一個類,用數組來模擬,
在類中書寫各種方法
部分調用數組的方法。
總的來說就是用類來包裝
數組的方法來實現棧的模擬
class Stack { constructor() { this.item = [] } push(element) { this.item.push(element) } pop() { return this.item.pop() } peek() { return this.item[this.item.length - 1] } isEmpty() { return this.item.length === 0 } clear() { this.item = [] size() { return this.item.length } } //實例化Stack類 const stack = new Stack() stack.push(4) stack.push(6) console.log( stack.pop()) console.log(stack.peek()) console.log(stack.isEmpty()) console.log(stack.size())
運行結果:
3.用面向對象的方法來源碼書寫
3.1思考
面向對象:
就是將構建問題的事物,分解成若幹個對象,
建立對象不是為瞭完成某個步驟,而是為瞭
描述某個事物在解決問題過程的行為
3.2需要實現的方法
- push(element)添加一個或多個元素到棧頂
- pop()刪除錢頂的元素,並返回移除的元素
- peek()返回棧頂的元素
- isEmpty()用於判斷棧是否為空,空則為空
- clear()用於清空棧的元素
- size()用於返回棧中元素的個數
- toString()用於將棧以字符串的形式打印
那麼在實現這個類,我們用對象來模擬棧
3.3源碼及使用類
class Stack { constructor() { this.count=0 this.items = {} } push(element) { this.items[this.count]=element 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 } return this.items[this.count-1] } isEmpty() { return this.count===0 } clear() { this.items={} this.count=0 } size() { return this.count } toString(){ if(this.isEmpty()){ return undefined } let objectString=`${this.items[0]}` for(let i=1;i<this.count;i++){ objectString=`${objectString},${this.items[i]}` } return objectString } } const stack = new Stack() stack.push(23) stack.push(34) stack.push(80) console.log( stack.pop()) console.log(stack.peek()) console.log(stack.isEmpty()) console.log(stack.size()) console.log(stack.toString())
在使用對象來模擬棧時,采用瞭鍵:值的方式
來存儲數據,比如this.items[this.count]=element
在這個結構中用this.count來記錄棧的大小,
當我們向裡面插入一個數字時,就分配count為鍵
插入的值為值。這個時候就需要將this.count++.
關於pop()與peek(),toString()方法都需要
先判斷棧是否為空,如果為空則返回undefined。
4.總結
- 瞭解瞭面向對象與面向過程
- 掌握瞭兩種方式用什麼來模擬棧
- 對棧模擬進行源碼設計
到此這篇關於JavaScript數據結構與算法之棧詳解的文章就介紹到這瞭,更多相關JS棧詳解內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!