栈（stack）是一种遵循后进先出（Last In First Out, LIFO）的有序集合所构成的数据结构。
- 新添加或待删除的元素保存在栈的末尾（栈顶），另一端叫做栈底。
- 在栈里，新元素都靠近栈顶，就元素都接近栈底。
栈
栈是和列表类似的一种高效的数据结构，由于数据只能在栈顶添加和删除，所以增删操作很快。
- 栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，此端称为栈顶。
入栈
后进先出的栈中，任何不在栈顶的元素都无法访问。为了得到栈底元素必须先拿掉上面的元素。
对栈的操作是将元素压入栈（push）和弹出栈（pop）。
入栈和出栈
- 若要预览栈顶元素，pop方法虽然访问栈顶元素，但调用后栈顶元素也从栈中被永久性地被删除了。peek方法则只返回栈顶元素而不删除它。
出栈
- 为了记录栈顶元素的位置，同时也为了标记哪里可以加入新元素，使用变量top，当向栈内压入元素时，该变量变大；当从栈内弹出元素时，该变量变小。
top变量记录栈顶元素的位置
栈的实现1
/*栈类*/
function Stack(){
this.data = [];//保存栈内元素
this.top = 0;//记录栈顶位置
this.push = push;
this.pop = pop;
this.peek = peek;
/*辅助方法*/
this.size = size;
this.clear = clear;
}
/*向栈中压入新元素*/
function push(element){
this.data[this.top++] = element;
}
/*从栈中弹出栈顶元素*/
function pop(){
return this.data[--this.top];
}
/*预览栈顶元素，空栈返回undefined*/
function peek(){
return this.data[this.top - 1];
}
/*获取栈内存储的元素数量*/
function size(){
return this.top;
}
/*清空栈*/
function clear(){
this.top = 0;
}
/*test*/
var stack = new Stack();
stack.push('David');
stack.push('Raymond');
stack.push('Bryan');
print(stack.size());//3
var poped = stack.pop();
print(poped, stack.peek());//Bryan Raymond
stack.clear();
print(stack.size());//0
数制间的相互转换
将数字n转换为b为基数的数字
- 最高位为n%b将此位压入栈
- 使用n/b替换n
- 重复以上操作知道n等于0且没有余数
- 持续将栈内元素弹出知道栈为空，依次排列元素。
// 将数字转化为二至九进制的数字
function mulBase(number,base){
var stack = new Stack();
do{
stack.push(number % base);
number = Math.floor(number /= base);
}while(number>0);
var converted = '';
while(stack.size() > 0){
converted += stack.pop();
};
return converted;
}
print(mulBase(125,2), mulBase(124,8));//1111101 174
回文
回文是指这样一种现象：一个单词、短语或数字，从前往后写和从后向前写都是一样的。
- dad、racecar
- A man, a plan, a canal: Panama
- 1001
使用栈判断一个字符串是否是回文，将字符串每个字符按从左到右的顺序压入栈。当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底。
使用栈判断一个单词是否是回文
字符串完整压入栈内后，通过持续弹出栈中的每个字母就可以得到一个新的字符串，该字符串与原来的字符串顺序相反。最后仅需比较两个字符串即可，若相等就是一个回文。
function isPalindrom(word){
var stack = new Stack();
for(var i=0; i<word.length; ++i){
stack.push(word[i]);
}
var rword = "";
while(stack.size() > 0){
rword += stack.pop();
}
return word == rword;
}
print(isPalindrom("hello"), isPalindrom("racecar"));//false true
递归
栈通常用来实现编程语言，使用栈实现递归即是一例。使用栈来模拟递归过程，考虑求阶乘函数的递归定义。
function factorial(n){
if(n === 0){
return 1;
}else{
return n*factorial(n-1);
}
}
function fact(n){
var stack = new Stack();
while(n>1){
stack.push(n--);
}
var product = 1;
while(stack.size()>0){
product *= stack.pop();
}
return product;
}
print(factorial(5), fact(5));//120 120
栈的实现2
function Stack(){
var items = [];//保存栈内元素
/*添加一个或多个元素到栈顶*/
this.push = function(element){
items.push(element);
};
/*移除栈顶元素同时返回被移除的元素*/
this.pop = function(){
return items.pop();
};
/*预览栈顶元素*/
this.peek = function(){
return items[items.length-1];
};
/*判断栈中是否空栈，true为空栈无元素，false为有元素。*/
this.isEmpty = function(){
return items.length===0;
};
/*返回栈内的元素个数*/
this.size = function(){
return items.length;
};
/*移除栈内的所有元素*/
this.clear = function(){
items = [];
};
/*将栈内元素输出到控制台*/
this.print = function(){
console.log(items.toString());
};
}
/*test*/
var stack = new Stack();
print(stack.isEmpty());//true
stack.push(5);
stack.push(8);
print(stack.peek());//8
stack.push(11);
print(stack.size(), stack.isEmpty());//3 false
stack.push(15);
入栈
stack.pop();
stack.pop();
print(stack.size());//2
stack.print();//5 8
出栈
十进制转二进制
要把十进制转换成二进制，可以将该十进制数字和2整除（二进制是逢二进一），知道结果为0为止。
十进制转二进制
function divideBy2(decnum){
var stack = new Stack();
var rem;
while(decnum > 0){
rem = Math.floor(decnum%2);//求模取余
stack.push(rem);
decnum = Math.floor(decnum/2);//商
}
var binary = '';
while(!stack.isEmpty()){
binary += stack.pop().toString();
}
return binary;
}
print(divideBy2(10));//1010
十进制转换成任何进制
function baseConvert(decnum, base){
var stack = new Stack();
var rem;
while(decnum>0){
rem = Math.floor(decnum%base);
stack.push(rem);
decnum = Math.floor(decnum/base);
}
var basestr = "";
var digits = "0123456789ABCDEF";
while(!stack.isEmpty()){
basestr += digits[stack.pop()];
}
return basestr;
}
print(baseConvert(100345,2),baseConvert(100345,8),baseConvert(100345,16));//11000011111111001 303771 187F9
