栈是一种后入先出（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=)