棧數(shù)據(jù)結(jié)構(gòu)
棧是一種遵從后進(jìn)先出（LIFO）原則的有序集合曙强。新增加的或刪除的元素都保存在棧的同一端救湖，稱作棧頂拣播，另外的一端就是棧底晾咪。在棧里面，新元素都靠近棧頂贮配，舊元素都接近棧底谍倦。
創(chuàng)建棧
我們將創(chuàng)建一個(gè)類來標(biāo)識棧。讓我們從基礎(chǔ)開始泪勒，先聲明這個(gè)類：
function Stack(){
//各種屬性和方法的聲明
}
首先昼蛀，我們需要一種數(shù)據(jù)結(jié)構(gòu)來保存棧的元素宴猾，可以選擇數(shù)組：
let items = [];
接下來，我們要為我們的棧聲明一些方法叼旋。
-
push(element(s)):添加一個(gè)（或幾個(gè)）新元素到棧頂仇哆。 -
pop():移除棧頂?shù)脑兀瑫r(shí)返回被移除的元素夫植。 -
peek():返回棧頂?shù)脑囟锾蓿粚Ｗ鋈魏蔚男薷模ㄟ@個(gè)方法不會(huì)移除棧頂?shù)脑兀瑑H僅是返回它） -
isEmpty():如果棧里沒有任何元素都返回true偷崩，否則返回false辟拷。 -
clear():移除棧里的所有元素 -
size():返回棧里的元素個(gè)數(shù)，這個(gè)方法和數(shù)組的length屬性很類似阐斜。
向棧添加元素
我們要先實(shí)現(xiàn)第一個(gè)方法push衫冻，這個(gè)方法負(fù)責(zé)往棧里添加新元素，有一點(diǎn)很重要：該方法只添加元素到棧頂谒出，也就是棧的末尾隅俘。push方法可以這樣寫：
this.push = function (element){
item.push(element);
}
因?yàn)槲覀兪褂昧藬?shù)組還是保存棧里的元素，所以可以用上一章學(xué)到了push方法來實(shí)現(xiàn)笤喳。
從棧移除元素
接下來为居，我們來實(shí)現(xiàn)pop方法。這個(gè)方法只要用來移除棧中的元素杀狡。棧遵從LIFO原則蒙畴，因此移出的是最后添加進(jìn)去的元素。因此呜象，我們可以用上一章講數(shù)組時(shí)介紹的pop方法膳凝。棧的pop方法可以這樣寫：
this.pop = function(){
return items.pop();
}
只能用push和pop方法添加和刪除棧中的元素，這樣一來恭陡，我們的棧自然就遵從了LIFO原則蹬音。
查看棧頂元素
現(xiàn)在我們的類實(shí)現(xiàn)一些額外的輔助方法，如果想知道棧里最后添加的元素是什么休玩，可以用peek方法著淆，這個(gè)方法將返回棧頂?shù)脑兀?/p>
this.peek = function(){
return items[items.length - 1];
}
如上圖中，有一個(gè)包含三個(gè)元素的棧拴疤，因此內(nèi)部數(shù)組的長度就是3.數(shù)組中最后一項(xiàng)的位數(shù)是2永部，length-1 （3-1）正是2。
檢測棧是否為空
下一步我們來實(shí)現(xiàn)isEmpty呐矾，如果棧為空的話講返回true扬舒，否則就返回false：
this.isEmpty = function (){
return items.length == 0;
}
使用isEmpty方法，我們能簡單的判斷內(nèi)部數(shù)組的長度是否為0.
那么下面我們來看一下size方法：
this.size = function (){
return items.length;
}
清空和打印棧元素
最后凫佛，我們來實(shí)現(xiàn)clear方法讲坎。clear方法用來移除棧中的所有元素孕惜，把棧清空。實(shí)現(xiàn)最簡單的方式是：
this.clear = function (){
items = [];
}
另外我們可以多調(diào)用pop方法晨炕，把數(shù)組中的元素全部移除衫画，這樣也能實(shí)現(xiàn)clear方法。
完成了瓮栗！棧已經(jīng)實(shí)現(xiàn)削罩，通過一個(gè)例子來放松一下：為了檢查棧里的內(nèi)容，我們開實(shí)現(xiàn)一個(gè)輔助方法费奸，交print弥激。他會(huì)把棧里的元素輸出到控制臺：
this.print = function (){
console.log(items.toString());
}
使用Stack類
在深入了解棧的應(yīng)用前，我們先來學(xué)習(xí)如何使用Stack類愿阐。
首先微服，我們需要初始化Stack類。然后缨历，驗(yàn)證一下棧是否為空（輸出true以蕴，因?yàn)檫€沒有往棧里添加元素）
let stack = new Stack();
console.log(stack.isEmpty()); // 輸出為true
// 向棧中添加元素
stack.push(5);
stack.push(8);
//查看棧頂元素
console.log(stack.peek()); //輸出 8
//再添加一個(gè)元素
stack.push(11);
console.log(stack.size()); // 輸出 3
console.log(stack.isEmpty()); //輸出false
//再添加一個(gè)元素
stack.push(15);
現(xiàn)在我們直觀的看一下我們對棧的操作，以及棧的當(dāng)前狀態(tài)：
然后調(diào)用兩次pop函數(shù)來移除2個(gè)元素：
stack.pop();
stack.pop();
console.log(stack.size()); // 輸出2
stack.print(); // 輸出[5,8]
現(xiàn)在我們直觀的看一下我們對棧的操作辛孵，以及棧的當(dāng)前狀態(tài)：
ECMAScript 6 和stack類
我們花時(shí)間分析一下代碼丛肮，看看是都能用ECMAScript6（ES6）的新功能來改進(jìn)。
我們創(chuàng)建一個(gè)可以當(dāng)做類來使用Stack函數(shù)魄缚。JavaScript函數(shù)都有構(gòu)造函數(shù)宝与，可以用來模擬類的行為。我們生命了一個(gè)私有的items變量冶匹，它只能被Stack函數(shù)/類訪問习劫。然而，這個(gè)方法為每個(gè)類的實(shí)例都創(chuàng)建一個(gè)items變量的副本徙硅。因此榜聂，如果要?jiǎng)?chuàng)建多個(gè)Stack實(shí)例搞疗，它就不太適合了嗓蘑。
用ES6 語法聲明Stack類
我們看一下下面的代碼：
class Stack {
constructor(){
this.item = []; //{1}
}
push(element){
this.items.push(element);
}
//其他方法
}
我們只是用ES6的簡化語法那Stack函數(shù)轉(zhuǎn)化成Stack類。這種方法不能像其他語言（Java匿乃，C++桩皿，C#）一樣直接在類里面聲明變量，只能在類的構(gòu)造函數(shù)constructor里聲明在類的其他函數(shù)里用this.nameofVariable就可任意引用這個(gè)變量幢炸。
盡管代碼看起來更簡潔泄隔，更漂亮，變量items卻是公共的宛徊。ES6的類是基于原型的佛嬉。雖然基本原型的類比基本函數(shù)的類更節(jié)省內(nèi)存逻澳，也更適合創(chuàng)造多個(gè)實(shí)例，卻不能夠聲明私有屬性（變量）或方法暖呕。而且斜做，在這個(gè)情況下，我們希望Stack類的用戶只能訪問暴露給類的方法湾揽。否則瓤逼，就有可能從棧的中間移除元素，這不是我們希望看到的库物。
看一下ES6的限定作用域Symbol實(shí)現(xiàn)類
1.用ES6的限定作用域Symbol實(shí)現(xiàn)類
ES6增加了一種叫做symbol的基本類型霸旗，它是不可變的，可以用作對象的屬性戚揭，看看怎么用它來在Stack類中聲明items屬性：
let _item = Symbol(); //(1)
class Stack {
constructor (){
this[_items] = []; // (2)
}
// Stack 方法
}
在上面的代碼中诱告，我們聲明了Symbol類型的變量_items（行1），在類的constructor函數(shù)中初始化它的值（行2）毫目。要訪問_items,只需把所有的this.items都換成this[_items]蔬啡。
這種方法創(chuàng)建了一個(gè)私有屬性，因?yàn)?code>ES6新增的Object.getOwnPropertySymbol方法能夠取到類里面聲明的所有Symbol屬性镀虐，下面是一個(gè)破壞Stack類的例子：
let stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); //1
console.log(objectSymbols); //[Symbol()]
console.log(objectSymbols[0]); //Symbol()
console.log(objectSymbols[0].push(1));
stack.print(); // 輸出：5,8,1
上面的代碼我們可以看到箱蟆，訪問stack[objectSymbols[0]]是可以得到_items.并且，_items屬性是一個(gè)數(shù)組刮便，可以進(jìn)行任何的數(shù)組操作空猜，比如從中間刪除或是添加元素。我們操作的是棧恨旱，不應(yīng)該出現(xiàn)這樣的操作辈毯。
2.ES6是的weakMap
有一種數(shù)據(jù)類型可以確保屬性是私有的，這就是WeakMap搜贤。我們會(huì)在以后深入探討Map這種數(shù)據(jù)結(jié)構(gòu)谆沃，現(xiàn)在只需要知道weakMap可以用來存儲鍵值對，其中鍵是對象仪芒，值可以是任意數(shù)據(jù)類型唁影。
如果用weakMap來存儲items變量，stack就是這樣的：
const items = new weakMap(); //聲明一個(gè)weakMap類型的變量items
class Stack{
constructor(){
items.set(this, []); //以this為鍵掂名，把代表?xiàng)５臄?shù)組存入items
}
push(element){
let s = items.get(this); //從weekMap中取出值
s.push(element)
}
pop(){
let s = items.get(this);
let r = s.pop();
return r;
}
}
在上面的代碼中据沈，items在stack類是真正的私有屬性，但是還有一件事要去做饺蔑。items現(xiàn)在仍然是在Stack類以外聲明的锌介，因此誰都可以來修改Stack這個(gè)類，這個(gè)時(shí)候我們需要一個(gè)閉包(外層函數(shù))把Stack類包起來沒這樣就只能在這個(gè)函數(shù)里訪問weakMap().
let Stack = (function(){
const items = new weakMap();
class Stack{
constructor(){
items.set(this, []);
}
//其他方法
return Stack;
})（）;
用棧解決的問題
從十進(jìn)制到二進(jìn)制
在現(xiàn)實(shí)生活中，我們主要使用十進(jìn)制孔祸，但是在科學(xué)計(jì)算中隆敢，二進(jìn)制是十分重要的，因?yàn)橛?jì)算機(jī)中的所有的內(nèi)容都是用二進(jìn)制來表現(xiàn)的（0和1）崔慧，沒有十進(jìn)制和二進(jìn)制的相互轉(zhuǎn)換能力筑公，與計(jì)算機(jī)的交流就會(huì)十分的困難。要把十進(jìn)制轉(zhuǎn)換成二進(jìn)制尊浪，我們可以將改十進(jìn)制數(shù)字和2整除（二進(jìn)制就是滿二進(jìn)一）匣屡，知道結(jié)果為0為止，現(xiàn)在我們舉個(gè)栗子拇涤，把十進(jìn)制數(shù)字10轉(zhuǎn)換成二進(jìn)制的數(shù)組捣作，大概的過程就是這樣的：
大學(xué)的計(jì)算機(jī)課程一般都會(huì)先教這個(gè)進(jìn)制轉(zhuǎn)換。下面對應(yīng)的算法描述：
function divideby2(decNumber){
let remStack = new Stack(),rem,binaryString = '';
while (decNumber > 0){
rem = Math.floor(decNumber % 2);
remStack.push(rem);
decNumber = Math.floor(decNumber / 2);
}
while(!remStack.isEmpty()){
binaryString += remStack.pop().toString();
}
return binaryString ;
}
從上面的算法中鹅士，我們很容易進(jìn)行修改券躁，讓十進(jìn)制可以轉(zhuǎn)換成任意進(jìn)制，除了讓十進(jìn)制和2整除轉(zhuǎn)換為二進(jìn)制掉盅，還可以傳入其他任意進(jìn)制的基數(shù)為參數(shù)也拜，就像下面的算法是這樣的：
function baseConverter(decNumber , base){
let remStack = new Stack(),
rem,
binaryString = '';
digits = '0123456789ABCDEF';
while (decNumber > 0){
rem = Math.floor(decNumber % base);
remStack.push(rem);
decNumber = Math.floor(decNumber / base);
}
while(!remStack.isEmpty()){
binaryString += remStack.pop().toString();
}
return binaryString ;
}
