摘要：所以，可以這樣寫利用數(shù)組的方法，就可以實現(xiàn)在棧頂末尾添加新的元素了。因為棧地內(nèi)部使用數(shù)組保存元素，所以數(shù)組地就是棧的長度。實現(xiàn)方法，方法用來清空棧中所有的元素。感興趣可以自行百度去了解原文鏈接行無忌的成長小屋如何用手動實現(xiàn)一個棧

棧是一種遵從后進先出（LIFO）原則的有序集合。

新添加的或待刪除的元素都保存在棧的末尾，稱為棧頂，另一端叫棧底。

在棧里，新元素都靠近棧頂，舊元素都接近棧底

在生活中也能發(fā)現(xiàn)很多棧的例子。例如，廚房里堆放的盤子，總是疊在上方的先被使用；輸入框內(nèi)容進行刪除時，總是最后輸入的先刪除；彈夾中的子彈，越后裝入的，越先發(fā)射......

首先，創(chuàng)建一個類來表示棧

function Stack () { }

我們需要選擇一種數(shù)據(jù)結構來保存棧里的元素，可以選擇數(shù)組

function Stack(){
    var items = [];     //用來保存棧里的元素
}

接下來，為棧添加一些方法

push(element(s));   //添加新元素到棧頂
pop();              //移除棧頂?shù)脑?，同時返回被移除的元素
peek();             //返回棧頂?shù)脑?，不對棧做任何修?isEmpty();          //如果棧里沒有任何元素就返回true，否則false
clear();            //移除棧里的所有元素
size();             //返回棧里的元素個數(shù),類似于數(shù)組的length屬性

我們需要實現(xiàn)的第一個方法時push。用來往棧里添加新元素，有一點很重要：該方法只添加到棧頂，也就是棧的末尾。所以，可以這樣寫：

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

利用數(shù)組的push方法，就可以實現(xiàn)在棧頂末尾添加新的元素了。

接著，來實現(xiàn)pop方法，用來實現(xiàn)移除棧里的元素。棧遵從LIFO（后進先出）原則。移出去的是最后添加進去的元素。因此，可以使用數(shù)組的pop方法。

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

這樣一來，這個棧自然就遵從了LIFO原則

現(xiàn)在，再來為這個棧添額外的輔助方法。

如果想知道棧里最后添加的元素是什么，可以用peek方法。這個方法將返回棧頂?shù)脑?/p>

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

因為類內(nèi)部是用數(shù)組保存元素的，所以這里訪問數(shù)組最后一個元素用length-1

下一個要實現(xiàn)的方法是isEmpty,如果棧為空的話，就返回true，否則返回false：

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

使用isEmpty方法，就能簡單地判斷棧內(nèi)部是否為空。

類似于數(shù)組地length屬性，我們也可以實現(xiàn)棧地length。

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

因為棧地內(nèi)部使用數(shù)組保存元素，所以數(shù)組地length就是棧的長度。

實現(xiàn)clear方法，clear方法用來清空棧中所有的元素。最簡單的實現(xiàn)方法是：

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

其實多次調(diào)用pop方法也可以，但是沒有這個方法來的簡單快捷。

最后，為了檢查棧里的內(nèi)容，還需要實現(xiàn)一個輔助方法：print。它會把棧里的元素都輸出到控制臺：

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

至此，我們就完整地創(chuàng)建了一個棧!

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());
    }
}

棧已經(jīng)創(chuàng)建好了，我們來測試一下

首先，來初始化Stack類。然后，驗證一下棧是否為空

var stack = new Stack();
console.log(stack.isEmpty());         //控制臺輸出true

接下來，往棧里面添加一下元素：

stack.push(5);
stack.push(8);

如果調(diào)用peek方法，很顯然將會輸出8，因為它是棧頂?shù)脑兀?/p>

console.log(stack.peek());            //控制臺輸出8

再添加一個元素：

stack.push(11);
console.log(stack.size());            //控制臺輸出3

我們往棧里又添加了11。如果調(diào)用size方法，輸出為3，因為棧里有三個元素（5，8和11）。如果這時候調(diào)用isEmpty方法，會看到輸出了false（因為此時棧不為空）。最后，再來往里面添加一個元素：

stack.push(15);

然后，調(diào)用兩次pop方法從棧里移除兩個元素：

stack.pop();
stack.pop();
console.log(stack.size());            //控制臺輸出2
stack.print();                        //控制臺輸出[5,8]

到這里，整個棧的功能測試完成。

使用棧來完成進制轉(zhuǎn)換。

現(xiàn)實生活中，我們主要用10進制，但在計算科學中，二進制非常重要，因為計算機里所有的內(nèi)容都是用二進制數(shù)字0和1來表示的。大學的計算機課都會先教進制轉(zhuǎn)換。以二進制為例：

function divideBy2 (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的余數(shù)，放到棧里（行{2}、{3}）。然后讓結果和2做整除（行{4}）

注：JavaScript有數(shù)字類型，但是它不會區(qū)分時整數(shù)還是浮點數(shù)。因此，要使用Math.floor函數(shù)讓除法的操作僅返回整數(shù)部分。

最后，用pop方法把棧中的元素都移除，把出棧的元素連接成字符串（行{5}）。

測試一下：

console.log(divideBy2(520));      //輸出1000001000
console.log(divideBy2(10));       //輸出1010
console.log(divideBy2(1000));     //輸出1111101000

接下來，可以很容易的修改上面的算法，使它能夠把十進制轉(zhuǎn)化為任何進制。除了讓十進制數(shù)字和2整除轉(zhuǎn)成二進制數(shù)，還可以傳入其他任意進制的基數(shù)作為參數(shù)，就像下面的算法這樣：

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;
}

在將十進制轉(zhuǎn)成二進制時，余數(shù)是0或1；在將十進制轉(zhuǎn)成八進制時，余數(shù)時0-8之間的數(shù)；但是將十進制轉(zhuǎn)成十六進制時，余數(shù)時0-9之間的數(shù)字加上A、B、C、D、E、F（對應10、11、12、13、14和15）。因此，需要對棧中的數(shù)字做個轉(zhuǎn)化才可以（行{6}、{7}）。

來測試一下輸出結果：

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

顯然是正確的。

我們用js代碼自己實現(xiàn)了棧。并且通過進制轉(zhuǎn)換的例子來實際應用了它。棧的應用實例還有很多，比如平衡圓括號和漢諾塔。感興趣可以自行百度去了解

原文鏈接：行無忌的成長小屋：如何用JavaScript手動實現(xiàn)一個棧