你的位置:首页 > Java教程

[Java教程]第四章:javascript: 栈


列表是一种最自然的数据组织方式。上一章已经介绍如何使用List类将数据组织成一个列表。如果数据存储的顺序不重要。也不必对数据进行查找,那么列表就是一种再好不过的数据结构。对于其它的一些应用,列表就显得有些简陋了。我们需要某种和列表类似但更复杂的数据结构。

栈就是和列表类似的一种数据结构,它可以用来解决计算机世界里很多的问题。栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样的操作很快,而且容易实现。栈的使用遍布程序语言的方方面面,从表达式求值到处理函数调用。

一:对栈的操作

栈是一种特殊列表,栈内的元素只能通过列表的一端访问,这一端被称为栈顶。咖啡厅的一摞盘子是现实世界中最常见的栈的例子。只能从上面取盘子,盘子洗净后,也只能摞在这一摞盘子的最上面。栈被称为一种后入先出(LIFO,last-in-first-out)的数据结构。

由于栈具有后入先出的特点,所有任何不在栈顶的元素都无法访问,为了拿到栈底的元素,必选先拿掉上面的元素。如图:

对于栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈,入栈使用push()方法。出栈使用pop()方法。

另外一个常用操作是预览栈顶的元素。pop()方法虽然可以访问栈顶的元素,但是调用该方法后,栈顶的元素也从栈中永久的删除了。peek()方法则只返回栈顶元素,而不删除它。

为了记录栈顶元素的位置,同时也为了标记哪里可以增加新的元素。我们使用变量top,当向栈内压入元素时,该变量增大,从栈内弹出元素时,该变量减小。


push(),pop()和peek()是栈的三个主要操作方法,但是栈还有其他的方法和属性。clear()方法清除栈内所有元素,length属性记录栈内元素的个数。我们还定义了一个empty属性,用于表示栈内是否还有元素(使用length也可以达到同样的目的)。


二:栈的实现:

实现一个栈,当务之急是决定存储数据的底层数据结构。这里采用的是数组。

我们实现以Stack类的构造函数开始:

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

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

先来实现push()方法。当向栈内压入一个新元素时,需要将其保存在数组中top所对应的位置,然后将top加1.让其指向数组中的下一个空位置。

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

这里特别要注意++操作符的位置,它放在this.top的后面,这样新入栈的元素就被放在top的当前值对应的位置,然后再将top值加1.指向下一个位置。

pop()方法恰好与push()方法相反,它返回栈顶元素,同时将变量top的值减1.

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

peek()方法返回数组的第top-1个位置的元素,即栈顶元素:

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

如果对空数组调用peek()方法,结果为undefined。这是因为栈是空的,栈顶没有任何元素。

有时候需要知道栈内存储了多个元素。length()方法通过返回变量top值返回栈内元素的个数;

  function length() {    return this.top  }

最后,可以将top的值设置为0,轻松清空一个栈。

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

附:测试代码

  function Stack() {    this.dataStore = [];    this.top = 0;    this.push = push;    this.pop = pop;    this.peek = peek;    this.clear = clear;    this.length = length;  }  //压入栈  function push (element) {    this.dataStore[this.top++] = element;  }  //弹出栈  function pop() {    return this.dataStore[--this.top]  }  //栈顶元素  function peek() {      // if (this.dataStore[this.top - 1] == undefined) {    //   return "none"    // }    return this.dataStore[this.top - 1]  }  //清空栈  function clear() {    this.top = 0;  }  //栈元素个数  function length() {    return this.top  }  var newstak = new Stack();  newstak.push("牛牛")  newstak.push("豆豆")  newstak.push("花花")  console.log(newstak.length())  console.log(newstak.peek())  var poped = newstak.pop();  console.log(poped);//  console.log(newstak.peek());//  newstak.clear();  console.log(newstak.length())  console.log(newstak.peek());  newstak.push("羊羊");  console.log(newstak);  console.log(newstak.peek());

三.使用Stack类 

有一些问题特别适合用栈来解决,先介绍几个例子:

1.数制间互相转换

可以利用栈将一个数字从一种数值转换成另一种数制。假设想将数字n转换为以b为基数的数字。实现转换算法如下:

  • 1.最高位为 n % b ,将此位压入栈
  • 2.使用n / b 代替n
  • 3.重复步骤1和2,直到n等于0,且没有余数。
  • 4.持续将栈内元素弹出,直到栈为空。依次将这些元素排列,就得到转换后数字的字符串形式。
  • (此算法只征对基数为2-9的情况)

使用栈,在javascript中实现该算法就很容易,下面就是该函数的定义,可以将数字转化为二至九进制的数字。

  function mulBase(num, base) {    var s = new Stack();    do {      s.push(num % base);      num = Math.floor(num /= base);    } while (num > 0);    var converted = "";    while(s.length() > 0) {      converted += s.pop()    }    return converted;  }

下面展示了如果使用该方法将数字转换为二进制和八进制数。
将数字转换为二进制和八进制。

  function mulBase(num, base) {    var s = new Stack();    do {      s.push(num % base);      num = Math.floor(num /= base);    } while (num > 0);    var converted = "";    while(s.length() > 0) {      converted += s.pop()    }    return converted;  }  var num = 32;  var base = 2;  var newNum = mulBase(num, base);  //32 converted to base 2 is 100000  console.log(num + " converted to base " + base + " is " + newNum)  num = 125;  base = 8;  var newNum = mulBase(num, base);  //125 converted to base 8 is 175  console.log(num + " converted to base " + base + " is " + newNum)

2.回文。


回文是这样一种现象:一个单词,短语或数字,从前往后写和往后写都是一样的。比如: 单词"dad","racecar"就是回文。如果忽略空格和标点符号,下面的句子也是回文。“A man, a plan, a canal:Panama”; 数字1001也是回文。

使用栈,可以轻松判断一个字符串是否回文。我们将拿到的自字符串的每个字符按照从左至右的顺序压入栈。当字符串的字符都入栈后,栈内就保存了一个反转的字符串,最后的字符串在栈顶,第一个字符串在栈底。

字符串完整压入栈内后,通过持续弹出栈中的每个字母就可以得到一个新字符串,该字符串刚好与原来的字符串顺序相反。我们只需比较两个字符串即可。如果他们相等,就是一个回文。

例子:判断给定字符串是否回文。

  function isPalindrome(word) {    var s = new Stack();    for (var i = 0; i < word.length; ++i) {      s.push(word[i]);    }    var word = "";    while(s.length() > 0) {      rword += s.pop();    }    if (word == rword) {      return true;    }    else {      return false;    }  }  var word = "hello";  if (isPalindrome(word)) {    console.log(word + " 是回文的");  } else {    console.log(word + " 不是回文的")  }  var word = "racecar";  if (isPalindrome(word)) {    console.log(word + " 是回文的");  } else {    console.log(word + " 不是回文的")  }

三:递归演示;

栈常用来实现编程语言,使用栈实现递归即为一例(这里只用栈来模拟递归过程)。

为了演示如何用栈实现递归,考虑以下求阶乘的递归定义。首先看看5的阶乘是如何定义的

5! = 5*4*3*2*1 = 120

下面是一个递归函数,可以计算任何数字的阶乘

function factorial(n) {  if (n === 0) {  return 1;  } else {  return n * factorial(n - 1)  }}


使用栈来模拟计算5的阶乘,返回120

使用栈来模拟计算5!的过程,首先将数字从5到1压入栈,然后使用一个循环,将数字弹出连乘,就得到了5 的阶乘

  function fact(n) {    var s = new Stack();    while (n > 1) {      s.push(n--);    }    var product = 1;    while(s.length() > 0) {      product *= s.pop()    }    return product;  }

 

 (本章完结)

上一章:第三章:javascript: 列表 下一章:第五章: 队列