栈（Stack）：是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。
栈的特点是：遵循LIFO （last in, first out）（后进先出）的原则。先进后出从栈顶放入元素的操作叫入栈（压栈），取出元素叫出栈（弹栈）。
image.png
入栈操作：
image.png
出栈操作：
image.png
栈常见的操作：
push（element）：添加一个新元素到栈顶位置；
pop（）：移除栈顶的元素，同时返回被移除的元素；
peek（）：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）；
isEmpty（）：如果栈里没有任何元素就返回true，否则返回false；
size（）：返回栈里的元素个数。这个方法和数组的length属性类似；
clear() : 清空栈;
toString（）：将栈结构的内容以字符串的形式返回。
function Stack() {
// 栈元素
this.items = [];
//1.入栈
Stack.prototype.push = (element) => {
this.items.push(element);
}
// 2.pop删除栈顶元素,并返回该元素
Stack.prototype.pop = () => {
return this.items.pop(); //pop方法删除最后一个元素,并返回删除的该值
}
// 3.取出栈顶元素
Stack.prototype.peek = () => {
return this.items[this.items.length - 1]
}
// 4.判断栈是否为空
Stack.prototype.isEmpty = () => {
return this.items.length === 0
}
// 5.获取栈的个数
Stack.prototype.size = () => {
return this.items.length;
}
// 6.输出栈数据,希望这种形式: 20 10 100
Stack.prototype.toString = () => {
let Str = ''
for (let i of this.items) {
Str += i + ' ';
}
return Str
}
}
let s = new Stack()
//测试案例:
s.push(20);
s.push(10);
s.push(100);
s.push(77);
console.log(s.toString()); //打印:20 10 100 77
//删除两个元素
console.log(s.pop()); //77
console.log(s.pop()); //100
//取出栈顶元素
console.log(s.peek()); //10
//是否为空
console.log(s.isEmpty()); //false
//剩余大小
console.log(s.size()); //2
//最终打印
console.log(s.toString()); //20 10
使用es6写法封装栈
// 栈结构的封装
class Stack{
constructor() {
this.items = [];
}
// push(item) 压栈操作，往栈里面添加元素
push(item) {
this.items.push(item);
}
// pop() 出栈操作，从栈中取出元素，并返回取出的那个元素
pop() {
return this.items.pop();
}
// peek() 查看栈顶元素
peek() {
return this.items[this.items.length - 1];
}
// isEmpty() 判断栈是否为空
isEmpty() {
return this.items.length === 0;
}
// size() 获取栈中元素个数
size() {
return this.items.length;
}
// toString() 返回以字符串形式的栈内元素数据
toString() {
let result = '';
for (let item of this.items) {
result += item + ' ';
}
return result;
}
}
栈的实际应用:
十进制转二进制
let decTobin = decNumber => {
//1.定义一个栈对象，保存余数
var stack = new Stack()
// 2.循环入栈操作
while (decNumber > 0) {//当除法结果不为零时,入栈添加
// 2.1.获取余数并放入栈中
stack.push(decNumber % 2)
// 2.2.获取整除后的结果作为下一次运算的数字(floor:向下取整)
decNumber = Math.floor(decNumber / 2)
}
// 3.循环出栈操作
let binaryString = '';
while (stack.items.length != 0) {
binaryString += stack.pop();
}
return binaryString;
}
//测试代码
console.log(decTobin(10)); //1010
console.log(decTobin(100)); //1100100
console.log(decTobin(1000)) //1111101000
十进制转任意进制
let decTobin = (decNumber, base) => {
if (base < 2 || base > 36) {
return "表示不了这个进制"
}
//1.定义一个栈对象，保存余数
var stack = new Stack()
var digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
// 2.循环操作
while (decNumber > 0) {
// 2.1.获取余数并放入栈中
stack.push(decNumber % base)
// 2.2.获取整除后的结果作为下一次运算的数字(floor:向下取整)
decNumber = Math.floor(decNumber / base)
}
// 3.从栈中取出值
let binaryString = '';
while (stack.items.length != 0) {
binaryString += digits[stack.pop()]; //根据下标返回字符值,如:"01"[1]=11
}
return binaryString;
}
//测试代码
console.log(decTobin(100345, 2)); //11000011111111001
console.log(decTobin(100345, 8)); //303771
console.log(decTobin(100345, 16)); //187F9
console.log(decTobin(100345, 35)); //2BW0
