栈是和列表很类似的数据结构，它可以解决很多我们日常生活中的问题。
栈的结构很像我们平常放衣服的收纳箱，它有两种操作，一种是入栈，就像在收纳箱里面放衣服,另外一种是出栈，类似于从收纳箱里面拿出衣服。
当然它是一种很高效的数据结构。因为数据只能在顶部添加和删除，所以这种操作比较快，而且容易实现。
注意：要访问栈底部的元素，必须得拿到它上面得元素。
下面是入栈和出栈操作示意图：
入栈.png
出栈.png
接下来，我们看一下栈的常见的操作。
function stack()
{
this.dataStore=[];
this.push=push;
this.pop=pop;
this.peek=peek;
this.length=length;
this.top=0; //栈顶元素的位置
}
栈常见的操作有入栈(push)，出栈(pop)，获取当前的栈顶元素(peek)，获取栈内的元素个数。
在这里，我们要注意的是，pop函数返回的是出栈前的栈顶元素，而peek函数则返回的是当前的栈顶元素。
入栈函数
function push(data)
{
this.dataStore[this.top++]=data;
}
出栈函数
function pop()
{
return this.dataStore[--this.top];
}
获取当前的栈顶元素
function peek()
{
return this.dataStore[this.top-1];
}
获取当前栈的元素个数
function length()
{
return this.top;
}
我们来使用一下栈
var fruits=new Stack();
fruits.push("pear");
fruits.push("apple");
console.log(fruits.peek());
console.log(fruits.length());
console.log(fruits.pop());
console.log(fruits.length());
console.log(fruits.peek());
那么栈到底有什么用处呢?
1.将数字从一种进制换成另外一种进制。
我们现实生活中常用的是十进制的数字，但是计算机中使用的是二进制的数字,那么我们怎么才能将十进制数字转化为二进制？
常规算法
function change(data)
{
var array=[];
while(data>=1)
{
var temp=data%2;
array.push(temp);
data=Math.floor(data/2);
}
array.reverse();
return array.join("");
}
使用栈处理
function change(data)
{
var str="";
var stack=new Stack();
while(data>=1)
{
var temp=data%2;
stack.push(temp);
data=Math.floor(data/2);
}
while(stack.length>0)
{
str+=stack.pop();
}
return str;
}
2.回文
回文是这样的一种现象，一段数字、单词、短语、句子，从前往后写和从后往前写都是一样的。
比如：12321，dad，pop这些就是回文。而12431，mongo这些就不是回文。
接下来我们判断给定的字符串是否是回文。
普通算法
function isPalindrome(data)
{
var str=data.split("").reverse().join("");
if(str==data)
{return true;}
else
{return false;}
}
使用栈处理
function isPalindrome(data)
{
var str=data.split("");
var stack=new Stack();
for(var i=0;i<str.length;i++)
{
stack.push(str[i]);
}
str="";
while(stack.length()>0)
{
str+=stack.pop();
}
if(str==data)
{return true;}
else
{return false;}
}
我们来判断一下给定的数字是否是回文。
普通算法
function isPalindrome(data)
{
var str=data.toString().split("").reverse().join("");
if(str==data.toString())
{return true;}
else
{return false;}
}
使用栈处理
function isPalindrome(data)
{
var temp=0;
if(data<0)
{return false;}
var stack=new Stack();
var curr=data;
var other=data;
while(curr>0)
{
stack.push(curr%10);
curr=Math.floor(curr/10);
}
while(stack.length()>0)
{
temp=stack.pop()+temp*10;
}
if(other==temp)
{return true;}
else
{return false;}
}
第一种算法是将数字转化为字符串之后去处理的。其实还有一种更高效的算法。
将数字转换成数组，若数组的第一个元素和最后一个元素一样，第二个元素和倒数第二个元素一样，...以此类推，只要全部相同那么就是回文，否则就不是回文。
function isPalindrome(data)
{
if(data<0)
{return false}
var cur=[];
while(cur>0)
{
cur.push(cur%10);
cur=Math.floor(cur/10);
}
for(var i=0;i<Math.floor(cur.length/2);i++)
{
if(cur[i]!=cur[cur.length-1-i])
{return false;}
}
return true;
}
3.递归
使用栈模拟递归
下面我们来计算某个数的阶乘。
function fact(n)
{
var stack=new Stack();
var last=1;
while(n>1)
{
stack.push(n--);
}
while(stack.length()>0)
{
last*=stack.pop();
}
return last;
}
网友评论