「数据结构与算法Javascript描述」栈
1. 对栈的操作
栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端称为栈顶。咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子,盘子洗净后,也只能摞在这一摞盘子的最上面。栈被称为一种后入先出(LIFO,last-in-fifirst-out)的数据结构。
由于栈具有后入先出的特点,所以任何不在栈顶的元素都无法访问。为了得到栈底的元素,必须先拿掉上面的元素。
对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用 push()
方法,出栈使用 pop()
方法。下图演示了入栈和出栈的过程:
另一个常用的操作是预览栈顶的元素。pop()
方法虽然可以访问栈顶的元素,但是调用该方法后,栈顶元素也从栈中被永久性地删除了。peek()
方法则只返回栈顶元素,而不删除它。
为了记录栈顶元素的位置,同时也为了标记哪里可以加入新元素,我们使用变量 top
,当向栈内压入元素时,该变量增大;从栈内弹出元素时,该变量减小。push()
、pop()
和 peek()
是栈的 3 个主要方法,但是栈还有其他方法和属性。clear()
方法清除栈内所有元素,length
属性记录栈内元素的个数。我们还定义了一个 empty
属性,用以表示栈内是否含有元素,不过使用 length
属性也可以达到同样的目的。
2. 栈的实现
实现一个栈,当务之急是决定存储数据的底层数据结构。这里采用的是数组。
我们的实现以定义 Stack
类的构造函数开始:
function Stack() { this.data = []; this.top = 0; }
我们用数组 data
保存栈内元素,构造函数将其初始化为一个空数组。变量 top
记录栈顶位置,被构造函数初始化为 0,表示栈顶对应数组的起始位置 0。如果有元素被压入栈,该变量的值将随之变化。
先来实现 push()
方法。当向栈中压入一个新元素时,需要将其保存在数组中变量 top
所对应的位置,然后将 top
值加 1,让其指向数组中下一个空位置。代码如下所示:
Stack.prototype.push = function(element) { this.data[this.top++] = element; }
这里要特别注意 ++
操作符的位置,它放在 this.top
的后面,这样新入栈的元素就被放在 top
的当前值对应的位置,然后再将变量 top
的值加 1,指向下一个位置。
pop()
方法恰好与 push()
方法相反——它返回栈顶元素,同时将变量 top
的值减 1:
Stack.prototype.pop = function() { return this.data[--this.top]; }
peek()
方法返回数组的第 top-1
个位置的元素,即栈顶元素:
Stack.prototype.peek = function() { return this.data[this.top - 1]; }
如果对一个空栈调用 peek()
方法,结果为 undefined
。这是因为栈是空的,栈顶没有任何元素。
有时候需要知道栈内存储了多少个元素。length()
方法通过返回变量 top
值的方式返回栈内的元素个数:
Stack.prototype.length = function() { return this.top; }
最后,可以将变量 top
的值设为 0,轻松清空一个栈:
Stack.prototype.clear = function() { this.top = 0; }
接下来我们测试一下 Stack
类的实现:
const s = new Stack(); s.push("夏安1"); s.push("夏安2"); s.push("夏安3"); console.log("length: " + s.length()); console.log(s.peek()); const popped = s.pop(); console.log("The popped element is: " + popped); console.log(s.peek()); s.push("夏安4"); console.log(s.peek()); s.clear(); console.log("length: " + s.length()); console.log(s.peek()); s.push("夏安5"); console.log(s.peek());
测试代码输出结果为:
length: 3 夏安3 The popped element is: 夏安3 夏安2 夏安4 length: 0 undefined 夏安5
倒数第二行返回 undefined
,这是因为栈被清空后,栈顶就没值了,这时使用 peek()
方法预览栈顶元素,自然得到 undefined
。
3. 使用Stack类
3.1 数制间的相互转换
可以利用栈将一个数字从一种数制转换成另一种数制。假设想将数字 n 转换为以 b 为基数的数字,实现转换的算法如下:
- 最高位为
n % b
,将此位压入栈。 - 使用
n/b
代替n
。 - 重复步骤 1 和 2,直到
n
等于 0,且没有余数。 - 持续将栈内元素弹出,直到栈为空,依次将这些元素排列,就得到转换后数字的字符串形式。
「此算法只针对基数为 2~9 的情况。」
使用栈,在 JavaScript
中实现该算法就是小菜一碟。下面就是该函数的定义,可以将数字转化为二至九进制的数字:
function mulBase(num, base) { const s = new Stack(); do { s.push(num % base); num = Math.floor(num /= base); } while (num > 0); let converted = ""; while (s.length() > 0) { converted += s.pop(); } return converted; }
3.2 回文
回文是指这样一种现象:一个单词、短语或数字,从前往后写和从后往前写都是一样的。比如,单词“dad”、“racecar”就是回文;如果忽略空格和标点符号,下面这个句子也是回文,“A man, a plan, a canal: Panama”;数字 1001 也是回文。
使用栈,可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后,栈内就保存了一个反转后的字符串,最后的字符在栈顶,第一个字符在栈底。
字符串完整压入栈内后,通过持续弹出栈中的每个字母就可以得到一个新字符串,该字符串刚好与原来的字符串顺序相反。我们只需要比较这两个字符串即可,如果它们相等,就是一个回文。
下面是一个利用前面定义的 Stack
类,判断给定字符串是否是回文的程序。
function isPalindrome(word) { const s = new Stack(); for (let i = 0; i < word.length; i++) { s.push(word[i]); } let rword = ""; while (s.length() > 0) { rword += s.pop(); } return word === rword; }
3.3 递归演示
为了演示如何用栈实现递归,考虑一下求阶乘函数的递归定义。首先看看 5 的阶乘是怎么定义的:
5! = 5 × 4 × 3 × 2 × 1 = 120
下面是一个递归函数,可以计算任何数字的阶乘:
function factorial(n) { if (n === 0) { return 1; } else { return n * factorial(n - 1); } }
使用栈来模拟计算 5! 的过程,首先将数字从 5 到 1 压入栈,然后使用一个循环,将数字挨个弹出连乘,就得到了正确的答案。
function fact(n) { const s = new Stack(); while (n > 1) { s.push(n--); } let product = 1; while (s.length() > 0) { product *= s.pop(); } return product; }