javascript中栈的实现(带栈操作示意图)

栈是一种很常见的数据结构之一，它也是一种高效的数据结构。

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

由于栈具有后入先出的的特点，所以任何不在栈顶的元素都无法访问。为了拿掉栈底的元素，必须拿掉上面的元素。

下图是一个栈操作示意图：

那么javascript中如何实现栈呢？

1.对栈的操作

我们可以定义：

使用push()方法将元素压入栈，用pop()方法将一个元素弹出栈，使用peek()方法预览栈顶元素，因为使用pop()方法后返回栈顶元素，栈顶元素也从栈中移除了。而可以用peek()方法对栈顶元素读取而不删除。

top变量用来记录栈顶元素的位置，当向栈中添加元素时，top增大，从栈中弹出元素时，top减小。

clear()方法清除栈中的所有元素；length()方法返回栈中元素的个数

2.栈的实现

我们定义一个Stack类的构造函数来实现栈的功能；大概结构为

 1function Stack(){
 2this.top=0;
 3this.dataStore=[];
 4this.push=function push(element){
 5this.dataStore[this.top++]=element;
 6    };
 7this.pop=function pop(){
 8returnthis.dataStore[--this.top];
 9    };
10this.peek=function peek(){
11returnthis.dataStore[this.top-1];
12    };
13this.length=function length(){
14returnthis.top;
15    };
16this.clear=function clear(){
17this.dataStore.length=0;
18this.top=0;
19    }
20 }

用数组dataStore保存栈内元素。

push()方法向栈内压入一个新元素时，需要将其保存在数组中变量top所在的位置，然后时top自增，让其指向数组中下一个空位置。

pop()方法与push()相反，它返回栈顶元素，同时将top减1

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

3.使用Stack类

1. 数制间的相互转换(基数为2-9)。算法如下：

(1).最高位为 n % b，将此位压入栈。
　　　　(2). 使用 n/b 代替 n。
　　　　(3). 重复步骤1和2，直到 n = 0，且没有余数。
　　　　(4). 持续将栈内元素弹出，直到栈为空，依次将这些元素排列

 1function mulBase(num, base) {
 2var stack = new Stack();
 3do {
 4         stack.push(num % base);
 5         num = (num / base);
 6     } while (num > 0);
 7var newNum = '';
 8while(()>0){
 9         newNum+=()
10    }
11return newNum;
12}
1314 console.log(mulBase(10, 2)) //1010

2.使用栈实现阶乘的递归

使用栈来模拟5！的过程，首先将数字5到1压入栈，然后使用一个循环将数字挨个弹出并连乘。如下所示

 1function fact(num) {
 2var stack=new Stack();
 3while(num>0){
 4         stack.push(num--);
 5    }
 6var sum=1;
 7while(()>0){
 8         sum*=();
 9    }
10return sum;
11}
1213 console.log(fact(5)) //120

以上浅显的介绍的javascript中栈的实现，其实前端工程师还是有必要了解数据结构和算法的知识的，如果不重视数据结构和算法，那么你可能永远只能是个切图仔。

以上内容引自 Michael McMillan--《数据结构与算法Javascript描述》