快捷導(dǎo)航

JavaScipt中棧的實(shí)現(xiàn)方法

更新時(shí)間：2016年02月17日 16:25:08 投稿：lijiao

這篇文章主要介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之棧詳解,本文講解了對(duì)棧的操作、對(duì)棧的實(shí)現(xiàn)實(shí)例等內(nèi)容,需要的朋友可以參考下

接下來(lái)就是數(shù)據(jù)結(jié)構(gòu)的第一部分，棧。
棧是一種遵從后進(jìn)先出原則(LIFO,全稱(chēng)為L(zhǎng)ast In First Out)的有序集合。棧頂永遠(yuǎn)是最新的元素。
舉個(gè)例子就是:棧就像放在箱子里的一疊書(shū) 你要拿下面的書(shū)先要把上面的書(shū)拿開(kāi)。(當(dāng)然，你不能先拿下面的書(shū))
看圖示也可明白。

JavaScipt中棧的實(shí)現(xiàn)
首先，創(chuàng)建一個(gè)構(gòu)造函數(shù)。

/**
 * 棧的構(gòu)造函數(shù)
 */
function Stack() {

 // 用數(shù)組來(lái)模擬棧
 var item = [];
}

棧需要有如下的方法:

push(element(s)): 添加幾個(gè)元素到棧頂
pop(): 移除并返回棧頂元素
peek(): 返回棧頂元素
isAmpty: 檢查棧是否為空，為空則返回true
clear: 移除棧中所有元素
size: 返回棧中元素個(gè)數(shù)。
print: 以字符串顯示棧中所有內(nèi)容

push方法的實(shí)現(xiàn)
說(shuō)明: 需要往棧中添加新元素，元素位置在隊(duì)列的末尾。也就是說(shuō)，我們可以用數(shù)組的push方法來(lái)模擬實(shí)現(xiàn)。
實(shí)現(xiàn):

/**
 * 將元素送入棧，放置于數(shù)組的最后一位
 * @param {Any} element 接受的元素，不限制類(lèi)型
 */
this.push = function(element) {
 items.push(element);
};

pop方法的實(shí)現(xiàn)
說(shuō)明: 需要把棧頂元素彈出，同時(shí)返回被彈出的值?？梢杂脭?shù)組的pop方法來(lái)模擬實(shí)現(xiàn)。
實(shí)現(xiàn):

/**
 * 彈出棧頂元素
 * @return {Any} 返回被彈出的值
 */
this.pop = function() {
 return items.pop();
};

peek方法的實(shí)現(xiàn)
說(shuō)明: 查看棧頂元素，可以用數(shù)組長(zhǎng)度來(lái)實(shí)現(xiàn)。
實(shí)現(xiàn):

/**
 * 查看棧頂元素
 * @return {Any} 返回棧頂元素
 */
this.peek = function() {
 return items[items.length - 1];
}

其余方法的實(shí)現(xiàn)
說(shuō)明: 前三個(gè)是棧方法的核心，其余方法則在此一次性列出。因?yàn)橄挛囊v的隊(duì)列，會(huì)與這部分有很大重合。
實(shí)現(xiàn):

/**
 * 確定棧是否為空
 * @return {Boolean} 若棧為空則返回true,不為空則返回false
 */
this.isAmpty = function() {
 return items.length === 0
};

/**
 * 清空棧中所有內(nèi)容
 */
this.clear = function() {
 items = [];
};

/**
 * 返回棧的長(zhǎng)度
 * @return {Number} 棧的長(zhǎng)度
 */
this.size = function() {
 return items.length;
};

/**
 * 以字符串顯示棧中所有內(nèi)容
 */
this.print = function() {
 console.log(items.toString());
};

實(shí)際應(yīng)用
棧的實(shí)際應(yīng)用比較多，書(shū)中有個(gè)十進(jìn)制轉(zhuǎn)二進(jìn)制的函數(shù)。(不懂二進(jìn)制怎么算的話可以百度)下面是函數(shù)的源代碼。
原理就是輸入要轉(zhuǎn)換的數(shù)字，不斷的除以二并取整。并且最后運(yùn)用while循環(huán)，將棧中所有數(shù)字拼接成字符串輸出。

/**
 * 將10進(jìn)制數(shù)字轉(zhuǎn)為2進(jìn)制數(shù)字
 * @param {Number} decNumber 要轉(zhuǎn)換的10進(jìn)制數(shù)字
 * @return {Number}      轉(zhuǎn)換后的2進(jìn)制數(shù)字
 */
function divideBy2(decNumber) {

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

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

 while (!remStack.isAmpty()) {
  binaryString += remStack.pop().toString();
 }

 return binaryString;
};

到此而言，棧的學(xué)習(xí)就告一段落了，希望對(duì)大家學(xué)習(xí)javascript中棧的實(shí)現(xiàn)方法有所幫助。

您可能感興趣的文章: