当前位置 博文首页 > 司夏的博客：JavaScript 数据结构与算法（栈）
栈是一种遵从后进先出（LIFO）原则的有序集合。 新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。栈也被用在编程语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录（浏览器的返回按钮）
创建一个类来表示栈，简单地从创建一个 stack-array.js 文件并声明 Stack 类开始
声明 Stack 类
class Stack {
constructor() {
this.items = []; // {1}
}
}
向栈添加元素
push(element(s)) 添加一个（或几个）新元素到栈顶。
push(element) {
this.items.push(element);
}
从栈移除元素
pop() 移除栈顶的元素，同时返回被移除的元素。
pop() {
return this.items.pop();
}
查看栈顶元素
peek() 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返它。
peek() {
return this.items[this.items.length - 1];
}
检查栈是否为空
isEmpty() 如果栈里没有任何元素就返回 true，否则返回 false。
isEmpty() {
return this.items.length === 0;
}
清空栈元素
clear() 移除栈里的所有元素。
clear() {
this.items = [];
}
实现栈的 length
size() 返回栈里的元素个数。该方法和数组lengt属性很类似。
size() {
return this.items.length;
}
完整的Stack类
class Stack {
constructor() {
this.items = []; // {1}
};
push(element) {
this.items.push(element);
};
pop() {
return this.items.pop();
};
peek() {
return this.items[this.items.length - 1];
};
isEmpty() {
return this.items.length === 0;
};
clear() {
this.items = [];
};
size() {
return this.items.length;
}
}
使用 Stack 类
首先需要初始化 Stack 类，然后验证一下栈是否为空
const stack = new Stack();
console.log(stack.isEmpty()); // 输出为 true
往栈里添加一些元素（可以添加任意类型的元素）
stack.push(5);
stack.push(11);
stack.push(8);
如果调用 peek 方法，将输出 8，因为它是往栈里添加的最后一个元素。
console.log(stack.peek()); // 输出 8
console.log(stack.size()); // 输出 3
console.log(stack.isEmpty()); // 输出 false
使用基于数组的栈的问题
对于使用 JavaScript 语言实现栈数据结构的场景，也可以使用一个JavaScript 对象来存储所有的栈元素
首先像下面这样声明一个 Stack 类（stack.js 文件）。
class Stack {
constructor() {
this.count = 0; //count 属性记录栈的大小
this.items = {};
}
// 方法
}
向栈中插入元素
在 JavaScript 中，对象是一系列键值对的集合。要向栈中添加元素，可以使用 count 变量作为 items 对象的键名，插入的元素则是它的值。在向栈插入元素后，递增 count 变量。
push(element) {
this.items[this.count] = element;
this.count++;
}
验证一个栈是否为空和它的大小
count 属性也表示栈的大小。因此，可以简单地返回 count 属性的值来实现 size 方法。
size() {
return this.count;
}
要验证栈是否为空，可以像下面这样判断 count 的值是否为 0。
isEmpty() {
return this.count === 0;
}
从栈中弹出元素
由于我们没有使用数组来存储元素，需要手动实现移除元素的逻辑。pop 方法同样返回了从栈中移除的元素。
pop() {
if (this.isEmpty()) { // {1}
return undefined;
}
this.count--; // {2}
const result = this.items[this.count]; // {3}
delete this.items[this.count]; // {4}
return result; // {5}
}
首先，需要检验栈是否为空（行{1}）。如果为空，就返回 undefined。如果栈不为空的话，将 count 属性减 1（行{2}），并保存栈顶的值（行{3}），以便在删除它（行{4}）之后将它返回（行{5}）
查看栈顶的值并将栈清空
要访问栈顶元素，需要将 count 属性减 1。
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
要清空该栈，只需要将它的值复原为构造函数中使用的值即可。
clear() {
this.items = {};
this.count = 0;
}
也可以遵循 LIFO 原则，使用下面的逻辑来移除栈中所有的元素。
while (!this.isEmpty()) {
this.pop();
}
创建 toString 方法
在数组版本中，不需要关心 toString 方法的实现，因为数据结构可以直接使用数组已经提供的 toString 方法。对于使用对象的版本，需要创建一个 toString 方法来像数组一样打印出栈的内容。
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[0]}`; // {1}
for (let i = 1; i < this.count; i++) { // {2}
objString = `${objString},${this.items[i]}`; // {3}
}
return objString;
}
如果栈是空的，只需返回一个空字符串即可。如果它不是空的，就需要用它底部的第一个元素作为字符串的初始值（行{1}），然后迭代整个栈的键（行{2}），一直到栈顶，添加一个逗号（,）以及下一个元素（行{3}）。如果栈只包含一个元素，行{2}和行{3}的代码将不会执行。
实现了 toString 方法后，就完成了这个版本的 Stack 类。
class Stack {
constructor() {
this.count = 0; //count 属性记录栈的大小
this.items = {};
}
// 方法
push(element) {
this.items[this.count] = element;
this.count++;
};
pop() {
if (this.isEmpty()) { // {1}
return undefined;
}
this.count--; // {2}
const result = this.items[this.count]; // {3}
delete this.items[this.count]; // {4}
return result; // {5}
};
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
};
clear() {
this.items
