日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
JavaScript實現(xiàn)棧結(jié)構(gòu)（Stack）

本文轉(zhuǎn)載自微信公眾號「泰斗賢若如」，作者AhuntSun 。轉(zhuǎn)載本文請聯(lián)系泰斗賢若如公眾號。

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比鐘樓網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式鐘樓網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務覆蓋鐘樓地區(qū)。費用合理售后完善，十余年實體公司更值得信賴。

一、前言

1.1.什么是數(shù)據(jù)結(jié)構(gòu)?

數(shù)據(jù)結(jié)構(gòu)就是在計算機中，存儲和組織數(shù)據(jù)的方式。

例如：圖書管理，怎樣擺放圖書才能既能放很多書，也方便取?

主要需要考慮兩個問題：

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

「常見的數(shù)據(jù)結(jié)構(gòu)：」

  • 「數(shù)組」(Aarray)
  • 「?！?Stack)
  • 「鏈表」(Linked List)
  • 「圖」(Graph)
  • 「散列表」(Hash)
  • 「隊列」(Queue)
  • 「樹」(Tree)
  • 「堆」(Heap)

「注意」：數(shù)據(jù)結(jié)構(gòu)與算法與語言無關(guān)，常見的編程語言都有「直接或間接」的使用上述常見的數(shù)據(jù)結(jié)構(gòu)。

1.2.什么是算法?

算法(Algorithm)的定義

  • 一個有限指令集，每條指令的描述不依賴于語言;
  • 接收一些輸入(有些情況下不需要輸入);
  • 產(chǎn)生輸入;
  • 一定在有限步驟之后終止;

算法通俗理解：解決問題的辦法/步驟邏輯。數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，離不開算法。

二、棧結(jié)構(gòu)(Stack)

2.1.簡介

數(shù)組是一個線性結(jié)構(gòu)，并且可以在數(shù)組的「任意位置」插入和刪除元素。而「棧和隊列」就是比較常見的「受限的線性結(jié)構(gòu)」。如下圖所示：

image-20200226131817102

棧的特點為「先進后出，后進先出」(LIFO：last in first out)。

「程序中的棧結(jié)構(gòu)：」

  • 「函數(shù)調(diào)用?！梗篈(B(C(D())))：即A函數(shù)中調(diào)用B，B調(diào)用C，C調(diào)用D;在A執(zhí)行的過程中會將A壓入棧，隨后B執(zhí)行時B也被壓入棧，函數(shù)C和D執(zhí)行時也會被壓入棧。所以當前棧的順序為：A->B->C->D(棧頂);函數(shù)D執(zhí)行完之后，會彈出棧被釋放，彈出棧的順序為D->C->B->A;
  • 「遞歸」：為什么沒有停止條件的遞歸會造成棧溢出?比如函數(shù)A為遞歸函數(shù)，不斷地調(diào)用自己(因為函數(shù)還沒有執(zhí)行完，不會把函數(shù)彈出棧)，不停地把相同的函數(shù)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()：移除棧頂?shù)脑?，同時返回被移除的元素;
  • peek()：返回棧頂?shù)脑兀粚Ｗ鋈魏涡薷?該方法不會移除棧頂?shù)脑?，僅僅返回它);
  • isEmpty()：如果棧里沒有任何元素就返回true，否則返回false;
  • size()：返回棧里的元素個數(shù)。這個方法和數(shù)組的length屬性類似;
  • toString()：將棧結(jié)構(gòu)的內(nèi)容以字符串的形式返回。

2.2.封裝棧類

「代碼實現(xiàn)：」

 
 
 
 
    
  
  
  
  
  1. // 封裝棧類
    2. 
  
  
  
  
  2.     function Stack(){
    3. 
  
  
  
  
  3.       // 棧中的屬性
    4. 
  
  
  
  
  4.       this.items =[]
    5. 
  
  
  
  
  5. 
  
  
  
  
  6.       // 棧的相關(guān)操作
    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.       // 利用數(shù)組item的push方法實現(xiàn)Stack類的pop方法
    15. 
  
  
  
  
  15.         this.items.push(element)
    16. 
  
  
  
  
  16.       }
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.       // 2.pop():從棧中取出元素
    19. 
  
  
  
  
  19.       Stack.prototype.pop = () => {
    20. 
  
  
  
  
  20.       // 利用數(shù)組item的pop方法實現(xiàn)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類沒有l(wèi)ength屬性啊)，而是           Stack類中定義的數(shù)組items才有l(wèi)ength屬性呀
    32. 
  
  
  
  
  32.         return this.items.length == 0 
    33. 
  
  
  
  
  33.       }
    34. 
  
  
  
  
  34. 
  
  
  
  
  35.       // 5.size():獲取棧中元素的個數(shù)
    36. 
  
  
  
  
  36.       Stack.prototype.size = () => {
    37. 
  
  
  
  
  37.         return this.items.length
    38. 
  
  
  
  
  38.       }
    39. 
  
  
  
  
  39. 
  
  
  
  
  40.       // 6.toString():以字符串形式輸出棧內(nèi)數(shù)據(jù)
    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.

「測試結(jié)果：」

image-20200305205050816

「棧結(jié)構(gòu)的簡單應用：」

利用棧結(jié)構(gòu)的特點封裝十進至轉(zhuǎn)換為二進至的函數(shù)：

 
 
 
 
    
  
  
  
  
  1. //簡單應用：
    2. 
  
  
  
  
  2.     //封裝函數(shù)：將十進制轉(zhuǎn)成二進制(十轉(zhuǎn)二的運算最后倒敘取余的特點符合棧'先進后出')
    3. 
  
  
  
  
  3.     let dec2bin = decNumber => {
    4. 
  
  
  
  
  4.       //1.定義一個棧對象，保存余數(shù)
    5. 
  
  
  
  
  5.       var  stack = new Stack()
    6. 
  
  
  
  
  6. 
  
  
  
  
  7.       // 2.循環(huán)操作
    8. 
  
  
  
  
  8.       while(decNumber > 0){
    9. 
  
  
  
  
  9.         // 2.1.獲取余數(shù)并放入棧中
    10. 
  
  
  
  
  10.         stack.push(decNumber % 2)
    11. 
  
  
  
  
  11.         // 2.2.獲取整除后的結(jié)果作為下一次運算的數(shù)字(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.

「測試結(jié)果：」

image-20200305205547226


網(wǎng)站名稱：JavaScript實現(xiàn)棧結(jié)構(gòu)（Stack）
文章URL：http://m.5511xx.com/article/cojidds.html