jq返回顶部js代码(jquery返回上一个页面)

小米IPO涉嫌披露违规，小米首次公开承认；郭台铭：富士康员工爱加班，因为多挣钱；58同城回应招聘陷阱...

----【IT服务圈儿报】第123期

脚本之家粉丝福利

想要书来点我?

　　作者：行无忌

　　https://hx-dl.github.io/hx-dl.github.io/2018/06/15/如何用Java手动实现一个栈/

什么是栈（Stack）

栈是一种遵从后进先出（LIFO）原则的有序集合

新添加的或待删除的元素都保存在栈的末尾，称为栈顶，另一端叫栈底

在栈里，新元素都靠近栈顶，旧元素都接近栈底

　　现实中的例子

在生活中也能发现很多栈的例子。例如，厨房里堆放的盘子，总是叠在上方的先被使用；输入框内容进行删除时，总是最后输入的先删除；弹夹中的子弹，越后装入的，越先发射......

　　手动实现一个栈

首先，创建一个类来表示栈

function Stack () { }

我们需要选择一种数据结构来保存栈里的元素，可以选择数组

function Stack(){

var items = []; //用来保存栈里的元素

}

接下来，为栈添加一些方法

push(element(s)); //添加新元素到栈顶

pop(); //移除栈顶的元素，同时返回被移除的元素

peek(); //返回栈顶的元素，不对栈做任何修改

isEmpty(); //如果栈里没有任何元素就返回true，否则false

clear(); //移除栈里的所有元素

size(); //返回栈里的元素个数,类似于数组的length属性

我们需要实现的第一个方法时 push。用来往栈里添加新元素，有一点很重要：该方法只添加到栈顶，也就是栈的末尾。所以，可以这样写：

this.push = function (element) {

items.push(element);

}

利用数组的 push 方法，就可以实现在栈顶末尾添加新的元素了。

接着，来实现 pop方法，用来实现移除栈里的元素。栈遵从 LIFO（后进先出）原则。移出去的是最后添加进去的元素。因此，可以使用数组的 pop 方法。

this.pop = function () {

return items.pop();

}

这样一来，这个栈自然就遵从了 LIFO 原则

现在，再来为这个栈添额外的辅助方法。

如果想知道栈里最后添加的元素是什么，可以用 peek方法。这个方法将返回栈顶的元素

this.peek = function () {

return items[items.length-1];

}

因为类内部是用数组保存元素的，所以这里访问数组最后一个元素用 length-1

下一个要实现的方法是 isEmpty, 如果栈为空的话，就返回 true，否则返回 false：

this.isEmpty = function () {

return items.length == 0;

}

使用 isEmpty 方法，就能简单地判断栈内部是否为空。

类似于数组地 length 属性，我们也可以实现栈地 length。

this.size = function () {

return items.length;

}

因为栈地内部使用数组保存元素，所以数组地 length 就是栈的长度。

实现 clear方法，clear 方法用来清空栈中所有的元素。最简单的实现方法是：

this.clear = function () {

items = [];

}

其实多次调用 pop 方法也可以，但是没有这个方法来的简单快捷。

最后，为了检查栈里的内容，还需要实现一个辅助方法： print。它会把栈里的元素都输出到控制台：

this.print = function () {

console.log(items.toString());

}

至此，我们就完整地创建了一个栈!

　　栈的完整代码

function Stack(){

var items = []; //用来保存栈里的元素

this.push = function (element) {

items.push(element);

}

this.pop = function () {

return items.pop();

}

this.peek = function () {

return items[items.length-1];

}

this.isEmpty = function () {

return items.length == 0;

}

this.size = function () {

return items.length;

}

this.clear = function () {

items = [];

}

this.print = function () {

console.log(items.toString());

}

}

使用 Stack 类

栈已经创建好了，我们来测试一下

首先，来初始化 Stack 类。然后，验证一下栈是否为空

var stack = new Stack();

console.log(stack.isEmpty()); //控制台输出true

接下来，往栈里面添加一下元素：

stack.push(5);

stack.push(8);

如果调用 peek 方法，很显然将会输出 8，因为它是栈顶的元素：

console.log(stack.peek()); //控制台输出8

再添加一个元素：

stack.push(11);

console.log(stack.size()); //控制台输出3

我们往栈里又添加了 11。如果调用 size 方法，输出为 3，因为栈里有三个元素（5，8 和 11）。如果这时候调用 isEmpty 方法，会看到输出了 false（因为此时栈不为空）。最后，再来往里面添加一个元素：

stack.push(15);

然后，调用两次 pop 方法从栈里移除两个元素：

stack.pop();

stack.pop();

console.log(stack.size()); //控制台输出2

stack.print(); //控制台输出[5,8]

到这里，整个栈的功能测试完成。

　　用栈来解决问题

使用栈来完成进制转换。

现实生活中，我们主要用 10 进制，但在计算科学中，二进制非常重要，因为计算机里所有的内容都是用二进制数字 0 和 1 来表示的。大学的计算机课都会先教进制转换。以二进制为例：

function divideBy2 (decNumber) {

var remStack = new Stack(),

rem,

binaryString = '';

while (decNumber>0) { //{1}

rem = Math.floor(decNumber % 2); //{2}

remStack.push(rem); //{3}

decNumber = Math.floor(decNumber / 2); //{4}

}

while (!remStack.isEmpty()) { //{5}

binaryString += remStack.pop().toString();

}

return binaryString;

}

这段代码里，当结果满足和 2 做整除的条件时，（行 {1}），我们会获得当前结果和 2 的余数，放到栈里（行 {2}、{3}）。然后让结果和 2 做整除（行 {4}）

　　注：Java 有数字类型，但是它不会区分时整数还是浮点数。因此，要使用 Math.floor 函数让除法的操作仅返回整数部分。

最后，用 pop 方法把栈中的元素都移除，把出栈的元素连接成字符串（行 {5}）。

测试一下：

console.log(divideBy2(520)); //输出1000001000

console.log(divideBy2(10)); //输出1010

console.log(divideBy2(1000)); //输出1111101000

接下来，可以很容易的修改上面的算法，使它能够把十进制转化为任何进制。除了让十进制数字和 2 整除转成二进制数，还可以传入其他任意进制的基数作为参数，就像下面的算法这样：

function baseConverter (decNumber, base) {

var remStack = new Stack(),

rem,

baseString = '';

digits = '0123456789ABCDEF'; //{6}

while (decNumber>0) {

rem = Math.floor(decNumber % base);

remStack.push(rem); //{3}

decNumber = Math.floor(decNumber / base);

}

while (!remStack.isEmpty()) {

baseString += digits[remStack.pop()]; //{7}

}

return baseString;

}

在将十进制转成二进制时，余数是 0 或 1；在将十进制转成八进制时，余数时 0-8 之间的数；但是将十进制转成十六进制时，余数时 0-9 之间的数字加上 A、B、C、D、E、F（对应 10、11、12、13、14 和 15）。因此，需要对栈中的数字做个转化才可以（行 {6}、{7}）。

来测试一下输出结果：

console.log(baseConverter(1231,2)); //输出10011001111

console.log(baseConverter(1231,8)); //输出2317

console.log(baseConverter(1231,16)); //输出4CF

显然是正确的。

　　小结

我们用 js 代码自己实现了栈。并且通过进制转换的例子来实际应用了它。栈的应用实例还有很多，比如平衡圆括号和汉诺塔。感兴趣可以自行百度去了解

　　：

?版权声明：转载文章和图片均来自公开网络，版权归作者本人所有，推送文章除非无法确认，我们都会注明作者和来源。如果出处有误或侵犯到原作者权益与我们联系删除或授权事宜。