Javascript数据结构与算法--栈的实现与用法

栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或者待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

我们在生活中常能看到栈的例子。整齐堆起来的书，厨房堆起的盘子等

栈也被用在编程语言的编译器和内存中保存变量、方法调用等。

我们可以，在这里，我们选择数组来保存栈中的元素。

/** * 使用es6中的Class语法来编写类：栈 * 此栈使用数组来保存元素 */ class Stack { constructor() { this.items = []; } /** * 添加一个（或几个）新元素到栈顶 * @param {*} element 新元素 */ push(element) { this.items.push(element) } /** * 移除栈顶的元素，同时返回被移除的元素 */ pop() { return this.items.pop() } /** * 返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它） */ peek() { return this.items[this.items.length - 1] } /** * 如果栈里没有任何元素就返回true,否则返回false */ isEmpty() { return this.items.length === 0 } /** * 移除栈里的所有元素 */ clear() { this.items = [] } /** * 返回栈里的元素个数。这个方法和数组的length属性很类似 */ size() { return this.items.length } /** * 返回以字符串形式输出的栈 */ toString() { return this.items.toString() } /** * 返回以数组形式输出的栈 */ toArray() { return this.items } } 栈的用法 进制转换

在计算机里所有的内容都是二进制数字表示的（0和1），而我们生活中主要用到十进制，还有16进制等。那么就需要进制转换。我们可以利用栈来实现转换。

/** * 10进制数转换为其他16进制以内进制的数 * @param {*} decNumber 需要转换的数 * @param {Int32Array} hex 进制数 */ function hexConverter(decNumber, hex) { let remStack = new Stack() let rem = 0 let baseString = '' let digits = '0123456789ABCDEF' //进制取数 if (hex < 2 || hex > 16) { return '只转换大于二进制小于十六进制之间的进制' } while (decNumber > 0) { rem = Math.floor(decNumber % hex) // 求模运算 remStack.push(rem) decNumber = Math.floor(decNumber / hex) // 除运算 } while (!remStack.isEmpty()) { baseString += digits[remStack.pop()] // 取出栈中的数据对应于进制数的表示数 } return baseString } 回文判断

正读反读都相同的字符序列称为回文，例如“abccba”、“abcba”、“12321”、“123321”。
回文判断有很多种方法，在这里，我们可以采用先入栈后出栈的方法，来比较入栈之前，和出栈之后两个字符串是否相同。
空字符串到底是不是回文呢，有点疑惑？ 我这里定义为不是回文。

/** * 判断字符串是否为回文 * @param {String} str 要判断的字符串 */ function palindrome(str) { // 非string类型的 或者 空字符串 直接判断不是回文 if (typeof (str) !== 'string' || str.length === 0) { return false } let stack = new Stack() let oStr = str.toLocaleLowerCase() let nStr = '' for (let i = 0; i < str.length; i++) { stack.push(str[i]) } while (!stack.isEmpty()) { nStr += stack.pop().toLocaleLowerCase() } if (nStr === oStr) { // return `输入的字符串【{$oStr}】是回文` return true } else { // return `输入的字符串【{$oStr}】不是回文` return false } } 平衡括号

如果一个括号序列包含完整的左右括号对，则称为平衡括号序列。如："{[()]}","", "({})", "{()}"都是平衡括号，而"{()[]", ")"则不是平衡括号。

括号只有三种()/[]/{}，每种分别有左右括号。我们可以这样操作：遇到左括号，左括号入栈，遇到右括号，取出栈中最后一个括号来比对的方式来判断是否相等平衡。

/** * 判断括号序列是否平衡,空序列也算是平衡 * @param {String} brackets 括号序列 */ function balanceBracket(brackets) { if (typeof (brackets) !== 'string') { return false } let left = '([{' let right = ')]}' let num = 0 // 括号的对数 let stack = new Stack() for (let i = 0; i < brackets.length; i++) { if (right.indexOf(brackets[0]) > -1) { return false } if (left.indexOf(brackets[i]) > -1) { stack.push(brackets[i]) num++ } else { if (right.indexOf(brackets[i]) > -1) { let topBracket = stack.pop() let rightSort = right.indexOf(brackets[i]) let leftSort = left.indexOf(topBracket) if (rightSort !== leftSort) { return false } } } } return `是平衡括号序列。有${num}对括号` } 汉诺塔

有三根相邻的柱子，标号为A,B,C。A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有圆盘移动到B柱子上。
要求：

每次只能移动一个圆盘。

每根柱子上的圆盘，下面的都比上面的大。