什么是栈
栈就是和列表类似的一种数据结构，它可用来解决计算机世界里的很多问题。栈是一种高 效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。 栈的使用遍布程序语言实现的方方面面，从表达式求值到处理函数调用。
栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。
栈被称为一种后入先出(LIFO，last-in-first-out)的数据结构。
栈的实现
在JavaScript中，我们可以用如下函数实现栈：
function Stack(){
this.dataStore = []; //使用数组保存栈内元素
this.top=0; //记录栈顶位置，初始化为0
this.push = push; // 向栈中压入一个新元素
this.pop = pop; // 从栈顶推出一个元素
this.peek = peek; // 返回栈顶元素
this.clear=clear; //清除栈
this.length=length;//返回栈的元素个数
}
//当向栈中压入一个新元素时，需要将其保存在数组中变量 top 所对 应的位置，
//然后将 top 值加 1，让其指向数组中下一个空位置。
function push(element){
this.dataStore[this.top++]=element;
}
//它返回栈顶元素，同时将变量 top 的值减 1
function pop(){
return this.dataStore[--this.top];
}
//返回数组的第 top-1 个位置的元素，即栈顶元素:
function peek(){
return this.dataStore[this.top-1];
}
//通过返回变量 top 值的方式返回栈 内的元素个数
function length(){
return this.top;
}
//清空一个栈
function clear(){
this.top = 0;
}
以下所有算法题目，都是依据Stack函数的。
实战练习
习题一
利用栈将一个数字从一种数制转换成另一种数制。假设想将数字 n 转换为以 b 为基数
的数字，实现转换的算法如下。
(1) 最高位为 n % b，将此位压入栈。
(2) 使用 n/b 代替 n。
(3) 重复步骤 1 和 2，直到 n 等于 0，且没有余数。
(4) 持续将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后数字的字符
串形式。
此算法只针对基数为2～9的情况
代码如下：
function mulBase(num, base) {
var s = new Stack();
do {
s.push(num % base);
num = Math.floor(num / base);
} while (num > 0)
var converted = "";
while (s.length() > 0) {
converted += s.pop();
}
return converted;
}
console.log(mulBase(32, 2)); // 100000
习题二
判断给定字符串是否是回文
思路：
从左往右把字符串的每一个字符，依次放入栈中，最后从栈的顶部往底部看去，就是一个反过来的字符串。我们只要依次将字符串弹出，组成一个新的字符串，与原来的字符串进行比较即可。相等的话，就是回文，反之，不是回文。
代码如下：
function isPalindrome(word){
var s = new Stack();
for(var i=0;i<word.length;++i){
s.push(word[i]);
}
var newWord = '';
while(s.length()>0){
newWord += s.pop();
}
if(newWord === word){
return true;
}else{
return false;
}
}
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello")); // false
习题三
使用栈来实现阶乘函数
思路：
首先将数字从 num 到 1 压入栈，然后使用一个循环，将数字挨
个弹出连乘，就得到了正确的答案
代码如下：
function factorial(num){
var s = new Stack();
while(num>1){
s.push(num--);
}
var product = 1;
while(s.length()>0){
product *= s.pop();
}
return product;
}
console.log(factorial(5)); //120
习题三
用栈来判断一个表达式中的括号（仅有一种括号,小、中或大括号）是否配对.编写并实现它的算法.
思路:
function isMatch(str){
var s = new Stack;
var bracket = '';
for(var i=0;i<str.length;i++){
bracket = str[i];
if(bracket === "(" || bracket === "[" || bracket === "{"){
s.push(bracket)
}else if(bracket === ")" || bracket === "]" || bracket === "}") {
if(s.length()>0){
s.pop()
}else {
return '括号不匹配';
}
}
}
if(s.length()>0){
return '括号不匹配'
}
return '匹配';
}
console.log(isMatch('1+2*(2+1')); // 括号不匹配
console.log(isMatch('1+2*(2+1)')); // 匹配
console.log(isMatch('1+2*(2+1)+(2*2+1')); // 括号不匹配
console.log(isMatch('1+2*(2+1)+(2*2+1)')); // 匹配
习题四
现实生活中栈的一个例子是佩兹糖果盒。想象一下你有一盒佩兹糖果，里面塞满了红 色、黄色和白色的糖果，但是你不喜欢黄色的糖果。使用栈(有可能用到多个栈)写一 段程序，在不改变盒内其他糖果叠放顺序的基础上，将黄色糖果移出。
思路
除了糖果盒，还需要俩个栈。一个用来存放黄色糖果，一个用来存放其他糖果。首先将糖果盒中的糖一个个弹出，压入目标栈中。当糖果盒中的糖全都弹出后，把存放其他糖果的栈中的糖一个个弹出，压入糖果盒中，这样就得到想要的结果了。
代码如下：
// 假设盒子中放着这些糖果
var sweetBox = new Stack();
sweetBox.push('yellow');
sweetBox.push('white');
sweetBox.push('yellow');
sweetBox.push('white');
sweetBox.push('red');
sweetBox.push('red');
sweetBox.push('yellow');
sweetBox.push('red');
sweetBox.push('yellow');
sweetBox.push('white');
console.log(sweetBox.dataStore);
function selectYellow(){
var yellow = new Stack(); //放置黄色糖果
var other = new Stack(); //放置其他糖果
var one = '';
while(sweetBox.length()>0){
var one = sweetBox.pop();
if(one === 'yellow'){
yellow.push(one);
}else{
other.push(one);
}
}
while(other.length()>0){
sweetBox.push(other.pop());
}
return sweetBox;
}
console.log(selectYellow().dataStore);
