JavaScript資料結構與演算法—— 棧
我們可以在陣列的任何位置上刪除或者新增元素,但有時候我們還需要在元素的新增或刪除時有更多控制的資料結構,有兩種資料結構類似於陣列,但在新增或刪除元素時更為可控,它們就是棧和佇列。
本節主要介紹棧。
1.棧資料結構
棧是一種遵循後進先出(LIFO)原則的有序集合。新新增的或待刪除的元素都儲存在棧的同一端,叫做棧頂,另一端叫棧底。在棧中,新元素靠近棧頂,舊元素接近棧底。如下圖所示:
2.建立棧
// 首先建立一類表示棧 function Stack(){ let items = []; // 選擇陣列來儲存棧中的元素 //各種屬性和方法 }
下面要為棧宣告一些方法:
push()//新增一個或多個新元素到棧頂 pop()//移除棧頂元素,同時返回被移除的元素 peek()// 僅僅返回棧頂元素,不對棧做任何修改 isEmpty()//如果棧中沒有元素返回true,否則返回false clear()// 移除棧中所有元素 size()// 返回棧中元素的個數(和陣列length類似)
2.1 向棧新增元素
this.push() = function(element) { items.push(element); }
2.2 從棧移除元素
this.pop = function() { items.pop(); }
2.3 檢視棧頂元素
this.peek = function() { return items[items.length - 1]; }
2.4 檢視棧是否為空
this.isEmpty = function(){ return items.length === 0; } this.size = function() { return items.lenght; }
2.5 清空和列印棧元素
this.clear = function() { items = []; } this.print = function() { console.log(items.toString()); }
經過上述的方法的新增,我們就完整的建立了一了個棧 Stack。
3.棧的應用—十進位制轉N進位制
首先我們寫出將十進位制轉為二進位制:
function divideBy2(decNum) { var remStack = new Stack(), rem, binaryString = ''; // 將十進位制數除2的餘數放入一個stack中 while(decNum > 0) { // 取餘 rem = Math.floor(decNum % 2); // 入棧 remStack.push(rem); decNum = Math.floor(decNum / 2); } // 從棧中取出轉化為字串然後連線起來構成二進位制 while(!remStack.isEmpty()) { // 出棧 binaryString += remStack.pop().toString(); } return binaryString; }
下面十進位制轉化N進位制演算法
function divideByN(decNum, n) { var remStack = new Stack(), rem, binaryString = '', digits = '0123456789ABCDEF'; // 將十進位制數除N的餘數放入一個stack中 while(decNum > 0) { // 取餘 rem = Math.floor(decNum % n); // 入棧 remStack.push(rem); decNum = Math.floor(decNum / n); } // 從棧中取出轉化為字串然後連線起來構成二進位制 while(!remStack.isEmpty()) { // 出棧 使用digits方便在16進制中做個對應轉化 binaryString += digits[remStack.pop()]; } return binaryString; }