JavaScript數據結構《棧》

nanchen2251 發布于2019-08-21 16:44 / 370人閱讀

摘要：我們都知道數組是里面比較常用的一種數據結構，棧和數組類似，定義如下棧是一種遵從后進先出原則的有序集合。新增加和待刪除的元素都保存在棧的尾部，也稱棧頂，相反的另一端就叫棧底，在棧的這種數據結構里面，我們新增的元素都在棧頂，舊的元素都在棧底。

由于不是計算機專業出身，對數據結構這些了解的比較少，最近看了一些相關的書籍，這里做一些總結。本篇要說的是棧。我們都知道數組是JavaScript里面比較常用的一種數據結構，棧和數組類似，定義如下

棧是一種遵從后進先出 (LIFO) 原則的有序集合。新增加和待刪除的元素都保存在棧的尾部，也稱棧頂，相反的另一端就叫棧底，在棧的這種數據結構里面，我們新增的元素都在棧頂，舊的元素都在棧底。

舉一個生活中的例子，我們平時吃完飯洗盤子的時候，我們都會把洗好的盤子一個個堆疊起來，先放進去的盤子就是我們棧里面比較舊的元素（棧底），后放的盤子就是比較新的盤子（棧頂），然后我們要把一個盤子拿下來的時候我們都是從上面開始拿（棧頂），這里就是后放進去的盤子先拿出來了，所以這里就遵循了后進先出 (LIFO) 的原則了。

代碼實現

代碼全部采用ES6的語法，首先我們定義一個類Stack來表示棧，然后為該類實現一些方法來模擬棧的行為

class Stack {

  constructor() {
    // 定義一個數組來保存棧里面的元素
    this.items = []
  }

  // 添加元素到棧頂
  push() { }
  // 從棧頂移除元素，同時返回被移除元素
  pop() { }
  // 返回棧頂的元素，不對棧本身做修改
  peek() { }
  // 判斷棧是否為空
  isEmpty() { }
  // 清空棧
  remove() { }
  // 返回棧里面元素的個數
  length() { }
}

這樣我們就定義好一個基類了，下面來分別實現棧的行為方法

push

我們要實現的第一個方法（行為）就是push，push方法會向棧的棧頂新增元素，因為我們是用數組來保存棧里面的元素的，所以這個方法的實現很簡單，直接用JavaScript數組的push方法就好了。

push(item) {
    this.items.push(item)
}

pop

接下來要實現是pop方法（行為），pop會移除棧頂的元素并且會返回被移除的元素，這個方法我們同樣可以用JavaScript數組的pop方法來實現

pop() {
    return this.items.pop()
}

peek

peek方法（行為）返回棧頂的最后一個元素，不對棧本身做修改，我們可以用Array.length-1來獲取數組的最后一個元素，所以peek方法可以這樣寫

peek() {
    return this.items[this.items.length-1]
}

isEmpty

isEmpty方法用來判斷棧是否為空，用數組來表示就是數組的 length 是否等于0，所以我們可以得出如下代碼

isEmpty() {
    return this.items.length === 0
}

remove

remove 方法用來清空棧里面所有的元素，實現這個方法是最簡單的了，直接讓數組等于一個新的空數組就好了

remove() {
    this.items = []
}

length

最后要實現的是length方法，length方法返回棧的大小，這個同樣可以用數組的length來實現

length() {
    return this.items.length
}

這里我們添加一個輔助print方法來打印棧里面的元素，方便我們觀察調試，這個方法和棧的行為無關，只是一個輔助方法

print（）{
    this.items.forEach((item, index) => {
        console.log(`${index+1}:${item}`)
    })
}

最后完整的代碼如下

class Stack {

  constructor() {
    this.items = []  // 定義一個數組來保存棧里面的元素
  }
  // 添加元素到棧頂
  push(item) {
    this.items.push(item)
  }
  // 從棧頂移除元素，同時返回被移除元素
  pop() {
    return this.items.pop()
  }
  // 返回棧頂的元素，不對棧本身做修改
  peek() {
    return this.items[this.items.length-1]
  }
  // 判斷棧是否為空
  isEmpty() {
    return this.items.length === 0
  }
  // 清空棧
  remove() {
    this.items = []
  }
  // 返回棧里面元素的個數
  length() {
    return this.items.length
  }

  print() {
    this.items.forEach((item, index) => {
        console.log(`${index+1}:${item}`)
    })
  }
}

這樣這個棧就基本實現了，下面來實際運行一下實現好的這個Stack類，首先我們需要實例化這個類，然后分別調用實例的方法來查看效果

const myStack = new Stack()  //  實例化

myStack.isEmpty() // true

myStack.push("這是棧的第一個元素") 
myStack.push("這是棧的第二個元素") 

myStack.print() // 1: 這是棧的第一個元素 2：這是棧的第二個元素

myStack.peek() // 這是棧的第二個元素

myStack.pop() // 這是棧的第一個元素

myStack.length() // 1

myStack.isEmpty() // false

myStack.remove() // 這時棧里面已經沒有元素了

myStack.isEmpty() // true

棧的基本說明就到此了，下篇會總結一下和棧類似的數據結構，隊列。

云服務器 GPU云服務器 javascript全棧視頻 javascript全棧教程 javascript全棧開發 javascript快速全棧開發

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/88657.html

javasctipt 工作原理之調用棧

摘要：譯者注翻譯一個對新手比較友好的工作原理解析系列文章注意以下全部是概念經驗豐富的老鳥可以離場啦正文從這里開始隨著的流行團隊們正在利用來支持多個級別的技術棧包括前端后端混合開發嵌入式設備以及更多這篇文章旨在成為深入挖掘和實際上他是怎么工作的系列譯者注翻譯一個對新手比較友好的 JavaScript 工作原理解析系列文章注意: 以下全部是概念,經驗豐富的老鳥可以離場啦正文從這里開始隨...

Pines_Cheng 2019-08-23 10:38 評論0 收藏0
前端進擊的巨人（二）：棧、堆、隊列、內存空間

摘要：中有三種數據結構棧堆隊列。前端進擊的巨人一執行上下文與執行棧，變量對象中解釋執行棧時，舉了一個乒乓球盒子的例子，來演示棧的存取方式，這里再舉個栗子搭積木。對于基本類型，棧中存儲的就是它自身的值，所以新內存空間存儲的也是一個值。面試經常遇到的深淺拷貝，事件輪詢，函數調用棧，閉包等容易出錯的題目，究其原因，都是跟JavaScript基礎知識不牢固有關，下層地基沒打好，上層就是豆腐渣工程，...

edgardeng 2019-08-23 14:43 評論0 收藏0
[譯文] JavaScript工作原理：引擎、運行時、調用棧概述

摘要：調用棧是單線程編程語言，意味著它只有單一的調用棧。調用棧是一種數據結構，基本記錄了程序運行的位置。舉個例子，先來看如下所示的代碼當引擎開始執行這段代碼時，調用棧將是空的。這正是拋出異常時棧追蹤的構造過程這基本上就是異常拋出時調用棧的狀態。原文 How JavaScript works: an overview of the engine, the runtime, and the c...

PAMPANG 2019-08-23 17:04 評論0 收藏0
理解 JavaScript 執行棧

摘要：執行棧所有的代碼在運行時都是在執行上下文中進行的。引擎執行棧頂的函數，執行完畢，彈出當前執行上下文。但是這里我們也可以用執行棧來解釋。這是 JavaScript 系列的第 3 篇。引例首先來看一個引例： function foo() { console.log(1); bar(); console.log(3); } function bar() { conso...

yacheng 2019-08-23 14:01 評論0 收藏0
【Javascript】探究javascript中的堆/棧/任務隊列與并發模型 event loop

摘要：而函數調用結束返回時，運行時會將棧頂的調用結構彈出。并發模型與引擎是單線程的，它的并發模型基于事件循環當線程中的同步任務執行完，執行棧為空時，則從任務隊列中取出異步任務進行處理。在當前的微任務沒有執行完成時，是不會執行下一個宏任務的。堆/棧/隊列在javascript中，存在調用棧 (call stack)和內存堆(memory heap) ,程序中函數依次進入棧中等待執行,若執行...

desdik 2019-08-26 13:47 評論0 收藏0