首頁  >  文章  >  web前端  >  如何用JavaScript實作一個棧

如何用JavaScript實作一個棧

不言
不言原創
2018-07-11 16:54:124599瀏覽

這篇文章主要介紹了關於如何用JavaScript實現一個棧,有著一定的參考價值,現在分享給大家,有需要的朋友可以參考一下

什麼是棧(Stack)

如何用JavaScript實作一個棧

  • 堆疊是一種遵從後進先出(LIFO)原則的有序集合。

  • 新加入的或待刪除的元素都保存在堆疊的結尾,稱為堆疊頂,另一端叫堆疊底部。

  • 在堆疊裡,新元素都靠近棧頂,舊元素都接近棧底

現實中的範例

# #在生活中也能發現很多堆疊的例子。例如,廚房裡堆疊的盤子,總是疊在上方的先被使用;輸入框內容進行刪除時,總是最後輸入的先刪除;彈夾中的子彈,越後裝入的,越先發射.. ....

手動實作一個堆疊首先,建立一個類別來表示堆疊

function Stack () { }

我們需要選擇一個資料結構來保存堆疊裡的元素,可以選擇數組<pre class="brush:php;toolbar:false">function Stack(){     var items = [];     //用来保存栈里的元素 }</pre>接下來,為堆疊添加一些方法

push(element(s));   //添加新元素到栈顶
pop();              //移除栈顶的元素,同时返回被移除的元素
peek();             //返回栈顶的元素,不对栈做任何修改
isEmpty();          //如果栈里没有任何元素就返回true,否则false
clear();            //移除栈里的所有元素
size();             //返回栈里的元素个数,类似于数组的length属性

我們需要實作的第一個方法時push。用來往棧裡加入新元素,有一點很重要:方法只加到棧頂,也就是棧的末端。所以,可以這樣寫:

this.push = function (element) {
    items.push(element);
}

利用數組的push方法,就可以實現在堆疊頂部末尾添加新的元素了。

接著,來實作

pop

方法,用來實作移除堆疊裡的元素。棧遵從LIFO(後進先出)原則。移出去的是最後加進去的元素。因此,可以使用陣列的pop方法。

this.pop = function () {
    return items.pop();
}

這樣一來,這個堆疊自然就遵從了LIFO原則現在,再來為這個堆疊添額外的輔助方法。

如果想知道堆疊裡最後加入的元素是什麼,可以用

peek

方法。這個方法會回傳棧頂的元素<pre class="brush:php;toolbar:false">this.peek = function () {     return items[items.length-1]; }</pre>因為類別內部是用陣列保存元素的,所以這裡存取數組最後一個元素用

length-1

下一個要實作的方法是

isEmpty

,如果堆疊為空的話,就回傳true,否則回傳false:

this.isEmpty = function () {
    return items.length == 0;
}

使用isEmpty方法,就能簡單地判斷堆疊內部是否為空。

類似於陣列地length屬性,我們也可以實作堆疊地length。

this.size = function () {
    return items.length;
}

因為堆疊地內部使用陣列保存元素,所以陣列地length就是堆疊的長度。

實作

clear

方法,clear方法用來清空堆疊中所有的元素。最簡單的實作方法是:

this.clear = function () {
    items = [];
}

其實多次呼叫pop方法也可以,但沒有這個方法來的簡單快速。

最後,為了檢查堆疊裡的內容,還需要實作一個輔助方法:

print

。它會把堆疊裡的元素都輸出到控制台:

this.print = function () {
    console.log(items.toString());
}

至此,我們就完整地創建了一個

堆疊

!

堆疊的完整程式碼

function Stack(){

    var items = [];     //用来保存栈里的元素

    this.push = function (element) {
        items.push(element);
    }

    this.pop = function () {
        return items.pop();
    }

    this.peek = function () {
        return items[items.length-1];
    }

    this.isEmpty = function () {
        return items.length == 0;
    }

    this.size = function () {
        return items.length;
    }

    this.clear = function () {
        items = [];
    }

    this.print = function () {
        console.log(items.toString());
    }
}

使用Stack類別

堆疊已經建立好了,我們來測試一下如何用JavaScript實作一個棧

#首先,來初始化Stack類別。然後,驗證一下堆疊是否為空

var stack = new Stack();
console.log(stack.isEmpty());         //控制台输出true
接下來,往堆疊裡面加入元素:
stack.push(5);
stack.push(8);
如果呼叫peek方法,很明顯將會輸出8,因為它是堆疊頂端的元素:

console.log(stack.peek());            //控制台输出8
再增加一個元素:

stack.push(11);
console.log(stack.size());            //控制台输出3
我們往堆疊裡又加入了11。如果呼叫size方法,輸出為3,因為堆疊裡有三個元素(5,8和11)。如果這時候呼叫isEmpty方法,會看到輸出了false(因為此時堆疊不為空)。最後,再來往裡面加入一個元素:

stack.push(15);
然後,呼叫兩次pop方法從堆疊中移除兩個元素:###
stack.pop();
stack.pop();
console.log(stack.size());            //控制台输出2
stack.print();                        //控制台输出[5,8]
###到這裡,整個堆疊的功能測試完成。 ######用堆疊來解決問題######使用堆疊來完成進位轉換。 ######現實生活中,我們主要用10進制,但在計算科學中,二進制非常重要,因為電腦裡所有的內容都是用二進制數字0和1來表示的。大學的電腦課都會先教進制轉換。以二進位為例:############
function pideBy2 (decNumber) {

    var remStack = new Stack(),
    rem,
    binaryString = '';

    while (decNumber>0) {  //{1}
        rem = Math.floor(decNumber % 2);  //{2}
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / 2);  //{4}
    }

    while (!remStack.isEmpty()) {  //{5}
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}
###這段程式碼裡,當結果滿足和2做整除的條件時,(行{1}),我們會得到目前結果和2的餘數,放到堆疊裡(行{2}、{3})。然後讓結果和2做整除(行{4})######註:JavaScript有數字型,但它不會區分時整數還是浮點數。因此,要使用Math.floor函數讓除法的運算只傳回整數部分。 ######最後,用pop方法把堆疊中的元素都移除,把出棧的元素連接成字串(行{5})。 ######測試一下:###
console.log(pideBy2(520));      //输出1000001000
console.log(pideBy2(10));       //输出1010
console.log(pideBy2(1000));     //输出1111101000
###接下來,可以輕鬆的修改上面的演算法,使它能夠把十進位轉換為任何進位。除了讓十進制數字和2整除轉成二進制數,還可以傳入其他任意進制的基數作為參數,就像下面的演算法一樣:###
function baseConverter (decNumber, base) {

    var remStack = new Stack(),
    rem,
    baseString = '';
    digits = '0123456789ABCDEF';     //{6}

    while (decNumber>0) {  
        rem = Math.floor(decNumber % base);
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / base);
    }

    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()];  //{7}
    }

    return baseString;
}

在将十进制转成二进制时,余数是0或1;在将十进制转成八进制时,余数时0-8之间的数;但是将十进制转成十六进制时,余数时0-9之间的数字加上A、B、C、D、E、F(对应10、11、12、13、14和15)。因此,需要对栈中的数字做个转化才可以(行{6}、{7})。

来测试一下输出结果:

console.log(baseConverter(1231,2));      //输出10011001111
console.log(baseConverter(1231,8));      //输出2317
console.log(baseConverter(1231,16));     //输出4CF

显然是正确的。

小结

我们用js代码自己实现了栈。并且通过进制转换的例子来实际应用了它。栈的应用实例还有很多,比如平衡圆括号和汉诺塔。

以上就是本文的全部内容,希望对大家的学习有所帮助,更多相关内容请关注PHP中文网!

相关推荐:

如何利用js fetch实现ping效果

以上是如何用JavaScript實作一個棧的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn