JavaScript实现栈结构（Stack）

本文转载自微信公众号「泰斗贤若如」，作者AhuntSun 。转载本文请联系泰斗贤若如公众号。

创新互联-专业网站定制、快速模板网站建设、高性价比钟楼网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式钟楼网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖钟楼地区。费用合理售后完善，十余年实体公司更值得信赖。

一、前言

1.1.什么是数据结构?

数据结构就是在计算机中，存储和组织数据的方式。

例如：图书管理，怎样摆放图书才能既能放很多书，也方便取?

主要需要考虑两个问题：

  • 操作一：新书怎么插入?
  • 操作二：怎么找到某本指定的书?

「常见的数据结构：」

  • 「数组」(Aarray)
  • 「栈」(Stack)
  • 「链表」(Linked List)
  • 「图」(Graph)
  • 「散列表」(Hash)
  • 「队列」(Queue)
  • 「树」(Tree)
  • 「堆」(Heap)

「注意」：数据结构与算法与语言无关，常见的编程语言都有「直接或间接」的使用上述常见的数据结构。

1.2.什么是算法?

算法(Algorithm)的定义

  • 一个有限指令集，每条指令的描述不依赖于语言;
  • 接收一些输入(有些情况下不需要输入);
  • 产生输入;
  • 一定在有限步骤之后终止;

算法通俗理解：解决问题的办法/步骤逻辑。数据结构的实现，离不开算法。

二、栈结构(Stack)

2.1.简介

数组是一个线性结构，并且可以在数组的「任意位置」插入和删除元素。而「栈和队列」就是比较常见的「受限的线性结构」。如下图所示：

image-20200226131817102

栈的特点为「先进后出，后进先出」(LIFO：last in first out)。

「程序中的栈结构：」

  • 「函数调用栈」：A(B(C(D())))：即A函数中调用B，B调用C，C调用D;在A执行的过程中会将A压入栈，随后B执行时B也被压入栈，函数C和D执行时也会被压入栈。所以当前栈的顺序为：A->B->C->D(栈顶);函数D执行完之后，会弹出栈被释放，弹出栈的顺序为D->C->B->A;
  • 「递归」：为什么没有停止条件的递归会造成栈溢出?比如函数A为递归函数，不断地调用自己(因为函数还没有执行完，不会把函数弹出栈)，不停地把相同的函数A压入栈，最后造成「栈溢出」(Stack Overfloat)

3.练习：题目：有6个元素6，5，4，3，2，1按顺序进栈，问下列哪一个不是合法的出栈顺序?

  • A：5 4 3 6 1 2 (√)
  • B：4 5 3 2 1 6 (√)
  • C：3 4 6 5 2 1 (×)
  • D：2 3 4 1 5 6 (√)

题目所说的按顺序进栈指的不是一次性全部进栈，而是有进有出，进栈顺序为6 -> 5 -> 4 -> 3 -> 2 -> 1。

解析：

  • A答案：65进栈，5出栈，4进栈出栈，3进栈出栈，6出栈，21进栈，1出栈，2出栈(整体入栈顺序符合654321);
  • B答案：654进栈，4出栈，5出栈，3进栈出栈，2进栈出栈，1进栈出栈，6出栈(整体的入栈顺序符合654321);
  • C答案：6543进栈，3出栈，4出栈，之后应该5出栈而不是6，所以错误;
  • D答案：65432进栈，2出栈，3出栈，4出栈，1进栈出栈，5出栈，6出栈。符合入栈顺序;

「栈常见的操作：」

  • push(element)：添加一个新元素到栈顶位置;
  • pop()：移除栈顶的元素，同时返回被移除的元素;
  • peek()：返回栈顶的元素，不对栈做任何修改(该方法不会移除栈顶的元素，仅仅返回它);
  • isEmpty()：如果栈里没有任何元素就返回true，否则返回false;
  • size()：返回栈里的元素个数。这个方法和数组的length属性类似;
  • toString()：将栈结构的内容以字符串的形式返回。

2.2.封装栈类

「代码实现：」

 
 
 
 
    
  
  
  
  
  1. // 封装栈类
    2. 
  
  
  
  
  2.     function Stack(){
    3. 
  
  
  
  
  3.       // 栈中的属性
    4. 
  
  
  
  
  4.       this.items =[]
    5. 
  
  
  
  
  5. 
  
  
  
  
  6.       // 栈的相关操作
    7. 
  
  
  
  
  7.       // 1.push():将元素压入栈
    8. 
  
  
  
  
  8.       //方式一(不推荐)：给对象添加方法，其他对象不能复用
    9. 
  
  
  
  
  9.       // this.push = () => {
    10. 
  
  
  
  
  10.       // }
    11. 
  
  
  
  
  11.       
    12. 
  
  
  
  
  12.       //方式二(推荐)：给Stack类添加方法，能够多对象复用
    13. 
  
  
  
  
  13.       Stack.prototype.push = function(element) {
    14. 
  
  
  
  
  14.       // 利用数组item的push方法实现Stack类的pop方法
    15. 
  
  
  
  
  15.         this.items.push(element)
    16. 
  
  
  
  
  16.       }
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.       // 2.pop():从栈中取出元素
    19. 
  
  
  
  
  19.       Stack.prototype.pop = () => {
    20. 
  
  
  
  
  20.       // 利用数组item的pop方法实现Stack类的pop方法
    21. 
  
  
  
  
  21.         return this.items.pop()
    22. 
  
  
  
  
  22.       }
    23. 
  
  
  
  
  23. 
  
  
  
  
  24.       // 3.peek():查看一下栈顶元素
    25. 
  
  
  
  
  25.       Stack.prototype.peek = () => {
    26. 
  
  
  
  
  26.         return this.items[this.items.length - 1]
    27. 
  
  
  
  
  27.       }
    28. 
  
  
  
  
  28. 
  
  
  
  
  29.       // 4.isEmpty():判断栈是否为空
    30. 
  
  
  
  
  30.       Stack.prototype.isEmpty = () => {
    31. 
  
  
  
  
  31.       // 两个小时的教训啊不是this.length(不是Stack对象的length，Stack类没有length属性啊)，而是           Stack类中定义的数组items才有length属性呀
    32. 
  
  
  
  
  32.         return this.items.length == 0 
    33. 
  
  
  
  
  33.       }
    34. 
  
  
  
  
  34. 
  
  
  
  
  35.       // 5.size():获取栈中元素的个数
    36. 
  
  
  
  
  36.       Stack.prototype.size = () => {
    37. 
  
  
  
  
  37.         return this.items.length
    38. 
  
  
  
  
  38.       }
    39. 
  
  
  
  
  39. 
  
  
  
  
  40.       // 6.toString():以字符串形式输出栈内数据
    41. 
  
  
  
  
  41.       Stack.prototype.toString = () => {
    42. 
  
  
  
  
  42.         //希望输出的形式：20 10 12 8 7
    43. 
  
  
  
  
  43.         let resultString = ''
    44. 
  
  
  
  
  44.         for (let i of this.items){
    45. 
  
  
  
  
  45.           resultString += i + ' '
    46. 
  
  
  
  
  46.         }
    47. 
  
  
  
  
  47.         return resultString
    48. 
  
  
  
  
  48.       }
    49. 
  
  
  
  
  49.     }
    50.

「测试代码：」

 
 
 
 
    
  
  
  
  
  1. // 栈的使用
    2. 
  
  
  
  
  2.    let  s = new Stack()
    3. 
  
  
  
  
  3.    s.push(20)
    4. 
  
  
  
  
  4.    s.push(10)
    5. 
  
  
  
  
  5.    s.push(100)
    6. 
  
  
  
  
  6.    s.push(77)
    7. 
  
  
  
  
  7.    console.log(s)                                                   //65
    8. 
  
  
  
  
  8. 
  
  
  
  
  9.    console.log(s.pop());                                            //68
    10. 
  
  
  
  
  10.    console.log(s.pop());                                            //69
    11. 
  
  
  
  
  11.    
    12. 
  
  
  
  
  12.    console.log(s.peek());                                           //71
    13. 
  
  
  
  
  13. console.log(s.isEmpty());                                       //72
    14. 
  
  
  
  
  14.   
    15. 
  
  
  
  
  15.    console.log(s.size());                                           //74
    16. 
  
  
  
  
  16.    console.log(s.toString());                                       //75
    17.

「测试结果：」

image-20200305205050816

「栈结构的简单应用：」

利用栈结构的特点封装十进至转换为二进至的函数：

 
 
 
 
    
  
  
  
  
  1. //简单应用：
    2. 
  
  
  
  
  2.     //封装函数：将十进制转成二进制(十转二的运算最后倒叙取余的特点符合栈'先进后出')
    3. 
  
  
  
  
  3.     let dec2bin = decNumber => {
    4. 
  
  
  
  
  4.       //1.定义一个栈对象，保存余数
    5. 
  
  
  
  
  5.       var  stack = new Stack()
    6. 
  
  
  
  
  6. 
  
  
  
  
  7.       // 2.循环操作
    8. 
  
  
  
  
  8.       while(decNumber > 0){
    9. 
  
  
  
  
  9.         // 2.1.获取余数并放入栈中
    10. 
  
  
  
  
  10.         stack.push(decNumber % 2)
    11. 
  
  
  
  
  11.         // 2.2.获取整除后的结果作为下一次运算的数字(floor:向下取整)
    12. 
  
  
  
  
  12.         decNumber = Math.floor(decNumber / 2)
    13. 
  
  
  
  
  13.       }
    14. 
  
  
  
  
  14. 
  
  
  
  
  15.       // 3.从栈中取出0和1
    16. 
  
  
  
  
  16.       let  binaryString = '';
    17. 
  
  
  
  
  17.       let a = stack.items.length
    18. 
  
  
  
  
  18.      while(stack.items.length != 0){
    19. 
  
  
  
  
  19.         binaryString += stack.pop();
    20. 
  
  
  
  
  20.       }
    21. 
  
  
  
  
  21.       return binaryString;
    22. 
  
  
  
  
  22.     }
    23. 
  
  
  
  
  23.     
    24. 
  
  
  
  
  24.     //测试代码
    25. 
  
  
  
  
  25.     console.log(dec2bin(10));                                       //103
    26. 
  
  
  
  
  26.     console.log(dec2bin(100));                                      //104
    27. 
  
  
  
  
  27.     console.log(dec2bin(1000));                                     //105
    28.

「测试结果：」

image-20200305205547226

本文名称：JavaScript实现栈结构（Stack）
网站地址：http://www.stwzsj.com/qtweb/news3/11303.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

企业建站知识

同城分类信息

乐山网站建设　　 　成都网站推广　　 　成都网站设计　　 　成都定制网站建设　　 　成都网站建设　　 　腾讯免备案主机　　 　物流公司网站建设方案　　 　簇桥薇薇新娘　　 　定制网站制作　　 　成都全屋定制　　 　网站推广公司　　 　wap网站制作　　 　成都ssl证书认证　　 　定制网站　　 　LED亮化工程　　 　四川柴油发电机　　 　联通机柜租用　　 　成都网站设计　　 　高端网站设计　　 　广安搬家公司