棧是一種後入先出（LIFO）的資料結構，資料隻能在棧頂添加或者删除，是以操作很快，容易實作。将從3個方面來深入了解和使用棧這種資料結構。
- 抽象資料類型定義
- 棧的JS實作
- 解決實際問題
抽象資料類型定義
| 屬性及方法 | 作用 |
|---|---|
| push() | 入棧 |
| pop() | 出棧 |
| peek() | 顯示棧頂元素 |
| dataStore | 存儲資料 |
| top | 記錄棧的長度和位置 |
棧的JS實作
使用構造器調用模式，這是一套類似類的對象建構文法，通過在函數前面加上調用，同時new
會綁定到這個新對象上。this
//Stack.js
//Stack對象定義
function Stack(){
this.dataStore = [];
this.pop = pop;
this.push = push;
this.peek = peek;
this.clear = clear;
this.length = length;
this.top = ;
}
function push(element){
this.dataStore[this.top++] = element;
}
function pop(){
return this.dataStore[--this.top]
}
function peek(){
return this.dataStore[this.top-]
}
function length(){
return this.top;
}
function clear(){
this.top = ;
}
//執行個體化Stack對象
var oneStack = new Stack();
棧的實際應用
（一）網頁展示
（二）html代碼
<!DOCTYPE html>
<html>
<head>
<title>JS structure - Stack</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<script src="stack.js" type="text/javascript"></script>
<script src="practice.js" type="text/javascript"></script>
</head>
<style>
div {
width: %;
margin: px auto;
padding: px;
border: px solid #333;
}
</style>
<body>
<div>
<h2>進制轉換</h2>
<form>
<label for="input_number">輸入一個數字：</label>
<input type="text" id="input_number" />
<label for="input_radix">輸入進制：</label>
<input type="text" id="input_radix" />
<input type="button" value="轉換" onClick="transfer()">
<textarea id="transfer_result"></textarea>
</form>
</div>
……
</body>
</html>
（三）Javascript方法
1. 進制轉換
//practice.js
function mulBase(num, base){
var tStack = new Stack();
do{
tStack.push(num%base);//最高位為n%b
num = Math.floor(num / base);//n/b代替n
}while(num > );
var converted = "";
while(tStack.length()>){
converted += tStack.pop();//FILO
}
return converted;
}
2. 階乘
//practice.js
function fact(number){
var fStack = new Stack();
while(number > )
{
fStack.push(number);//将數字從大到小壓入棧中
number = number -;
}
var result = ;
while(fStack.length()>)
{
result *= fStack.pop();//彈出的元素挨個出棧相乘
}
return result;
}
3. 括号比對
//practice.js
function bracketmatch(expression)
{
var bStack = new Stack();
for(var i=; i<expression.length; i++)
{
if(expression[i] == "(")
{
bStack.push(expression[i]);//遇到“（”将其壓入棧出
}
else if(expression[i] == ")")
{
if(bStack.peek() == "(")
bStack.pop();//直到遇到“）”，将“（"彈出棧
}
else
{
//其他符号，不進行任何操作
}
}
if(bStack.length()>)
return false;
else
return true;
}
4. 字尾表達式
将中綴表達式轉換成字尾表達式的算法思路，可以參看Miibotree的資料結構文，http://blog.csdn.net/gaoxin1076/article/details/7364098
//practice.js
function expressionChange(expression){
var result = "";
var operators = new Stack();
for(var i=; i<expression.length; i++)
{
var currentCharac = expression[i];
switch(currentCharac)
{
case "("://左括号直接入棧
operators.push(currentCharac);
break;
case ")"://右括号将所有棧内元素彈出
while(operators.peek()!="(")
{
result += operators.pop()+" ";
}
operators.pop();//彈出左括号
break;
case "+":
case "-"://因為+和-的優先級最低，将所有棧内元素彈出後，将目前符号壓入棧。
while(operators.length()> && operators.peek() != "(")
{
result += operators.pop()+" ";
}
operators.push(currentCharac);
break;
case "/":
case "*"://隻有當棧頂元素是/，*的時候，才需要彈出所有棧内元素。
while(operators.length()> && (operators.peek() == "*" || operators.peek() == "/"))
{
result += operators.pop()+" ";
}
operators.push(currentCharac);
break;
default:
while(currentCharac<="9" && currentCharac>="0")
{
result += currentCharac;
currentCharac = expression[++i];
}
result += " ";
i--;//一定要減，不然的話i加了兩次1
break;
}
}
while(operators.length()>)//最後要将站内剩下元素彈出
{
result += operators.pop()+" ";
}
return result;
}
![JavaScript的那些坑之事件代理事件代理事件階段[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)