共计 1502 个字符，预计需要花费 4 分钟才能阅读完成。
我们可以在数组的任何位置上删除或者添加元素，但有时候我们还需要在元素的添加或删除时有更多控制的数据结构，有两种数据结构类似于数组，但在添加或删除元素时更为可控，它们就是栈和队列。本节主要介绍栈。
1. 栈数据结构
栈是一种遵循后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，叫做栈顶，另一端叫栈底。在栈中，新元素靠近栈顶，旧元素接近栈底。如下图所示：
2. 创建栈
// 首先创建一类表示栈
function Stack(){
let items = []; // 选择数组来保存栈中的元素
// 各种属性和方法
}
下面要为栈声明一些方法：
push() // 添加一个或多个新元素到栈顶
pop() // 移除栈顶元素，同时返回被移除的元素
peek() // 仅仅返回栈顶元素，不对栈做任何修改
isEmpty() // 如果栈中没有元素返回 true，否则返回 false
clear() // 移除栈中所有元素
size() // 返回栈中元素的个数（和数组 length 类似）
2.1 向栈添加元素
this.push() = function(element) {
items.push(element);
}
2.2 从栈移除元素
this.pop = function() {
items.pop();
}
2.3 查看栈顶元素
this.peek = function() {
return items[items.length – 1];
}
2.4 查看栈是否为空
this.isEmpty = function(){
return items.length === 0;
}
this.size = function() {
return items.lenght;
}
2.5 清空和打印栈元素
this.clear = function() {
items = [];
}
this.print = function() {
console.log(items.toString());
}
经过上述的方法的添加，我们就完整的创建了一了个栈 Stack。
3. 栈的应用—十进制转 N 进制
首先我们写出将十进制转为二进制：
function divideBy2(decNum) {
var remStack = new Stack(),
rem,
binaryString = ”;
// 将十进制数除 2 的余数放入一个 stack 中
while(decNum > 0) {
// 取余
rem = Math.floor(decNum % 2);
// 入栈
remStack.push(rem);
decNum = Math.floor(decNum / 2);
}
// 从栈中取出转化为字符串然后连接起来构成二进制
while(!remStack.isEmpty()) {
// 出栈
binaryString += remStack.pop().toString();
}
return binaryString;
}
下面十进制转化 N 进制算法
function divideByN(decNum, n) {
var remStack = new Stack(),
rem,
binaryString = ”,
digits = ‘0123456789ABCDEF’;
// 将十进制数除 N 的余数放入一个 stack 中
while(decNum > 0) {
// 取余
rem = Math.floor(decNum % n);
// 入栈
remStack.push(rem);
decNum = Math.floor(decNum / n);
}
// 从栈中取出转化为字符串然后连接起来构成二进制
while(!remStack.isEmpty()) {
// 出栈 使用 digits 方便在 16 进制中做个对应转化
binaryString += digits[remStack.pop()];
}
return binaryString;
}
