資訊專欄INFORMATION COLUMN
摘要：一實現(xiàn)一個棧類基于堆棧的特性，可以用數(shù)組做線性表進行存儲。出棧出棧同樣是利用數(shù)組的方法，在數(shù)組尾部推出數(shù)據(jù)。聚合最后，將所有功能聚合后，如下所示，一個堆棧的數(shù)據(jù)結(jié)構(gòu)就搞定了。堆棧的經(jīng)典算法應用，首推就是漢諾塔。
棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。一、實現(xiàn)一個棧類Stack
基于堆棧的特性，可以用數(shù)組做線性表進行存儲。
初始化Stack類的結(jié)構(gòu)如下：
function Stack(){
this.space = [];
}
Stack.prototype = {
constructor: Stack,
/* 接口code */
};
接下來，就是在原型上，對入棧、出棧、清空棧、讀取棧頂、讀取整個棧數(shù)據(jù)這幾個接口的實現(xiàn)。
Stack類默認以數(shù)組頭部做棧底，尾部做棧頂。
入棧可以利用js數(shù)組的push方法，在數(shù)組尾部壓入數(shù)據(jù)。
Stack.prototype = {
push: function(value){
return this.space.push(value);
}
}
1.2 出棧 pop
出棧同樣是利用js數(shù)組的pop方法，在數(shù)組尾部推出數(shù)據(jù)。
Stack.prototype = {
pop: function(){
return this.space.pop();
}
}
1.3 清空棧 clear
清空棧相對簡單，將存儲數(shù)據(jù)的數(shù)組重置為空數(shù)組即可。
Stack.prototype = {
clear: function(){
this.space = [];
}
}
1.4 讀取棧頂readTop
讀取棧頂數(shù)據(jù)，采用數(shù)組下標的方式進行獲取。帶來的一個好處就是：下標超出數(shù)組有效范圍時，返回值為undefined。
Stack.prototype = {
readTop: function(){
return this.space[this.space.length - 1];
}
}
1.4 讀取整個棧read
讀取整個棧數(shù)據(jù)，直接返回當前數(shù)組即可。
Stack.prototype = {
read: function(){
return this.space;
}
}
1.5 聚合
最后，將所有功能聚合后，如下所示，一個堆棧的數(shù)據(jù)結(jié)構(gòu)就搞定了。
function Stack(){
this.space = [];
}
Stack.prototype = {
constructor: Stack,
push: function(value){
return this.space.push(value);
},
pop: function(){
return this.space.pop();
},
clear: function(){
this.space = [];
},
readTop: function(){
return this.space[this.space.length - 1];
},
read: function(){
return this.space;
}
};
二、實戰(zhàn)
學數(shù)據(jù)結(jié)構(gòu)和算法是為了更好、更高效率地解決工程問題。
這里學以致用，提供了幾個真實的案例，來體會下數(shù)據(jù)結(jié)構(gòu)和算法的魅力:)
當前案例，將用堆棧來實現(xiàn)數(shù)組的反轉(zhuǎn)功能。
function reverse(arr){
var ArrStack = new Stack();
for(var i = arr.length - 1; i >= 0; i--){
ArrStack.push(arr[i]);
}
return ArrStack.read();
}
如代碼所示，可分為以下幾個步驟：
實例化一個堆棧用于存儲數(shù)據(jù)
將傳入的數(shù)組進行倒序遍歷，并逐個壓入堆棧
最后使用read接口，輸出數(shù)據(jù)
好像很簡單，不用擔心，復雜的在后面:)
2.2 十進制轉(zhuǎn)換為二進制數(shù)值轉(zhuǎn)換進制的問題，是堆棧的小試牛刀。
講解轉(zhuǎn)換方法前，先來看一個小例子：
將十進制的13轉(zhuǎn)換成二進制
2 | 13 1
￣￣￣
2 | 6 0
￣￣￣
2 | 3 1
￣￣￣￣
1 1
如上所示：13的二進制碼為1101。
將手工換算，變成堆棧存儲，只需將對2取余的結(jié)果依次壓入堆棧保存，最后反轉(zhuǎn)輸出即可。
function binary(number){
var tmp = number;
var ArrStack = new Stack();
if(number === 0){
return 0;
}
while(tmp){
ArrStack.push(tmp % 2);
tmp = parseInt(tmp / 2, 10);
}
return reverse(ArrStack.read()).join("");
}
binary(14); // 輸出=> "1110"
binary(1024); // 輸出=> "10000000000"
2.3 表達式求值
這個案例，其實可以理解為簡化版的eval方法。
案例內(nèi)容是對1+7*(4-2)的求值。
進入主題前，有必要先了解以下的數(shù)學理論：
中綴表示法（或中綴記法）是一個通用的算術或邏輯公式表示方法， 操作符是以中綴形式處于操作數(shù)的中間（例：3 + 4）。
逆波蘭表示法（Reverse Polish notation，RPN，或逆波蘭記法），是一種是由波蘭數(shù)學家揚·武卡謝維奇1920年引入的數(shù)學表達式方式，在逆波蘭記法中，所有操作符置于操作數(shù)的后面，因此也被稱為后綴表示法。逆波蘭記法不需要括號來標識操作符的優(yōu)先級。
常規(guī)中綴記法的“3 - 4 + 5”在逆波蘭記法中寫作“3 4 - 5 +”
調(diào)度場算法（Shunting Yard Algorithm）是一個用于將中綴表達式轉(zhuǎn)換為后綴表達式的經(jīng)典算法，由艾茲格·迪杰斯特拉引入，因其操作類似于火車編組場而得名。
提前說明，這只是簡單版實現(xiàn)。所以規(guī)定有兩個：
數(shù)字要求為整數(shù)
不允許表達式中出現(xiàn)多余的空格
實現(xiàn)代碼如下：
function calculate(exp){
var valueStack = new Stack(); // 數(shù)值棧
var operatorStack = new Stack(); // 操作符棧
var expArr = exp.split(""); // 切割字符串表達式
var FIRST_OPERATOR = ["+", "-"]; // 加減運算符
var SECOND_OPERATOR = ["*", "/"]; // 乘除運算符
var SPECIAL_OPERATOR = ["(", ")"]; // 括號
var tmp; // 臨時存儲當前處理的字符
var tmpOperator; // 臨時存儲當前的運算符
// 遍歷表達式
for(var i = 0, len = expArr.length; i < len; i++){
tmp = expArr[i];
switch(tmp){
case "(":
operatorStack.push(tmp);
break;
case ")":
// 遇到右括號，先出棧括號內(nèi)數(shù)據(jù)
while( (tmpOperator = operatorStack.pop()) !== "(" &&
typeof tmpOperator !== "undefined" ){
valueStack.push(calculator(tmpOperator, valueStack.pop(), valueStack.pop()));
}
break;
case "+":
case "-":
while( typeof operatorStack.readTop() !== "undefined" &&
SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 &&
(SECOND_OPERATOR.indexOf(operatorStack.readTop()) !== -1 || tmp != operatorStack.readTop()) ){
// 棧頂為乘除或相同優(yōu)先級運算，先出棧
valueStack.push(calculator(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
}
operatorStack.push(tmp);
break;
case "*":
case "/":
while( typeof operatorStack.readTop() != "undefined" &&
FIRST_OPERATOR.indexOf(operatorStack.readTop()) === -1 &&
SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 &&
tmp != operatorStack.readTop()){
// 棧頂為相同優(yōu)先級運算，先出棧
valueStack.push(calculator(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
}
operatorStack.push(tmp);
break;
default:
valueStack.push(tmp);
}
}
// 處理棧內(nèi)數(shù)據(jù)
while( typeof (tmpOperator = operatorStack.pop()) !== "undefined" ){
valueStack.push(calculator(tmpOperator, valueStack.pop(), valueStack.pop()));
}
return valueStack.pop(); // 將計算結(jié)果推出
/*
@param operator 操作符
@param initiativeNum 主動值
@param passivityNum 被動值
*/
function calculator(operator, passivityNum, initiativeNum){
var result = 0;
initiativeNum = typeof initiativeNum === "undefined" ? 0 : parseInt(initiativeNum, 10);
passivityNum = typeof passivityNum === "undefined" ? 0 : parseInt(passivityNum, 10);
switch(operator){
case "+":
result = initiativeNum + passivityNum;
console.log(`${initiativeNum} + ${passivityNum} = ${result}`);
break;
case "-":
result = initiativeNum - passivityNum;
console.log(`${initiativeNum} - ${passivityNum} = ${result}`);
break;
case "*":
result = initiativeNum * passivityNum;
console.log(`${initiativeNum} * ${passivityNum} = ${result}`);
break;
case "/":
result = initiativeNum / passivityNum;
console.log(`${initiativeNum} / ${passivityNum} = ${result}`);
break;
default:;
}
return result;
}
}
實現(xiàn)思路：
采用調(diào)度場算法，對中綴表達式進行讀取，對結(jié)果進行合理運算。
臨界點采用operatorStack.readTop() !== "undefined"進行判定。有些書采用#做結(jié)束標志，個人覺得有點累贅。
將字符串表達式用split進行拆分，然后進行遍歷讀取，壓入堆棧。有提前要計算結(jié)果的，進行對應的出棧處理。
將計算部分結(jié)果的方法，封裝為獨立的方法calculator。由于乘除運算符前后的數(shù)字，在運算上有區(qū)別，所以不能隨意調(diào)換位置。
2.4 中綴表達式轉(zhuǎn)換為后綴表達式（逆波蘭表示法）逆波蘭表示法，是一種對計算機友好的表示法，不需要使用括號。
下面案例，是對上一個案例的變通，也是用調(diào)度場算法，將中綴表達式轉(zhuǎn)換為后綴表達式。
function rpn(exp){
var valueStack = new Stack(); // 數(shù)值棧
var operatorStack = new Stack(); // 操作符棧
var expArr = exp.split("");
var FIRST_OPERATOR = ["+", "-"];
var SECOND_OPERATOR = ["*", "/"];
var SPECIAL_OPERATOR = ["(", ")"];
var tmp;
var tmpOperator;
for(var i = 0, len = expArr.length; i < len; i++){
tmp = expArr[i];
switch(tmp){
case "(":
operatorStack.push(tmp);
break;
case ")":
// 遇到右括號，先出棧括號內(nèi)數(shù)據(jù)
while( (tmpOperator = operatorStack.pop()) !== "(" &&
typeof tmpOperator !== "undefined" ){
valueStack.push(translate(tmpOperator, valueStack.pop(), valueStack.pop()));
}
break;
case "+":
case "-":
while( typeof operatorStack.readTop() !== "undefined" &&
SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 &&
(SECOND_OPERATOR.indexOf(operatorStack.readTop()) !== -1 || tmp != operatorStack.readTop()) ){
// 棧頂為乘除或相同優(yōu)先級運算，先出棧
valueStack.push(translate(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
}
operatorStack.push(tmp);
break;
case "*":
case "/":
while( typeof operatorStack.readTop() != "undefined" &&
FIRST_OPERATOR.indexOf(operatorStack.readTop()) === -1 &&
SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 &&
tmp != operatorStack.readTop()){
// 棧頂為相同優(yōu)先級運算，先出棧
valueStack.push(translate(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
}
operatorStack.push(tmp);
break;
default:
valueStack.push(tmp);
}
}
while( typeof (tmpOperator = operatorStack.pop()) !== "undefined" ){
valueStack.push(translate(tmpOperator, valueStack.pop(), valueStack.pop()));
}
return valueStack.pop(); // 將計算結(jié)果推出
/*
@param operator 操作符
@param initiativeNum 主動值
@param passivityNum 被動值
*/
function translate(operator, passivityNum, initiativeNum){
var result = "";
switch(operator){
case "+":
result = `${initiativeNum} ${passivityNum} +`;
console.log(`${initiativeNum} + ${passivityNum} = ${result}`);
break;
case "-":
result = `${initiativeNum} ${passivityNum} -`;
console.log(`${initiativeNum} - ${passivityNum} = ${result}`);
break;
case "*":
result = `${initiativeNum} ${passivityNum} *`;
console.log(`${initiativeNum} * ${passivityNum} = ${result}`);
break;
case "/":
result = `${initiativeNum} ${passivityNum} /`;
console.log(`${initiativeNum} / ${passivityNum} = ${result}`);
break;
default:;
}
return result;
}
}
rpn("1+7*(4-2)"); // 輸出=> "1 7 4 2 - * +"
2.5 漢諾塔
漢諾塔（港臺：河內(nèi)塔）是根據(jù)一個傳說形成的數(shù)學問題：
有三根桿子A，B，C。A桿上有 N 個 (N>1) 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至 C 桿：每次只能移動一個圓盤；
大盤不能疊在小盤上面。
堆棧的經(jīng)典算法應用，首推就是漢諾塔。
理解該算法，要注意以下幾點：
不要深究每次的移動，要抽象理解
第一步：所有不符合要求的盤，從A塔統(tǒng)一移到B塔緩存
第二步：將符合的盤移動到C塔
第三步：把B塔緩存的盤全部移動到C塔
以下是代碼實現(xiàn)：
var ATower = new Stack(); // A塔
var BTower = new Stack(); // B塔
var CTower = new Stack(); // C塔 (目標塔)
var TIER = 4; // 層數(shù)
for(var i = TIER; i > 0; i--){
ATower.push(i);
}
function Hanoi(n, from, to, buffer){
if(n > 0){
Hanoi(n - 1, from, buffer, to); // 所有不符合要求的盤（n-1），從A塔統(tǒng)一移到B塔緩存
to.push(from.pop()); // 將符合的盤（n）移動到C塔
Hanoi(n - 1, buffer, to, from); // 把B塔緩存的盤全部移動到C塔
}
}
Hanoi(ATower.read().length, ATower, CTower, BTower);
漢諾塔的重點，還是靠遞歸去實現(xiàn)。把一個大問題，通過遞歸，不斷分拆為更小的問題。然后，集中精力解決小問題即可。
三、小結(jié)不知不覺，寫得有點多ORZ。
后面章節(jié)的參考鏈接，還是推薦看看。也許配合本文，你會有更深的理解。
[1] 中綴表示法
[2] 后綴表示法
[3] 調(diào)度場算法
[4] 漢諾塔
喜歡我文章的朋友，可以通過以下方式關注我：
「star」 或 「watch」 我的GitHub blog
RSS訂閱我的個人博客：王先生的基地
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/96804.html
摘要：它的主體特征是增量渲染能夠?qū)秩竟ぷ鞣指畛蓧K，并將其分散到多個幀中。實際上，這樣做可能會造成浪費，導致幀丟失并降低用戶體驗。當一個函數(shù)被執(zhí)行時，一個新的堆棧框架被添加到堆棧中。該堆棧框表示由該函數(shù)執(zhí)行的工作。 原文 react-fiber-architecture 介紹 React Fibre是React核心算法正在進行的重新實現(xiàn)。它是React團隊兩年多的研究成果。 React ...
摘要：同步一次執(zhí)行一件事，同步引擎一次只執(zhí)行一行，是同步的。調(diào)用函數(shù)將其推入堆棧并從函數(shù)返回將其彈出堆棧。執(zhí)行上下文當函數(shù)放入到調(diào)用堆棧時由創(chuàng)建的環(huán)境。執(zhí)行結(jié)果它會立即被推到回調(diào)隊列，但它仍然會等待調(diào)用堆棧為空才會執(zhí)行。 為了保證可讀性，本文采用意譯而非直譯。 想閱讀更多優(yōu)質(zhì)文章請猛戳GitHub博客,一年百來篇優(yōu)質(zhì)文章等著你！ 一些名詞 JS引擎 — 一個讀取代碼并運行的引擎，沒有單一的J...
摘要：原始緩沖區(qū)的創(chuàng)建通過這個構(gòu)造函數(shù)可以創(chuàng)建一個原始緩沖區(qū)從控制臺可以看到實例擁有一個的屬性，用于獲取的，一個只有以及支持的方法，用于對長度進行截取操作。所有數(shù)組類型的長度均固定。 本文同步自我的博客園：http://www.cnblogs.com/hustskyking/ 相信每一個 javascript 學習者，都會去了解 JS 的各種基本數(shù)據(jù)類型，數(shù)組就是數(shù)據(jù)的組合，這是一個很基本...
摘要：值啟用了更詳細的堆棧保護檢查，它以犧牲一些性能的代價提供更精確的。這種可以由任何類型的編碼錯誤引起，但表現(xiàn)為函數(shù)指針錯誤，因為在運行時的預期表中無法找到函數(shù)。 翻譯：云荒杯傾本文是Emscripten-WebAssembly專欄系列文章之一，更多文章請查看專欄。也可以去作者的博客閱讀文章。歡迎加入Wasm和emscripten技術交流群，群聊號碼：939206522。 調(diào)試Emscri...
閱讀 2984·2023-04-26 00:23
閱讀 3399·2021-09-13 10:28
閱讀 2178·2021-08-31 14:18
閱讀 2884·2019-08-30 15:54
閱讀 1939·2019-08-30 15:43
閱讀 1276·2019-08-29 16:56
閱讀 2800·2019-08-29 14:16
閱讀 2053·2019-08-28 17:51
