JavaScript数据结构与算法之栈详解

  • Z时代
  • 2024-01-10
  • 分类：综合

在上一篇博客介绍了下列表，列表是最简单的一种结构，但是如果要处理一些比较复杂的结构，列表显得太简陋了，所以我们需要某种和列表类似但是更复杂的数据结构---栈。栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样操作很快，而且容易实现。

一：对栈的操作。

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端陈为栈顶。比如餐馆里面洗盘子，只能先洗最上面的盘子，盘子洗完后，也只能螺到这一摞盘子的最上面。栈被称为 "后入先出"（LIFO）的数据结构。

由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问，为了得到栈低的元素，必须先拿掉上面的元素。我们可以对栈的两种主要操作是将一个元素 压入栈 和 将一个元素 弹出栈。入栈我们可以使用方法push（）方法，出栈我们使用pop（）方法。pop（）方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也就从栈中被永久性的删除了。另一个我们很常用的方法是peek（），该方法只返回栈顶元素，而不删除它。

入栈和出栈的实列图如下：

push(),pop()和peek（）是栈的三个主要方法，但是栈还有其他方法和属性。如下：

clear（）：清除栈内的所有元素。

length(): 记录栈内元素的个数。

二：对栈的实现如下：

我们可以先实现栈类的方法开始；如下：

 

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

 如上：dataStore 是保存栈内的所有元素。变量top记录栈顶的位置，初始化为0. 表示栈顶对应数组的起始位置为0，如果有元素被压入栈。该变量值将随之变化。

我们还有如下几个方法：push(), pop(), peek(),clear()，length();

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

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

2. pop()方法与push（）方法相反---它返回栈顶元素，同时将top值减1.如下代码：

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

3. peek()方法返回数组的第top-1个位置的元素，即栈顶元素；

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

4. length()方法 有时候我们要知道栈内有多少个元素，我们可以通过返回变量top值的方式返回栈内的元素个数，如下代码：

     function length(){
         return this.top;
     }

5. clear(); 有时候我们要清空栈，我们将变量top值设为0；如下代码：

   function clear() {

        this.top = 0;

    }

以上是 JavaScript数据结构与算法之栈详解 的全部内容， 来源链接： utcz.com/z/330430.html

回到顶部