站就是和列表类似的一种数据结构，它可用来解决计算机世界里的很多问题。栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。栈的使用遍布程序语言实现的方方面面，从表达式求值到处理函数调用。
1. 对栈的操作
对栈的两种主要操作就是将一个元素压入栈和将一个元素弹出栈。入栈使用push()方法，出栈使用pop（）方法。
图片演示了入栈和出栈的过程
pop() 方法虽然可以访问栈顶的元素，但是调用该方 法后，栈顶元素也从栈中被永久性地删除了。
peek() 方法则只返回栈顶元素，而不删除它。
clear() 清除栈内所有元素
length 属性记录栈内元素的个数
empty 属性，用 以表示栈内是否含有元素，使用 length 属性也可以达到同样的目的。
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top - 1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}
var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
print("length: " + s.length()); print(s.peek());
var popped = s.pop();
print("The popped element is: " + popped); print(s.peek());
s.push("Cynthia");
print(s.peek());
s.clear();
print("length: " + s.length()); print(s.peek());
s.push("Clayton");
print(s.peek());使用Stack类
数制间的相互转换
将数字转换为二进制和八进制
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;
}
print(mulBase(32, 2))-
(1) 最高位为 n % b，将此位压入栈。
-
(2) 使用 n / b 代替 n。
-
(3) 重复步骤 1 和 2，直到 n 等于 0，且没有余数。
-
(4) 持续将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后数字的字符
串形式
-
此算法只针对基数为 2~9 的情况
回文
使用栈，可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至 右的顺序压入栈。当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底，字符串完整压入栈内后，通过持续弹出栈中的每个字母就可以得到一个新字符串，该字符串刚好与原来的字符串顺序相反。我们只需要比较这两个字符串即可，如果它们相等，就是一个回文。
function isPalindrome(word) {
var s = new Stack();
for (var i = 0; i < word.length; ++i) {
s.push(word[i]);
}
var rword = "";
while (s.length() > 0) {
rword += s.pop();
}
if (word == rword) {
return true;
}
else {
return false;
}
}
递归演示
求阶乘函数的递归定义。首先看看 5 的阶乘是怎么 定义的:
5! = 5×4×3×2×1 = 120
使用栈来模拟计算 5! 的过程，首先将数字从 5 到 1 压入栈，然后使用一个循环，将数字挨个弹出连乘，就得到了正确的答案:120。例 4-5 包含了该函数和测试程序的代码。
使用栈模拟递归过程
function fact(n) {
var s = new Stack();
while (n > 1) {
s.push(n--);
}
var product = 1;
while (s.length() > 0) {
product *= s.pop();
}
return product;
}
print(factorial(5)); // 显示 120 print(fact(5)); // 显示 120
