JavaScript數(shù)據(jù)結(jié)構(gòu)《隊(duì)列》

saucxs 發(fā)布于2019-08-21 16:47 / 487人閱讀

摘要：在隊(duì)列的這種數(shù)據(jù)結(jié)構(gòu)里面，新增的元素都在尾部，要移除的元素都在頂部。代碼實(shí)現(xiàn)下面用代碼來(lái)實(shí)現(xiàn)隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)，同樣都采用的語(yǔ)法，我們先定義一個(gè)類來(lái)表示隊(duì)列，然后在這個(gè)類的基礎(chǔ)上定義一下方法來(lái)模擬隊(duì)列的行為。

隊(duì)列和棧非常的類似，但是他們采用了不同的原則，棧采用的是后進(jìn)先出，隊(duì)列正好相反，采用的是先進(jìn)先出的原則。隊(duì)列的定義如下

隊(duì)列是遵循FIFO(先進(jìn)先出)原則的有序集合，新添加的元素保存在隊(duì)列的尾部，要移除的元素保存在隊(duì)列的頂部。在隊(duì)列的這種數(shù)據(jù)結(jié)構(gòu)里面，新增的元素都在尾部，要移除的元素都在頂部。

舉一個(gè)生活中的例子，在我們平時(shí)去吃肯德基吃飯時(shí)肯定要排隊(duì)，這條隊(duì)伍就可以看做是一個(gè)隊(duì)列，排在隊(duì)伍前面的就是隊(duì)列的頂部，隊(duì)伍后面的就是隊(duì)列的尾部，后來(lái)的人都要排在隊(duì)伍的后面（隊(duì)列的尾部），這就符合了隊(duì)列先進(jìn)先出的原則了（先排隊(duì)的可以先點(diǎn)餐）。

代碼實(shí)現(xiàn)

下面用代碼來(lái)實(shí)現(xiàn)隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)，同樣都采用ES6的語(yǔ)法，我們先定義一個(gè)類Queue來(lái)表示隊(duì)列，然后在這個(gè)類的基礎(chǔ)上定義一下方法來(lái)模擬隊(duì)列的行為。

class Queue {

  constructor() {
    // 定義一個(gè)數(shù)組來(lái)保存隊(duì)列里面的元素
    this.items = []
  }

  // 在隊(duì)列尾部添加一個(gè)或者多個(gè)元素
  enqueue(element) { }
    
  // 移除隊(duì)列頂部的元素，并返回被移除的元素
  dequeue() { }
    
  // 清空隊(duì)列
  remove() { }
    
  // 返回隊(duì)列頂部的元素，不對(duì)隊(duì)列本身做修改
  front() { }
    
  // 判斷隊(duì)列是否為空
  isEmpty() { }
    
  // 返回隊(duì)列里面元素的個(gè)數(shù)
  length() { }
}

這樣我們就定義好一個(gè)基類了，下面來(lái)分別實(shí)現(xiàn)隊(duì)列的行為方法

enqueue

第一個(gè)要實(shí)現(xiàn)的就是enqueue方法，這個(gè)方法接收一個(gè)參數(shù)，然后把該參數(shù)插入隊(duì)列的尾部，因?yàn)檫@里我們是用數(shù)組來(lái)存儲(chǔ)隊(duì)列的元素的，所以可以用數(shù)組的push方法來(lái)實(shí)現(xiàn)該操作，代碼如下

 enqueue (element) {
   this.items.push(element)
 }

dequeue

下面接著實(shí)現(xiàn)dequeue方法，這個(gè)方法會(huì)從隊(duì)列里面移除項(xiàng)，由于隊(duì)列遵循的是先進(jìn)先出的原則，所以我們要移除的元素就是隊(duì)列頂部的元素，同樣因?yàn)檫@里我們是用數(shù)組來(lái)存儲(chǔ)隊(duì)列的元素的，所以可以用數(shù)組的shift方法來(lái)實(shí)現(xiàn)該操作。代碼如下

dequeue () {
    return this.items.shift()
}

remove

接著來(lái)實(shí)現(xiàn)remove方法，改方法會(huì)移除隊(duì)列里面所有的項(xiàng)，同理我們把保存隊(duì)列元素的數(shù)組置空就好了，代碼如下

remove () {
    this.items = []
}

front

上面的方法都是對(duì)隊(duì)列本身有修改的，接下來(lái)要實(shí)現(xiàn)的方法front做的是只讀操作，front方法會(huì)返回隊(duì)列頂部的元素但不對(duì)隊(duì)列本身進(jìn)行修改，代碼實(shí)現(xiàn)如下

front () {
    return this.items[0]
}

isEmpty

isEmpty方法判斷隊(duì)列是否為空，也就是保存隊(duì)列的數(shù)組的長(zhǎng)度是否等于0，代碼實(shí)現(xiàn)如下

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

length

最后一個(gè)方法返回隊(duì)列的長(zhǎng)度，同理就是返回保存隊(duì)列元素的數(shù)組的長(zhǎng)度就好了，代碼如下

length () {
    return this.item.length
}

這里和棧一樣添加一個(gè)輔助方法print來(lái)打印棧里面的元素，方便我們觀察調(diào)試，這個(gè)方法和隊(duì)列的行為無(wú)關(guān)，只是一個(gè)輔助方法

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

這樣隊(duì)列的方法就全部寫好了，最后完整Queue類的代碼如下

class Queue {

  constructor() {
    // 定義一個(gè)數(shù)組來(lái)保存隊(duì)列里面的元素
    this.items = []
  }

  // 在隊(duì)列尾部添加一個(gè)或者多個(gè)元素
  enqueue (element) {
      this.items.push(element)
  }
  // 移除隊(duì)列頂部的元素，并返回被移除的元素
  dequeue() { 
      return this.items.shift()
  }
  // 清空隊(duì)列
  remove() {
      this.items = []
  }
  // 返回隊(duì)列頂部的元素，不對(duì)隊(duì)列本身做修改
  front() { 
      return this.items[0]
  }
  // 判斷隊(duì)列是否為空
  isEmpty() { 
      return this.items.length === 0
  }
  // 返回隊(duì)列里面元素的個(gè)數(shù)
  length() { 
      return this.item.length
  }
    
  print（）{
      this.items.forEach((item, index) => {
          console.log(`${index+1}:${item}`)
      })
  }
}

使用Queue類

要使用這個(gè)類我們得先實(shí)例化它

const queue = new Queue()

queue.isEmpty() // true

queue.push("我是隊(duì)列的第一個(gè)元素")
queue.push("我是隊(duì)列的第二個(gè)元素")

queue.print() // 1: 我是隊(duì)列的第一個(gè)元素 2：我是隊(duì)列的第二個(gè)元素

queue.dequeue() // 我是隊(duì)列的第一個(gè)元素

queue.front() // 我是隊(duì)列的第二個(gè)元素

queue.length() // 1

queue.isEmpty() // false

queue.remove() // 這時(shí)隊(duì)列里面已經(jīng)沒(méi)有元素了

queue.isEmpty() // true

總結(jié)

隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)運(yùn)用的是非常的廣泛的，就比如javaScript的運(yùn)行機(jī)制，我們都知道javaScript是單線程的，是不能同時(shí)執(zhí)行多個(gè)任務(wù)，但是單線程就意味著所有任務(wù)需要排隊(duì)。但是在javaScript里面，很多時(shí)候阻止線程運(yùn)行的很慢的是網(wǎng)絡(luò)IO之類，這時(shí)候CPU是空閑的，這樣就會(huì)造成資源的浪費(fèi)。所以javaScript在主線程之外實(shí)現(xiàn)了一個(gè)任務(wù)隊(duì)列，像IO之類比較慢的操作暫時(shí)都會(huì)掛在任務(wù)隊(duì)列上，這樣不會(huì)影響到主線程上任務(wù)的執(zhí)行，等到IO的響應(yīng)回來(lái)后再回到主線程上來(lái)執(zhí)行掛起的任務(wù)。例子就是我們的Ajax請(qǐng)求，定時(shí)器等。