JavaScript數(shù)據(jù)結(jié)構(gòu)《棧》

nanchen2251 發(fā)布于2019-08-21 16:44 / 366人閱讀

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

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

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

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

代碼實現(xiàn)

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

class Stack {

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

  // 添加元素到棧頂
  push() { }
  // 從棧頂移除元素，同時返回被移除元素
  pop() { }
  // 返回棧頂?shù)脑兀粚１旧碜鲂薷?  peek() { }
  // 判斷棧是否為空
  isEmpty() { }
  // 清空棧
  remove() { }
  // 返回棧里面元素的個數(shù)
  length() { }
}

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

push

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

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

pop

接下來要實現(xiàn)是pop方法（行為），pop會移除棧頂?shù)脑夭⑶視祷乇灰瞥脑兀@個方法我們同樣可以用JavaScript數(shù)組的pop方法來實現(xiàn)

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

peek

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

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

isEmpty

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

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

remove

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

remove() {
    this.items = []
}

length

最后要實現(xiàn)的是length方法，length方法返回棧的大小，這個同樣可以用數(shù)組的length來實現(xiàn)

length() {
    return this.items.length
}

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

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

最后完整的代碼如下

class Stack {

  constructor() {
    this.items = []  // 定義一個數(shù)組來保存棧里面的元素
  }
  // 添加元素到棧頂
  push(item) {
    this.items.push(item)
  }
  // 從棧頂移除元素，同時返回被移除元素
  pop() {
    return this.items.pop()
  }
  // 返回棧頂?shù)脑兀粚１旧碜鲂薷?  peek() {
    return this.items[this.items.length-1]
  }
  // 判斷棧是否為空
  isEmpty() {
    return this.items.length === 0
  }
  // 清空棧
  remove() {
    this.items = []
  }
  // 返回棧里面元素的個數(shù)
  length() {
    return this.items.length
  }

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

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

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() // 這時棧里面已經(jīng)沒有元素了

myStack.isEmpty() // true

棧的基本說明就到此了，下篇會總結(jié)一下和棧類似的數(shù)據(jù)結(jié)構(gòu)，隊列。