JS中数据结构之栈

站长资源 2024/11/25 佚名

65 1538 65

DDR爱好者之家 Design By 杰米

栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元素，必须先拿掉上面的元素。

栈的实现

用数组 dataStore 保存栈内元素，构造函数将其初始化为一个空数组。变量 top 记录栈顶位置，被构造函数初始化为 0，表示栈顶对应数组的起始位置 0。如果有元素被压入栈，该变量的值将随之变化。

function Stack() {
  this.dataStore = [];
  this.top = 0;
  this.push = push;
  this.pop = pop;
  this.peek = peek;
}

push() 方法：当向栈中压入一个新元素时，需要将其保存在数组中变量 top 所对应的位置，然后将 top 值加 1，让其指向数组中下一个空位置。

function push(element) {
  this.dataStore[this.top++] = element;
}

pop() 方法：与 push() 方法相反——它返回栈顶元素，同时将变量 top 的值减 1

function pop() {
  return this.dataStore[--this.top];
}

peek() 方法：返回数组的第 top-1 个位置的元素，即栈顶元素。如果对一个空栈调用 peek() 方法，结果为 undefined。这是因为栈是空的，栈顶没有任何元素。

pop() 方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。peek() 方法则只返回栈顶元素，而不删除它。

function peek() {
  return this.dataStore[this.top-1];
}

length() 方法：通过返回变量 top 值的方式返回栈内的元素个数

function length() {
  return this.top;
}

clear()方法：将变量 top 的值设为 0，清空栈

function clear() {
  this.top = 0;
}

使用栈解决问题举例：判断一个字符串是否是回文

DDR爱好者之家 Design By 杰米

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

DDR爱好者之家 Design By 杰米

评论“JS中数据结构之栈”

暂无评论...