栈是一种很常见的数据结构之一,它也是一种高效的数据结构。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
栈内的元素只能通过列表的一端访问,这一端称为栈顶。咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子,盘子洗干净后,也只能放在这一摞盘子的最上面。所以栈被称为一种后入先出(LIFO,last-in-first-out)的数据结构。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
由于栈具有后入先出的的特点,所以任何不在栈顶的元素都无法访问。为了拿掉栈底的元素,必须拿掉上面的元素。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
下图是一个栈操作示意图:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
那么javascript中如何实现栈呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
1.对栈的操作文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
我们可以定义:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
使用push()方法将元素压入栈,用pop()方法将一个元素弹出栈,使用peek()方法预览栈顶元素,因为使用pop()方法后返回栈顶元素,栈顶元素也从栈中移除了。而可以用peek()方法对栈顶元素读取而不删除。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
top变量用来记录栈顶元素的位置,当向栈中添加元素时,top增大,从栈中弹出元素时,top减小。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
clear()方法清除栈中的所有元素;length()方法返回栈中元素的个数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
2.栈的实现文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
我们定义一个Stack类的构造函数来实现栈的功能;大概结构为文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
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保存栈内元素。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
push()方法向栈内压入一个新元素时,需要将其保存在数组中变量top所在的位置,然后时top自增,让其指向数组中下一个空位置。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
pop()方法与push()相反,它返回栈顶元素,同时将top减1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
peek()方法返回数组的第top-1个位置的元素,即栈顶元素。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
3.使用Stack类文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
- 数制间的相互转换(基数为2-9)。算法如下:
(1).最高位为 n % b,将此位压入栈。
(2). 使用 n/b 代替 n。
(3). 重复步骤1和2,直到 n = 0,且没有余数。
(4). 持续将栈内元素弹出,直到栈为空,依次将这些元素排列文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
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.使用栈实现阶乘的递归文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
使用栈来模拟5!的过程,首先将数字5到1压入栈,然后使用一个循环将数字挨个弹出并连乘。如下所示文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
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中栈的实现,其实前端工程师还是有必要了解数据结构和算法的知识的,如果不重视数据结构和算法,那么你可能永远只能是个切图仔。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html
以上内容引自 Michael McMillan--《数据结构与算法Javascript描述》文章源自菜鸟学院-https://www.cainiaoxueyuan.com/gcs/12489.html